Самые медленные алгоритмы сортировки

К первой группе отнесем самые медленные алгоритмы, принадлежащие к классу O(n²), хотя некоторые из них в лучших случаях могут дать высокие показатели производительности.

Сортировка простой выборкой реализует сформулированную стратегию выборки. В реализации алгоритма возникает проблема значения ключа «пусто» после выбора элемента. Часто используют в качестве такового некоторое заведомо отсутствующее во входной последовательности значение, например, максимальное из теоретически возможных. Другой, более строгий подход – создание отдельного вектора, каждый элемент которого имеет логический тип и отражает состояние соответствующего элемента входного множества («истина» – «непусто», «ложь» – «пусто»). Именно такой вариант приведен в примере.

Роль входной последовательности выполняет параметр aList, роль выходной – параметр bList, роль вектора состояний – массив c. Алгоритм несколько усложняется за счет того, что для установки начального значения при поиске минимума приходится отбрасывать уже «пустые» элементы.

{ Сортировка простой выборкой }

procedure SelectionStdSort(aList, bList: TList; aCompare: TCompareFunc);

Var

i, j, m, N: Integer;

{ Состояние элементов входного множества}

c: array of Boolean;

Begin

N:=aList.Count;

SetLength(c, N);

{ Сброс отметок}

for i:=0 to N-1 do c[i]:=True;

{ Поиск первого невыбранного элемента во входном множестве}

for i:=0 to N-1 do

Begin

j:=0;

while not c[j] do j:=j+1;

m:=j;

{ Поиск минимального элемента }

for j:=1 to N-1 do

if c[j] and (aCompare(aList.List[j], aList.List[m]) = -1) then m:=j;

{ Запись в выходное множество}

bList.Items[i]:=aList.List[m];

{ В входное множество - "пусто" }

c[m]:=False;

end;

end;

Количество выполняемых сравнений для первого прохода равно n, для второго n-1 и т.д. Общее число сравнений будет равно n(n+1)/2-1 и порядок алгоритма – O(n²). Однако количество перестановок значительно меньше – при каждом выполнении цикла производится всего одна перестановка, а общее их количество n-1 и О(n).

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

Обменная сортировка простой выборкой. Алгоритм сортировки простой выборкой, однако, редко применяется в том варианте, в каком он описан выше. Гораздо чаще применяется, обменный вариант. При обменной сортировке входное и выходное множество располагаются в одной и той же области памяти; выходное – в начале области, входное – в оставшейся ее части. В исходном состоянии входное множество занимает всю область, а выходное множество – пустое. По мере выполнения сортировки входное множество сужается, а выходное – расширяется. Обменная сортировка простой выборкой показана в следующем примере.

{ Обменная сортировка простой выборкой }

procedure SelectionSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

i, j, IndexOfMin: Integer;

Temp: Pointer;

Begin

{ Перебор элементов выходного множества }

for i:=aFirst to aLast-1 do

{ Входное множество - [i:N-1]; выходное - [1:i-1] }

Begin

IndexOfMin:=i;

{ Поиск минимума во входном множестве }

for j:=i+1 to aLast do

{ Обмен первого элемента входного множества с минимальным }

if (aCompare(aList.List[j], aList.List[IndexOfMin]) < 0) then

IndexOfMin:=j;

Temp:=aList.List[i];

aList.List[i]:=aList.List[IndexOfMin];

aList.List[IndexOfMin]:=Temp;

end;

end;

Результаты трассировки представлены в табл. 4.8. Двоеточием показана граница между входным и выходным множествами. Очевидно, обменный вариант обеспечивает экономию памяти и не возникает проблемы «пустого» значения. Общее число сравнений уменьшается вдвое – n·(n-1)/2, но порядок алгоритма остается прежним – O(n²). Количество перестановок n-1, но перестановка вдвое более времяемкая операция, чем пересылка в предыдущем алгоритме.

Табл. 4.8. Трассировка сортировки простой выборкой.

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

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

Пузырьковая сортировка. Входное множество просматривается, при этом попарно сравниваются соседние элементы. Если порядок их следования не соответствует заданному критерию упорядоченности, то элементы меняются местами. В результате одного просмотра при сортировке по возрастанию элемент с самым большим значением ключа переместится («всплывет») на последнее место во множестве.

При следующем проходе на свое место «всплывет» второй по величине ключа элемент и т.д. Для постановки на свои места n элементов следует сделать n-1 проходов. Выходное множество формируется в конце сортируемой последовательности, при каждом следующем проходе его объем увеличивается на 1, а объем входного множества уменьшается на 1.

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

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

procedure BubbleSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

i,j: Integer;

Temp: Pointer;

Done: Boolean;

Begin

for i:=aFirst to aLast-1 do

Begin

Done:=True;

for j:=aLast downto i+1 do

{ Переставить j-й и j-1-й элементы }

if aCompare(aList.List[j],aList.List[j-1]) < 0 then

Begin

Temp:=aList.List[j];

aList.List[j]:=aList.List[j-1];

aList.List[j-1]:=Temp;

Done:=False;

end;

if Done then Exit;

end;

end;

Пузырьковая сортировка принадлежит к алгоритмам класса O(n²). В реализации присутствуют два цикла: внешний и внутренний, при этом количество выполнений каждого цикла зависит от числа элементов. При первом выполнении внутреннего цикла будет произведено n-1 сравнений, при втором – n-2, при третьем – n-3 и т.д. Всего будет n-1 таких циклов, а общее число сравнений составит: (n-1)+(n-2)+..+1. Сумму можно упростить до n(n-1)/2 или (n²-n)/2 и получаем O(n²).

Количество перестановок в худшем случае (при отсортированном исходном наборе в обратном порядке) равно числу сравнений. В лучшем случае (при исходной упорядоченности всех элементов) будет выполнен всего один проход, (n-1) сравнение и ни одной перестановки, что дает линейный порядок O(n).

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

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

Результаты трассировки примера представлены в табл. 4.9.

Табл. 4.9. Трассировка пузырьковой сортировки.

Модификация пузырьковой сортировки носит название шейкер-сортировки. Направления просмотров чередуются: за просмотром от начала к концу входного множества следует просмотр в обратном направлении. При просмотре в прямом направлении элемент с самым большим значением ставится на свое место в последовательности, при просмотре в обратном направлении – элемент с самым маленьким.

{ Пузырьковая двухпроходная сортировка }

procedure ShakerSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

i: Integer;

Temp: Pointer;

Begin

while aFirst < aLast do

Begin

for i:=aLast downto aFirst+1 do

if aCompare(aList.List[i], aList.List[i-1]) < 0 then

Begin

Temp:=aList.List[i];

aList.List[i]:=aList.List[i-1];

aList.List[i-1]:=Temp;

end;

Inc(aFirst);

for i:=aFirst+1 to aLast do

if aCompare(aList.List[i], aList.List[i-1]) < 0 then

Begin

Temp:=aList.List[i];

aList.List[i]:=aList.List[i-1];

aList.List[i-1]:=Temp;

end;

Dec(aLast);

end;

end;

Алгоритм по-прежнему относится к классу O(n²), но время его выполнения немного меньше. Название сортировка получила ввиду того, что элементы в наборе колеблются относительно своих позиций до тех пор, пока набор не будет отсортирован. Алгоритм неустойчивый.

Описанный алгоритм весьма эффективен для задач восстановления упорядоченности, когда исходная последовательность уже была упорядочена, но подверглась незначительным изменениям. Упорядоченность в последовательности с одиночным изменением будет гарантированно восстановлена всего за два прохода.

Сортировка простыми вставками представляет дословную реализацию стратегии включения. Порядок алгоритма сортировки простыми вставками – O(n²), если учитывать только операции сравнения. Но сортировка требует еще в среднем n²/4 перемещений, что делает ее менее эффективной, чем сортировка выборкой. Алгоритм сортировки простыми вставками иллюстрируется следующим примером.

{ Сортировка простыми вставками }

procedure InsertionStdSort(aList, bList: TList; aCompare: TCompareFunc);

var i, j, k: Integer;

Begin

{ Перебор входного массива }

for i:=0 to aList.Count-1 do

Begin

j:=0;

{ Поиск места для a[i] в выходном массиве

при условии (j < i) и (b[j] <= a[i]) }

while (j < i) and (aCompare(bList.Items[j],aList.Items[i]) <= 0) do

j:=j+1;

{ Освобождение места для нового элемента }

for k:=i downto j+1 do

bList.Items[k]:=bList.Items[k-1];

{ Запись в выходной массив }

bList.Items[j]:=aList.Items[i];

end;

end;

Сортировка принадлежит к группе устойчивых алгоритмов. Его эффективность может быть улучшена при применении не линейного, а двоичного поиска. Однако следует иметь в виду, что такое улучшение может быть достигнуто лишь на множествах значительного по количеству элементов объема. Алгоритм требует большого числа пересылок, поэтому при значительном объеме одного элемента эффективность может определяться не количеством операций сравнения, а количеством пересылок.

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

Первый элемент входного множества примыкает к концу выходного множества. На каждом шаге сортировки происходит перераспределение последовательности: выходное множество увеличивается на один элемент, а входное – уменьшается. Это происходит за счет того, что первый элемент входного множества теперь считается последним элементом выходного.

Затем выполняется просмотр выходного множества от конца к началу с перестановкой соседних элементов, которые не соответствуют критерию упорядоченности. Просмотр прекращается, когда прекращаются перестановки. Это приводит к тому, что последний элемент выходного множества «выплывает» на свое место во множестве.

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

{ Пузырьковая сортировка методом вставок }

procedure InsertionBublSort(aList: TList;

aFirst, aLast: Integer; aCompare: TCompareFunc);

Var

i, j: Integer;

Temp: Pointer;

Begin

{ Перебор входного массива }

for i:=aFirst+1 to aLast do

{ Входное множество - [i..N-1], выходное множество - [0..i-1] }

Begin

{ Запоминается значение нового элемента }

Temp:=aList.List[i];

j:=i;

{ Поиск места для элемента в выходном множестве со сдвигом

цикл закончится при достижении начала или,

когда будет встречен элемент, меньший нового }

while (j > aFirst) and (aCompare(Temp, aList.List[j-1]) < 0) do

Begin

{ Все элементы, большие нового сдвигаются }

aList.List[j]:=aList.List[j-1];

{ Цикл от конца к началу выходного множества }

Dec(j);

end;

{ Новый элемент ставится на свое место }

aList.List[j]:=Temp;

end;

end;

Интересная особенность приведенной реализации алгоритма состоит в следующем: значение текущего элемента сохраняется в локальной переменной, а затем при поиске нужного места его вставки (внутренний цикл) происходит перемещение каждого элемента, значение которого больше текущего, на одну позицию вправо, тем самым, перемещая «дыру» в наборе влево. В конце концов, обнаруживается нужное место, и сохраненное значение помещается в освободившееся место. Результат трассировки представлены в табл. 4.10.

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

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

Табл. 4.10. Трассировка сортировки вставками.