Пузырьковая сортировка

Пузырьковая сортировка (bubblesort) — это алгоритм, предназначенный для сортировки списков, которые уже находятся в почти упорядоченном состоянии. Если в начале процедуры список полностью отсортирован, алгоритм выполняется очень быстро за время порядка O(N). Если часть элементов находятся не на своих местах, алгоритм выполняется медленнее. Если первоначально элементы расположены в случайном порядке, алгоритм выполняется за время порядка O(N²). Поэтому перед применением пузырьковой сортировки важно убедиться, что элементы в основном расположены по порядку.

При пузырьковой сортировке список просматривается до тех пор, пока не найдутся два соседних элемента, расположенных не по порядку. Тогда они меняются местами, и процедура продолжается дальше. Алгоритм повторяет этот процесс до тех пор, пока все элементы не займут свои места.

На рис. 9.2 показано, как алгоритм вначале обнаруживает, что элементы 6 и 3 расположены не по порядку, и поэтому меняет их местами. Во время следующего прохода, меняются местами элементы 5 и 3, в следующем — 4 и 3. После еще одного прохода алгоритм обнаруживает, что все элементы расположены по порядку, и завершает работу.

Можно проследить за перемещениями элемента, который первоначально был расположен ниже, чем после сортировки, например элемента 3 на рис. 9.2. Во время каждого прохода элемент перемещается на одну позицию ближе к своему конечному положению. Он движется к вершине списка подобно пузырьку газа, который всплывает к поверхности в стакане воды. Этот эффект и дал название алгоритму пузырьковой сортировки.

Можно внести в алгоритм несколько улучшений. Во‑первых, если элемент расположен в списке выше, чем должно быть, вы увидите картину, отличную от той, которая приведена на рис. 9.2. На рис. 9.3 показано, что алгоритм вначале обнаруживает, что элементы 6 и 3 расположены в неправильном порядке, и меняет их местами. Затем алгоритм продолжает просматривать массив и замечает, что теперь неправильно расположены элементы 6 и 4, и также меняет их местами. Затем меняются местами элементы 6 и 5, и элемент 6 занимает свое место.

 

@Рис. 9.2. «Всплывание» элемента

 

========236

 

@Рис. 9.3. «Погружение» элемента

 

При просмотре массива сверху вниз, элементы, которые перемещаются вверх, сдвигаются всего на одну позицию. Те же элементы, которые перемещаются вниз, сдвигаются на несколько позиций за один проход. Этот факт можно использовать для ускорения работы алгоритма пузырьковой сортировки. Если чередовать просмотр массива сверху вниз и снизу вверх, то перемещение элементов в прямом и обратном направлениях будет одинаково быстрым.

Во время проходов сверху вниз, наибольший элемент списка перемещается на место, а во время проходов снизу вверх — наименьший. Если M элементов списка расположены не на своих местах, алгоритму потребуется не более M проходов для того, чтобы расположить элементы по порядку. Если в списке N элементов, алгоритму потребуется N шагов для каждого прохода. Таким образом, полное время выполнения для этого алгоритма будет порядка O(M * N).

Если первоначально список организован случайным образом, большая часть элементов будет находиться не на своих местах. В примере, приведенном на рис. 9.3, элемент 6 трижды меняется местами с соседними элементами. Вместо выполнения трех отдельных перестановок, можно сохранить значение 6 во временной переменной до тех пор, пока не будет найдено конечное положение элемента. Это может сэкономить большое число шагов алгоритма, если элементы перемещаются на большие расстояния внутри массива.

Последнее улучшение — ограничение проходов массива. После просмотра массива, последние переставленные элементы обозначают часть массива, которая содержит неупорядоченные элементы. При проходе сверху вниз, например, наибольший элемент перемещается в конечное положение. Поскольку нет больших элементов, которые нужно было бы поместить за ним, то можно начать очередной проход снизу вверх с этой точки и на ней же заканчивать следующие проходы сверху вниз.

 

========237

 

Таким же образом, после прохода снизу вверх, можно сдвинуть позицию, с которой начнется очередной проход сверху вниз, и будут заканчиваться последующие проходы снизу вверх.

Реализация алгоритма пузырьковой сортировки на языке Visual Basic использует переменные min и max для обозначения первого и последнего элементов списка, которые находятся не на своих местах. По мере того, как алгоритма повторяет проходы по списку, эти переменные обновляются, указывая положение последней перестановки.

 

Public Sub Bubblesort(List() As Long, ByVal min As Long, ByVal max As Long)

Dim last_swap As Long

Dim i As Long

Dim j As Long

Dim tmp As Long

 

‘ Повторять до завершения.

Do While min < max

   ‘ «Всплывание».

   last_swap = min - 1

   ‘ То есть For i = min + 1 To max.

   i = min + 1

   Do While i <= max

      ‘ Найти «пузырек».

      If List(i - 1) > List(i) Then

          ‘ Найти, куда его поместить.

          tmp = List(i - 1)

          j = i

          Do

              List(j - 1) = List(j)

              j = j + 1

              If j > max Then Exit Do

          Loop While List(j) < tmp

          List(j - 1) = tmp

          last_swap = j - 1

          i = j + 1

      Else

      i = i + 1

      End If

   Loop

   ‘ Обновить переменную max.

   max = last_swap - 1

 

   ‘ «Погружение».

   last_swap = max + 1

   ‘ То есть For i = max -1 To min Step -1

   i = max - 1

   Do While i >= min

      ‘ Найти «пузырек».

      If List(i + 1) < List(i) Then

      ‘ Найти, куда его поместить.

          tmp = List(i + 1)

          j = i

          Do

              List(j + 1) = List(j)

              j = j - 1

              If j < min Then Exit Do

          Loop While List(j) > tmp

          List(j + 1) = tmp

          last_swap = j + 1

          i = j - 1

      Else

          i = i - 1

      End If

   Loop

   ‘ Обновить переменную min.

   Min = last_swap + 1

Loop

End Sub

 

 

==========238

 

Для того чтобы протестировать алгоритм пузырьковой сортировки при помощи программы Sort, поставьте галочку в поле Sorted (Отсортированные) в области Initial Ordering (Первоначальный порядок). Введите число элементов в поле # Unsorted (Число несортированных). После нажатия на кнопку Go (Начать), программа создает и сортирует список, а затем переставляет случайно выбранные пары элементов. Например, если вы введете число 10 в поле # Unsorted, программа переставит 5 пар чисел, то есть 10 элементов окажутся не на своих местах.

Для второго варианта первоначального алгоритма, программа сохраняет элемент во временной переменной при перемещении на несколько шагов. Этот происходит еще быстрее, если использовать функцию API MemCopy. Алгоритм пузырьковой сортировки в программе FastSort, используя функцию MemCopy, сортирует элементы в 50 или 75 раз быстрее, чем первоначальная версия, реализованная в программе Sort.

В табл. 9.2 приведено время выполнения пузырьковой сортировки 2000 элементов на компьютере с процессором Pentium с тактовой частотой 90 МГц в зависимости от степени первоначальной упорядоченности списка. Из таблицы видно, что алгоритм пузырьковой сортировки обеспечивает хорошую производительность, только если список с самого начала почти отсортирован. Алгоритм быстрой сортировки, который описывается далее в этой главе, способен отсортировать тот же список из 2000 элементов примерно за 0,12 сек, независимо от первоначального порядка расположения элементов в списке. Пузырьковая сортировка может превзойти этот результат, только если примерно 97 процентов списка было упорядочено до начала сортировки.

 

=====239

 

@Таблица 9.2. Время пузырьковой сортировки 2.000 элементов

 

Несмотря на то, что пузырьковая сортировка медленнее, чем многие другие алгоритмы, у нее есть свои применения. Пузырьковая сортировка часто дает наилучшие результаты, если список изначально уже почти упорядочен. Если программа управляет списком, который сортируется при создании, а затем к нему добавляются новые элементы, пузырьковая сортировка может быть лучшим выбором.

Быстрая сортировка

Быстрая сортировка (quicksort) — рекурсивный алгоритм, который использует подход «разделяй и властвуй». Если сортируемый список больше, чем минимальный заданный размер, процедура быстрой сортировки разбивает его на два подсписка, а затем рекурсивно вызывает себя для сортировки двух подсписков.

Первая версия алгоритма быстрой сортировки, обсуждаемая здесь, достаточно проста. Если алгоритм вызывается для подсписка, содержащего не более одного элемента, то подсписок уже отсортирован, и подпрограмма завершает работу.

Иначе, процедура выбирает какой‑либо элемент из списка и использует его для разбиения списка на два подсписка. Она помещает элементы, которые меньше, чем выбранный элементы в первый подсписок, а остальные — во второй, и затем рекурсивно вызывает себя для сортировки двух подсписков.

 

Public Sub QuickSort(List() As Long, ByVal min as Integer, _

ByVal max As Integer)

Dim med_value As Long

Dim hi As Integer

Dim lo As Integer

 

‘ Если осталось менее 1 элемента, подсписок отсортирован.

If min >= max Then Exit Sub

 

‘ Выбрать значение для деления списка.

med_value = list(min)

lo = min

hi = max

Do

    Просмотр от hi до значения < med_value.

   Do While list(hi) >= med_value

      hi = hi - 1

      If hi <= lo Then Exit Do

   Loop

   If hi <= lo Then

      list(lo) = med_value

      Exit Do

   End If

   ‘ Поменять местами значения lo и hi.

   list(lo) = list(hi)

 

   ‘ Просмотр от lo до значения >= med_value.

   lo = lo + 1

   Do While list(lo) < med_values

      lo = lo + 1

      If lo >= hi Then Exit Do

   Loop

   If lo >= hi Then

      lo = hi

      list(hi) = med_value

      Exit Do

   End If

   ‘ Поменять местами значения lo и hi.

   list(hi) = list(lo)

Loop

 

‘ Рекурсивная сортировка двух подлистов.

QuickSort list(), min, lo - 1

QuickSort list(), lo + 1, max

End Sub

 

 

=========240

 

Есть несколько важных моментов в этой версии алгоритма, которые стоит упомянуть. Во‑первых, значение med_value для деления списка не входит ни в один подсписок. Это означает, что в двух подсписках содержится на одни элемент меньше, чем в исходном списке. Т.к. число рассматриваемых элементов уменьшается, то в конечном итоге алгоритм завершит работу.

Эта версия алгоритма использует в качестве разделителя первый элемент в списке. В идеале, это значение должно было бы находиться где‑то в середине списка, так чтобы два подсписка были примерно равного размера. Тем не менее, если элементы первоначально почти отсортированы, то первый элемент — наименьший в списке. При этом алгоритм не поместит ни одного элемента в первый подсписок, и все элементы во второй. Последовательность действий алгоритма будет примерно такой, как показано на рис. 9.4.

В этом случае каждый вызов подпрограммы требует порядка O(N) шагов для перемещения всех элементов во второй подсписок. Т.к. алгоритм рекурсивно вызывает себя N - 1 раз, время его выполнения будет порядка O(N²), что не лучше, чем у ранее рассмотренных алгоритмов. Ситуацию еще более ухудшает то, что уровень вложенности рекурсии алгоритма N - 1. Для больших списков огромная глубина рекурсии приведет к переполнению стека и сбою в работе программы.

 

=========242

 

@Рис. 9.4. Быстрая сортировка упорядоченного списка

 

Существует много стратегий выбора разделительного элемента. Можно использовать элемент из середины списка. Это может оказаться неплохим выбором, тем не менее, может оказаться и так, что это окажется наименьший или наибольший элемент списка. При этом один подсписок будет намного больше, чем другой, что приведет к снижению производительности до порядка O(N²) и глубокому уровню рекурсии.

Другая стратегия может заключаться в том, чтобы просмотреть весь список, вычислить среднее арифметическое всех значений, и использовать его в качестве разделительного значения. Этот подход будет давать неплохие результаты, но потребует дополнительных усилий. Дополнительный проход со сложностью порядка O(N) не изменит теоретическое время выполнения алгоритма, но снизит общую производительность.

Третья стратегия — выбрать средний из элементов в начале, конце и середине списка. Преимущество этого подхода в быстроте, потому что потребуется выбрать всего три элемента. При этом гарантируется, что этот элемент не является наибольшим или наименьшим в списке, и вероятно окажется где‑то в середине списка.

И, наконец, последняя стратегия, которая используется в программе Sort, заключается в случайном выборе элемента из списка. Возможно, это будет неплохим выбором. Даже если это не так, возможно на следующем шаге алгоритм, возможно, сделает лучший выбор. Вероятность постоянного выпадения наихудшего случая очень мала.

Интересно, что этот метод превращает ситуацию «небольшая вероятность того, что всегда будет плохая производительность» в ситуацию «всегда небольшая вероятность плохой производительности». Это довольно запутанное утверждение объясняется в следующих абзацах.

При использовании других методов выбора точки раздела, существует небольшая вероятность того, что при определенной организации списка время сортировки будет порядка O(N²), Хотя маловероятно, что подобная организация списка в начале сортировки встретится на самом деле, тем не менее, время выполнения при этом будет определенно порядка O(N²), неважно почему. Это то, что можно назвать «небольшой вероятностью того, что всегда будет плохая производительность».

 

===========242

 

При случайном выборе точки раздела первоначальное расположение элементов не влияет на производительность алгоритма. Существует небольшая вероятность неудачного выбора элемента, но вероятность того, что это будет происходить постоянно, чрезвычайно мала. Это можно обозначить как «всегда небольшая вероятность плохой производительности». Независимо от первоначальной организации списка, очень маловероятно, что производительность алгоритма будет порядка O(N²).

Тем не менее, все еще остается ситуация, которая может вызвать проблемы при использовании любого из этих методов. Если в списке очень мало различных значений в списке, алгоритм заносит множество одинаковых значений в подсписок при каждом вызове. Например, если каждый элемент в списке имеет значение 1, последовательность выполнения будет такой, как показано на рис. 9.5. Это приводит к большому уровню вложенности рекурсии и дает производительность порядка O(N²).

Похожее поведение происходит также при наличии большого числа повторяющихся значений. Если список состоит из 10.000 элементов со значениями от 1 до 10, алгоритм довольно быстро разделит список на подсписки, каждый из которых содержит только одно значение.

Наиболее простой выход — игнорировать эту проблему. Если вы знаете, что данные не имеют такого распределения, то проблемы нет. Если данные имеют небольшой диапазон значений, то вам стоит рассмотреть другой алгоритм сортировки. Описываемые далее в этой главе алгоритмы сортировки подсчетом и блочной сортировки очень быстро сортируют списки, данных в которых находятся в узком диапазоне.

Можно внести еще одно небольшое улучшение в алгоритм быстрой сортировки. Подобно многих другим более сложным алгоритмам, описанным далее в этой главе, быстрая сортировка — не самый лучший выбор для сортировки небольших списков. Благодаря своей простоте, сортировка выбором быстрее при сортировке примерно десятка записей.

 

@Рис. 9.5. Быстрая сортировка списка из единиц

 

==========243

 

@Таблица 9.3. Время быстрой сортировки 20.000 элементов

 

Можно улучшить производительность быстрой сортировки, если прекратить рекурсию до того, как подсписки уменьшатся до нуля, и использовать для завершения работы сортировку выбором. В табл. 9.3 приведено время, которое занимает выполнение быстрой сортировки 20.000 элементов на компьютере с процессором Pentium с тактовой частотой 90 МГц, если останавливать сортировку при достижении подсписками определенного размера. В этом тесте оптимальное значение этого параметра было равно 15.

Следующий код демонстрирует доработанный алгоритм:

 

Public Sub QuickSort*List() As Long, ByVal min As Long, ByVal max As Long)

Dim med_value As Long

Dim hi As Long

Dim lo As Long

Dim i As Long

 

‘ Если в списке больше, чем CutOff элементов,

‘ завершить его сортировку процедурой SelectionSort.

If max - min < cutOff Then

   SelectionSort List(), min, max

   Exit Sub

End If

 

‘ Выбрать разделяющее значение.

i = Int((max - min + 1) * Rnd + min)

med_value = List(i)

 

‘ Переместить его вперед.

List(i) = List(min)

 

lo = min

hi = max

Do

   ‘ Просмотр сверху вниз от hi до значения < med_value.

   Do While List(hi) >= med_value

      hi = hi - 1

      If hi <= lo Then Exit Do

   Loop

   If hi <= lo Then

      List(lo) = med_value

      Exit Do

   End If

 

   ‘ Поменять местами значения lo и hi.

   List(lo) = List(hi)

 

   ‘ Просмотр снизу вверх от lo до значения >= med_value.

   lo = lo + 1

   Do While List(lo) < med_value

      lo = lo + 1

      If lo >= hi Then Exit Do

   Loop

   If lo >= hi Then

      lo = hi

      List(hi) = med_value

      Exit Do

   End If

 

   ‘ Поменять местами значения lo и hi.

   List(hi) = List(lo)

Loop

 

‘ Сортировать два подсписка.

QuickSort List(), min, lo - 1

QuickSort List(), lo + 1, max

End Sub

 

 

=======244

 

Многие программисты выбирают алгоритм быстрой сортировки, т.к. он дает хорошую производительность в большинстве обстоятельств.

Сортировка слиянием

Как и быстрая сортировка, сортировка слиянием (mergesort) — это рекурсивный алгоритм. Он также разделяет список на два подсписка, и рекурсивно сортирует подсписки.

Сортировка слиянием делит список пополам, формируя два подсписка одинакового размера. Затем подсписки рекурсивно сортируются, и отсортированные подсписки сливаются, образуя полностью отсортированный список.

Хотя этап слияния легко понять, это наиболее интересная часть алгоритма. Подсписки сливаются во временный массив, и результат копируется в первоначальный список. Создание временного массива может быть недостатком, особенно если размер элементов велик. Если размер временного размера очень большой, он может приводить к обращению к файлу подкачки и значительно снижать производительность. Работа с временным массивом также приводит к тому, что большая часть времени уходит на копирование элементов между массивами.

Так же, как и в случае с быстрой сортировкой, можно ускорить выполнение сортировки слиянием, остановив рекурсию, когда подсписки достигают определенного минимального размера. Затем можно использовать сортировку выбором для завершения работы.

 

=========245

 

 

Public Sub Mergesort(List() As Long, Scratch() As Long, _

ByVal min As Long, ByVal max As Long)

Dim middle As Long

Dim i1 As Long

Dim i2 As Long

Dim i3 As Long

 

‘ Если в списке больше, чем CutOff элементов,

‘ завершить его сортировку процедурой SelectionSort.

If max - min < CutOff Then

   Selectionsort List(), min, max

   Exit Sub

End If

 

‘ Рекурсивная сортировка подсписков.

middle = max \ 2 + min \ 2

Mergesort List(), Scratch(), min, middle

Mergesort List(), Scratch(), middle + 1, max

 

‘ Слить отсортированные списки.

i1 = min      ‘ Индекс списка 1.

i2 = middle + 1 ‘ Индекс списка 2.

i3 = min      ‘ Индекс объединенного списка.

Do While i1 <= middle And i2 <= max

   If List(i1) <= List(i2) Then

      Scratch(i3) = List(i1)

      i1 = i1 + 1

   Else

      Scratch(i3) = List(i2)

      i2 = i2 + 1

   end If

   i3 = i3 + 1

Loop

 

‘ Очистка непустого списка.

Do While i1 <= middle

   Scratch(i3) = List(i1)

   i1 = i1 + 1

   i3 = i3 + 1

Loop

Do While i2 <= max

   Scratch(i3) = List(i2)

   i2 = i2 + 1

   i3 = i3 + 1

Loop

 

‘ Поместить отсортированный список на место исходного.

For i3 = min To max

   List(i3) = Scratch(i3)

Next i3

End Sub

 

 

========246

 

Сортировка слиянием тратит много времени на копирование временного массива на место первоначального. Программа FastSort использует функцию API MemCopy, чтобы немного ускорить эту операцию.

Даже с использованием функции MemCopy, сортировка слиянием немного медленнее, чем быстрая сортировка. В нашем тесте на компьютере с процессором Pentium с тактовой частотой 90 МГц, сортировка слиянием потребовала 2,95 сек для упорядочения 30.000 элементов со значениями в диапазоне от 1 до 10.000. Быстрая сортировка потребовала всего 2,44 сек.

Преимущество сортировки слиянием в том, что время ее выполнения остается одинаковым независимо от различных распределений и начального расположения данных. Быстрая же сортировка дает производительность порядка O(N²) и достигает глубокого уровня вложенности рекурсии, если список содержит много одинаковых значений. Если список большой, быстрая сортировка может переполнить стек и привести к аварийному завершению работы программы. Сортировка слиянием никогда не достигает слишком глубокого уровня вложенности рекурсии, т.к. всегда делит список на равные части. Для списка из N элементов, глубина вложенности рекурсии для сортировки слиянием составляет всего лишь log(N).

В другом тесте, в котором использовались 30.000 элементов со значениями от 1 до 100, сортировка слиянием потребовала столько же времени, сколько и для элементов со значениями от 1 до 10.000 — 2,95 секунд. Быстрая сортировка заняла 15,82 секунды. Если значения лежали между 1 и 50, сортировка слиянием потребовала 2,95 секунд, тогда как быстрая сортировка — 138,52 секунды.