Алгоритмы сортировки

В этом разделе мы рассмотрим различные алгоритмы решения задачи сортировки. Задача сортировки ставится следующим образом: дана последовательность записей R₁,R₂,...,R_n. Каждая запись содержит ключ - некоторую величину, для которой определены операции “больше” и “меньше”. Ключ может быть числовой, символьный, строковый или иметь более сложную структуру. Требуется переставить записи в таком порядке, чтобы их ключи строго возрастали. В практических приложениях ключи могут повторяться, поэтому мы будем требовать не строгого возрастания ключей, а их неубывания. Для самого алгоритма сортировки структура записи R_j не важна, так что можно, не умаляя общности, считать, что сортируется числовая последовательность. Какие требования предъявляются к алгоритму сортировки? Конечно, прежде всего он должен быть верным, то есть давать правильное решение задачи. И, во-вторых, он должен быть достаточно быстрым. Если длина сортируемой последовательности не очень велика, то любой алгоритм сортировки пригоден и, как правило, наиболее простые алгоритмы оказываются самыми эффективными, но если последовательность может быть достаточно длинной, решающее значение приобретает сложность алгоритма. Понятие “сложность” уже обсуждалось нами, и для алгоритмов сортировки оно определяется точно так же: алгоритм имеет сложность f(n), если для сортировки последовательности из n элементов ему требуется C×f(n) операций, где C не зависит от n. Мы знаем два алгоритма сортировки - сортировка обменами и сортировка выбором. Оценим их сложность. Сортировка обменами требует ровно n(n-1)/2 сравнений и не более n(n-1)/2 обменов, следовательно, ее сложность - n². Сортировка выбором требует столько же сравнений и не более n-1 обменов. Иногда при анализе алгоритмов сортировки отдельно оценивают их сложность относительно операций сравнения и относительно операций обмена, в этом случае сортировка выбором имеет сложность n² сравнений и n обменов. Но суммарная сложность алгоритма тем не менее остается n². Эти два алгоритма очень просты, не требуют дополнительной памяти и для малых n достаточно эффективны, но для больших n практически не применимы, так как время их работы становится неприемлемо большим. Известны десятки других алгоритмов сортировки, в том числе имеющих сложность меньшую, чем n². Здесь мы рассмотрим: сортировку “пузырьком”, сортировку простыми вставками, сортировку бинарными вставками, сортировку слияниями, сортировку Шелла, класс алгоритмов QuickSort, сортировку бинарным деревом поиска, алгоритм HeapSort, поразрядную сортировку и сортировку множеством.

Сортировка “пузырьком” - также довольно простой и широко известный алгоритм. Он заключается в следующем: сравниваем X[1] и X[2], если X[1] < X[2], то сравниваем X[2] и X[3], и так далее, пока не дойдем до конца последовательности или не встретим пару элементов X[i], X[i+1] такую, что X[i]>X[i+1]. Элемент X[i+1] находится “не на своем месте”, перемещаем его туда, где он должен стоять. Для этого меняем местами элементы X[j] и X[j-1], j=i+1,i,i-1,..., пока не выполнится условие X[j]>X[j-1] или не дойдем до начала последовательности. Теперь все элементы от X[1] до X[i+1] расположены в нужном порядке, продолжаем проверку, начиная с X[i+1]. Сортировка “пузырьком” обладает двумя замечательными достоинствами - во-первых, если последовательность уже упорядочена или почти упорядочена, он является одним из самых быстрых среди всех известных алгоритмов, во-вторых, его легко запрограммировать так, что меняться местами будут только пары соседних элементов; если сортируются записи разной длины, то это обстоятельство существенно упрощает программу. Оценим сложность сортировки “пузырьком”. В худшем случае потребуется порядка n² сравнений и n² обменов, так что это алгоритм сложности n², но для сортировки почти упорядоченной последовательности необходимо всего порядка n×m операций, где m - количество элементов, стоящих “не на своих местах”. Если m много меньше n, то эта величина много меньше n². Приведем один из вариантов записи сортировки “пузырьком”. Здесь x - числовой массив с элементами типа T_Num; n1, n2 индексы первого и последнего элементов сортируемой части массива.

 

Procedure Bubble_Sorting(n1,n2 : Word; Var x : T_Array);

Var

i,j : Word;

tmp : T_Num;

Begin

i:=n1;

While i<n2 Do Begin

While x[i+1]>=x[i] Do Begin

Inc(i);

If i>=n2 Then Break;

End;

If i>=n2 Then Continue;

j:=i+1;

tmp:=x[j];

While tmp<x[j-1] Do Begin

x[j]:=x[j-1];

Dec(j);

If j=1 Then Break;

End;

x[j]:=tmp;

End;

End;

 

Сортировка простыми вставками выполняется следующим образом: пусть подпоследовательность X[1], X[2], ..., X[k] уже упорядочена, вставим в нее X[k+1], не нарушая упорядоченности. Для этого будем, начиная с X[1], искать первый элемент X[i] такой, что X[i] > X[k+1], после чего вставим X[k+1] перед X[i] и получим упорядоченную подпоследовательность длиной k+1. Начнем вставки с подпоследовательности X[1] из одного элемента, которая очевидно упорядочена. Чтобы вставить элемент в подпоследовательность, нужно предварительно сдвинуть все элементы X[i], X[i+1],..., X[k] на одну позицию вправо. Если использовать для этого не цикл, а более быстрые средства (в Паскале это процедура Move), то скорость алгоритма существенно возрастет.

 

Procedure Insert_Sorting(n1,n2 : Word; Var x : T_Array);

Var

N_Sort,Ins_Pos : Word;

Current : T_Num;

Begin

N_Sort:=n1;

While N_Sort<n2 Do Begin

Current:=x[N_Sort+1];

If x[n1]>Current Then Ins_Pos:=n1-1

Else

If x[N_Sort]<=Current Then Ins_Pos:=N_Sort

Else Begin

Ins_Pos:=1;

While x[Ins_Pos]<Current Do Inc(Ins_Pos);

Dec(Ins_Pos);

End;

If N_Sort<>Ins_Pos Then Begin

Move(x[Ins_Pos+1],x[Ins_Pos+2],

(N_Sort-Ins_Pos)*SizeOf(T_Num));

x[Ins_Pos+1]:=Current;

End;

Inc(N_Sort);

End;

End;

 

Сортировка простыми вставками так же, как и все предыдущие методы, имеет сложность n².

Алгоритм сортировки бинарными вставками получается из сортировки простыми вставками, если место для нового элемента искать не простым перебором, а известным нам методом бисекции, который имеет сложность log₂(n). Метод бисекции используется здесь практически в том же виде, что и для решения алгебраического уравнения.

 

Procedure Binary_Sorting(n1,n2 : Word; Var x : T_Array);

Var

N_Sort,Ins_Pos,a,b,t : Word;

Current : T_Num;

Begin

N_Sort:=n1;

While N_Sort<n2 Do Begin

Current:=x[N_Sort+1];

If x[n1]>Current Then Ins_Pos:=n1-1

Else

If x[N_Sort]<=Current Then Ins_Pos:=N_Sort

Else Begin

a:=n1;

b:=N_Sort;

t:=(a+b) Div 2;

While (t<>a)And(t<>b) Do Begin

If x[t]<Current Then a:=t Else b:=t;

t:=(a+b) Div 2;

End;

Ins_Pos:=a;

End;

If N_Sort<>Ins_Pos Then Begin

Move(x[Ins_Pos+1],x[Ins_Pos+2],

(N_Sort-Ins_Pos)*SizeOf(T_Num));

x[Ins_Pos+1]:=Current;

End;

Inc(N_Sort);

End;

End;

 

Сортировка бинарными вставками требует n-1 выполнения операции бинарного поиска и n-1 выполнения операции вставки. Если бы мы умели вставить элемент, затратив не более C×log₂(n) операций, то этот алгоритм имел бы сложность n×log₂(n). Но, к сожалению, сама вставка все же требует порядка n операций, так что суммарная сложность сортировки бинарными вставками равна n².

Сортировка слияниями - это первый из рассматриваемых нами алгоритмов, который имеет сложность n×log₂(n). Доказано, что не существует алгоритмов, которые в общем случае имели бы меньшую сложность (в некоторых частных случаях удается построить алгоритмы сложности n). Идея сортировки слияниями достаточно проста. Предположим, что левая и правая половины последовательности уже упорядочены. Объединим две половины в один массив, не нарушая упорядоченности, алгоритм слияния двух упорядоченных массивов нам уже известен. Но как упорядочить “голову” и “хвост” массива? Для этого предварительно упорядочим их слияниями, а их половины еще раньше упорядочим слияниями и так далее. Таким образом, сортировка слияниями начинается со слияния пар соседних элементов в упорядоченную двухэлементную подпоследовательность, затем эти пары сливаются в четверки и так далее, пока не будет получена полная упорядоченная последовательность. Сортировку слияниями можно записать и рекурсивной, и не рекурсивной процедурой. Приведем рекурсивную запись.

 

Procedure Glue_Sorting_Recursive(Num1,Num2 : Word; Var x : T_Array);

Var

i,Half,i1,i2 : Word;

Buf : ^T_Array;

tmp : T_Num;

Begin

If Num2=Num1 Then Exit;

If Num2=Num1+1 Then Begin

If x[Num1]>x[Num2] Then Begin

tmp:=x[Num1];

x[Num1]:=x[Num2];

x[Num2]:=tmp;

End;

Exit;

End;

Half:=(Num2+Num1)Div 2;

Glue_Sorting_Recursive(Num1,Half,x);

Glue_Sorting_Recursive(Half+1,Num2,x);

New(Buf);

Move(x[Num1],Buf^[Num1],(Num2-Num1+1)*SizeOf(T_Num));

<слияние последовательностей Buf[Num1],...,Buf[Half] и Buf[Half+1] ,..., Buf[Num2] в последовательность x[Num1],...,x[Num2]>

Dispose(Buf);

End;

 

Сортировка слияниями требует дополнительного буфера памяти, равного размеру сортируемого массива. Оценим сложность алгоритма. Каждое слияние увеличивает вдвое размер упорядоченных частей последовательности, следовательно, после h слияний размер упорядоченных частей будет равен 2^h. Следовательно, если n есть степень двойки, нужно ровно log₂(n) слияний, а если нет, то достаточно log₂(n)+1 слияния. Каждое слияние требует порядка n операций, следовательно, суммарная сложность алгоритма равна n×log₂(n), причем она не зависит от расположения элементов в исходной последовательности, это очень ценное качество для алгоритмов сортировки.

Сортировка методом Шелла выполняется следующим образом. Вычисляется максимальное расстояние в серии h по закону h[0]=1, h[i+1]=3h[i]+1, i=0,1,..., пока h<[n/d], где d - эмпирический коэффициент »9-10. Затем сортируются серии с найденным шагом h (в серию входят элементы с номерами k,k+h,k+2h,..., где k=1...h, т.е. всего в последовательности h серий). Сортировка в каждой серии осуществляется методом включения (“пузырьком”). Вычисляется новое h по формуле h=[h/3], и сортируются серии с новым h. Наконец, когда h становится равным 1, начисто сортируется вся последовательность (одна серия с h=1).

 

Procedure Schell_Sorting(n : Word; Var a : T_Array);

Const d=9;

Var

i,j,k : LongInt;

h : Word;

tmp : T_Num;

Begin

h:=1;{расстояние в серии}

While h<n Div d Do h:=3*h+1; {получаем исходное приращение}

Repeat {сортировки сериями с расстояниями h}

For k:=1 To h Do Begin {сортировка k-й серии включением}

i:=k+h;

While i<=n Do Begin

{включение a[i] на свое место среди предшествующих в серии}

tmp:=a[i];

j:=i-h;

While (j>=1)And(a[j]>tmp) Do Begin

a[j+h]:=a[j];

Dec(j,h);

End;

a[j+h]:=tmp;

Inc(i,h);

End;

End;

h:=h Div 3;

{здесь массив отсортирован сериями с расстояниями h}

Until h=0;

End;

 

Метод Шелла имеет сложность n×log₂(n).

Алгоритмы, принадлежащие к классу алгоритмов QuickSort или алгоритмы “быстрой сортировки”, в каком-то смысле симметричны алгоритму сортировки слияниями. В них сначала вся последовательность грубо сортируется, чтобы разделить “маленькие” и “большие” элементы, при этом “маленькие” перемещаются в начало последовательности, а “большие” - в конец. После этого тем же способом сортируется начало и конец последовательности. В некоторых алгоритмах этого класса выполняется не двоичная, а троичная грубая сортировка, то есть элементы разделяются на “маленькие”, “средние” и “большие”. Рассмотрим самый простой из алгоритмов “быстрой сортировки”. Выберем в качестве “среднего” элемента первый элемент последовательности. Выделим в памяти буфер, равный по размеру исходной последовательности. Все элементы последовательности, кроме первого, будем сравнивать со “средним” элементом. Если очередной элемент меньше среднего, то отнесем его к “маленьким” и запишем в первый свободный элемент буфера. Если элемент больше “среднего”, то он “большой”, и мы записываем его в последний свободный элемент буфера. Когда все элементы проверены, в буфере остается место для одного элемента, куда и записывается “средний” элемент. Теперь “средний” элемент стоит на своем месте: все элементы, расположенные левее, меньше, и все элементы, расположенные правее, больше, чем “средний” элемент. Затем этот алгоритм применяется к началу и к концу последовательности, и так до тех пор, пока длина упорядочиваемой подпоследовательности не станет равной единице. Для увеличения скорости обычно применяют этот алгоритм, пока длина подпоследовательности не станет меньше некоторого Nmin, а для меньших подпоследовательностей используют какой-нибудь простой алгоритм сложности n², например сортировку “пузырьком”. Дело в том, что для малых n алгоритмы сложности n×log₂(n) оказываются, как правило, менее эффективными, чем простые алгоритмы (вспомним, что количество операций равно произведению сложности на некоторую константу, которая у простых алгоритмов во много раз меньше). Алгоритмы класса QuickSort в большинстве случаев очень быстры, то есть оправдывают свое название, но представим себе, что исходная последовательность уже упорядочена. Мы выберем в качестве “среднего” первый - самый маленький элемент, тогда начало последовательности будет содержать 0 элементов, а конец - n-2 элемента. Грубо сортируя конец последовательности, мы снова не получим ни одного “маленького” элемента и так далее. Очевидно, что эффективность такого алгоритма зависит от того, насколько хорошо выбран “средний” элемент. Если он делит последовательность на две примерно равные части, то алгоритм имеет сложность n×log₂(n), если же одна из частей много больше другой, то сложность алгоритма стремится к n². Говорят, что такой алгоритм имеет сложность n² в худшем случае. Алгоритмы QuickSort удобнее всего записывать рекурсивными процедурами, например, так:

 

Procedure Quick_Sorting_Recursive(Num1,Num2 : Word; Var x : T_Array);

Var

Buf : ^T_Array;

i,iL,iR : Word;

tmp : T_Num;

Begin

If Num2=Num1 Then Exit;

If Num2=Num1+1 Then Begin

If x[Num2]<x[Num1] Then Begin

tmp:=x[Num1];

x[Num1]:=x[Num2];

x[Num2]:=tmp;

End;

Exit;

End;

New(Buf);

iL:=Num1;

iR:=Num2;

tmp:=x[Num1];

For i:=Num1+1 TO Num2 Do Begin

If x[i]<tmp Then Begin

Buf^[iL]:=x[i];

Inc(iL);

End

Else Begin

Buf^[iR]:=x[i];

Dec(iR);

End;

End;

Buf^[iL]:=tmp;

Move(Buf^[Num1],x[Num1],(Num2-Num1+1)*SizeOf(T_Num));

Dispose(Buf);

If iL-1>=Num1 Then Quick_Sorting_Recursive(Num1,iL-1,x);

If iL+1<=Num2 Then Quick_Sorting_Recursive(iL+1,Num2,x);

End;

 

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

Представленный здесь алгоритм - самый простой из алгоритмов QuickSort, известно много других вариантов. Отметим среди них три - метод Синглтона, быструю сортировку Хоара и сортировку “движениями”. В методе Синглтона “средний” элемент выбирается как средний из трех элементов: первого, последнего и стоящего точно в середине последовательности. Такой простой прием позволяет сохранить сложность n×log₂(n) при любых входных данных. Быстрая сортировка Хоара использует не двоичную, а троичную грубую сортировку, а “средний” элемент выбирается случайным образом, ее полезно применять, если в последовательности много одинаковых элементов. Сортировка “движениями” не требует дополнительного буфера памяти, грубая сортировка осуществляется непосредственно в исходном массиве.

Рассмотрим подробнее этот полезный алгоритм. Пусть индексы L и R первоначально указывают на первый и последний элементы последовательности. Будем “двигать” поочередно индекс L вправо, а индекс R влево, пока они не станут равны друг другу. Сначала “двигаем” индекс R, пока выполняется условие X[R]>X[L]. Если условие не выполнилось, значит элементы X[L] и X[R] расположены “неправиль-но”, поменяем их местами и начнем “двигать” индекс L. Встретив X[L]>X[R], поменяем местами элементы и вновь начнем “двигать” индекс R. Когда L станет равно R, все “маленькие” элементы будут находиться левее, все “большие” - правее, а элемент X[L=R] будет “средним”. Сортировка движениями очень экономно расходует память, но в худшем случае имеет сложность n². Все названные алгоритмы могут легко быть запрограммированы как в рекурсивной, так и в нерекурсивной форме.

Сортировка бинарным деревом поиска выполняется следующим образом: элементы исходной последовательности поочередно добавляются в первоначально пустое упорядоченное бинарное дерево. Когда все элементы включены в дерево, его достаточно обойти в инфиксном порядке, записывая элементы в массив. Этот алгоритм довольно просто записать как в рекурсивной, так и в нерекурсивной форме. Алгоритмы включения элемента в дерево и обхода дерева были описаны выше. Такой алгоритм сортировки в среднем имеет сложность n×log₂(n), но в худшем случае, когда дерево получается очень плохо сбалансированным, его сложность возрастает до n².

Алгоритм HeapSort, который называют также “сорти-ровка пирамидой”, использует линейную проекцию сортдерева, или приоритетную очередь (мы уже видели, что это одно и то же). Сортировка выполняется следующим образом: элементы последовательности с индексами 2,3,...,n поочередно включаются в проекцию сортдерева. Затем из сортдерева n раз удаляется корневой (самый большой) элемент и записывается на то место, где находился концевой элемент проекции. После чего проекция сортдерева оказывается пустой, а последовательность упорядоченной. Алгоритмы включения элемента в сортдерево и удаления корневого элемента сортдерева были приведены выше. Сортировка HeapSort не требует дополнительной памяти и обеспечивает сложность n×log₂(n) при любых входных данных.

Существуют ли алгоритмы сортировки со сложностью, меньшей, чем n×log₂(n)? Если ключи сортируемых записей обладают нужными свойствами, то можно применить так называемую поразрядную сортировку. Это очень простой, но, на первый взгляд, несколько странный алгоритм. Рассмотрим его на конкретном примере. Требуется упорядочить последовательность целых чисел, причем известно, что все числа принадлежат отрезку [0,999]. Пусть, например, исходная последовательность содержит числа 834 998 027 601 280 113 345 472 557 769 592 005 331 980 573 645. Разместим все числа последовательности в десяти списках в соответствии с их последней цифрой: в нулевом списке - числа, заканчивающиеся цифрой 0, в первом списке - числа, заканчивающиеся единицей, и так далее, а потом вновь соберем числа из списков в последовательность, сначала из нулевого, затем из первого и в последнюю очередь - из девятого. Последовательность примет вид 280 980 601 331 472 592 113 573 834 345 005 645 027 557 998 769. На втором шаге проделаем то же самое, но будем распределять числа по спискам в соответствии со второй цифрой: 601 005 113 027 331 834 345 645 557 769 472 573 280 980 592 998. И наконец, на третьем шаге будем распределять числа по спискам в соответствии с первой цифрой числа : 005 027 113 280 331 345 472 557 573 592 601 645 769 834 980 998. И последовательность упорядочена. Такой алгоритм применим для сортировки целых чисел или строк, но для вещественных чисел его использовать нельзя, так как в них невозможно выделить разряды. Конечно, в программе не стоит использовать десятичную запись чисел, гораздо эффективнее выделять в числах 16-ричные, или 8-ричные, или 4-ричные цифры. Сложность поразрядной сортировки формально равна n, но все-таки более реалистично оценить ее как n×m, где m - наибольшее количество разрядов в числе (потребуется m шагов для завершения сортировки).

Для некоторых типов ключей возможна еще более быстрая сортировка, чем поразрядная, назовем этот алгоритм сортировкой множеством. Пусть сортируемые величины таковы, что их тип может быть базовым типом множества в языке Паскаль, например пусть это будут символы. Включим все символы в множество, а затем поместим в последовательность все символы, содержащиеся в множестве, в порядке возрастания - и задача решена. Потребовалось порядка n операций для формирования множества и порядка m операций для записи символов в упорядоченную последовательность, где m - количество различных символов, которые могут присутствовать в исходной последовательности. Таким образом, суммарная сложность алгоритма равна n+m. Не обязательно использовать в этом алгоритме именно тип Set, для сортировки двухбайтовых целых чисел можно, например, описать массив с элементами типа Boolean и устанавливать его элемент в True, если соответствующее число встретилось в последовательности; такой способ хранения множеств часто используется в программировании.