Методы внутренней сортировки

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

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

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

Имеются простые и усовершенствованные методы внутренней сортировки. Простые методы обеспечивают достаточную скорость для небольших массивов и входят как составная часть в усовершенствованные методы. Наиболее часто рассматривают три класса простых методов сортировки: включениями, выбором и обменом.

Рассмотрим подробнее простые методы внутренней сортировки. В качестве объекта сортировки выступает массив из n элементов A. В составе элемента есть ключ сортировки. Без ограничения общности можно считать, что элементы состоят только из ключа, поэтому их можно сравнивать между собой. Будем для определенности сортировать элементы по возрастанию значений элементов.

Сортировка простыми включениями выполняется следующим образом. Пусть первые k элементов массива A отсортированы, то есть a₁ £ a₂ £ …£ a_k. Сравним последовательно элемент a_k+1 с элементами a_k, a_k-1,… ,a₁ до выполнения соотношения a_j £ a_k+1 £ a_j+1. Элементы a_k, a_k-1,… ,a_j+1 и сдвигаются на одно место вправо, а элемент a_k+1 помещается на место элемента a_j+1. Сначала считаем, что отсортирован один элемент массива. Сортировка заканчивается, когда на “свое” место помещается элемент a_n.

Трудоемкость простого включения зависит от начального распределения элементов. Число пересылок M составляет в среднем (n²+9n-10)/4. Некоторым улучшением метода является использование бинарного поиска для включения очередного элемента в отсортированную часть массива. Это уменьшает необходимое количество сравнений, но не пересылок.

Сортировка простым выбором начинается с поиска минимального элемента массива, который обменивается затем с первым элементом. Далее находится минимальный элемент среди a₂, a₃,… ,a_n и обменивается со вторым элементом. Затем на третье место помещается наименьший элемент из a₃,… ,a_n и так далее. Обычно сортировка выбором лучше, чем включениями, однако начальная частичная сортировка не уменьшает трудоемкость метода. Число пересылок M составляет в среднем n(log ₂ n+0.6).

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

For I:=2 to N do

For J:=N downto I do

if A[J-1]>A[J] then

begin

X:= A[J-1]; A[J-1]= A[J];

A[j]:=X

end;

Метод сортировки пузырьком получил свое название по аналогии с всплывающим пузырьком воздуха и, возможно, поэтому незаслуженно популярен. При каждом проходе меньшие (“легкие”) элементы поднимаются вверх. Метод ассиметричен: “легкие” элементы всплывают быстро, а “тяжелые” тонут медленно. Очевидное улучшение состоит в том, чтобы при каждом проходе запоминать, были ли обмены, и заканчивать сортировку, если их не было. Можно также запоминать место последнего обмена, чтобы выше сравнение не производить. Еще одно улучшение составляет основу шейкер-сортировки, в которой чередуются прямое и обратное направления проходов массива. Все улучшения уменьшают только число сравнений. Количество пересылок M составляет в среднем 3(n²-n)/4. Метод пузырька хуже как метода включения, так и метода выбора.

Сортировка включениями Шелла или сортировка с убывающими приращениями является усовершенствованным методом простого включения. В основе метода лежит понятие k-сортировки, при которой сортируются отдельно k частей массива A. Любая часть образуется из начального элемента и каждого k-го элемента, отсчитываемого от начального. Сортировка проводится на месте методом простого включения. Оказывается, что m-сортировка, проведенная после k-сортировки при m<k, не нарушает k-сортировки, а вносит свой вклад в конечный результат. Метод Шелла состоит в выполнении последовательности k-сортировок с уменьшающимися шагами k. Шаги сортировки h₁, h₂,…, h_t должны удовлетворять условиям h _i > h_i+1 и h_t =1. По рекомендациям Кнута,

t = [log ₃ n] – 1, h_k-1 = 3h_k+1, h_t =1 .

Количество пересылок сортировки Шелла пропорционально величине n^{1. 2}.

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

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

Пирамидой называется последовательность элементов a_k, a_k+1,…,a_r такая, что a_i £ a_2i и a_i £ a_2i+1 при i = k, k+1,…,[r/2], где [t] – целая часть числа t. В нашей задаче внутренней сортировки будем считать, что эти элементы представляют собой часть массива A с соответствующими индексами. Пирамиду удобно изображать бинарным деревом. Например, в следующей пирамиде

a₁

a₂ a₃

a₄ a₅ a₆ a₇

a₂ £ a₄ и a₂ £ a₅, а a₁ является минимальным элементом по определению пирамиды.

Если элементы a₁, a₂,…,a_r составляют пирамиду, то элементы a₂, a₃,…,a_r также являются пирамидой и могут быть изображены деревом без корня. Элементы a₃,…,a_r также являются пирамидой и т. д.

Пусть к элементам a₂, a₃,…,a_r добавляется новый элемент a₁ с неизвестным значением. Попытаемся так поменять местами элементы a₁, a₂,…,a_r, чтобы они вновь стали пирамидой. Для этого если a₁ больше a₂ или a₃, поменяем местами a₁ с минимальным из этих элементов. Если оказавшийся на новом месте элемент a₁ снова больше одного из своих сыновей, выполним аналогичный обмен. В конце концов элементы a₁, a₂,…,a_r будут пирамидой. Такая процедура называется просеиванием.

А как путем обменов организовать пирамиду из всего массива a₁, a₂,…,a_n ? Определим k=(n div 2) +1 и расположим элементы a_k, a_k+1,…,a_n в основании пирамиды. Далее будем просеивать последовательно элементы a_k-1, a_k-2,…, a₁ среди элементов с большими индексами. В результате элементы a₁, a₂,…,a_n будут представлять собой пирамиду.

Рассмотрим пример начальной организации пирамиды из массива 25, 14, 18, 11, 31, 37, 15. Сначала организуем основание пирамиды

11(4) 31(5) 37(6) 15(7)

где в скобках указаны индексы массива.

После просеивания элементов 18 и 14 пирамида примет вид

11(2) 15(3)

14(4) 31(5) 37(6) 18(7)

Наконец, после просеивания первого элемента 25 получится пирамида

11(1)

14(2) 15(3)

25(4) 31(5) 37(6) 18(7)

Не всегда пирамида оказывается настолько правильной, как сейчас. Например, из элементов массива 5, 11, 14, 7, 3, 8, 1, 9, 18, 6 получится пирамида

1(1)

3(2) 5(3)

7(4) 6(5) 8(6) 14(7)

9(8) 18(9) 11(10)

Итак, массив a₁, a₂,…,a_n представляет собой пирамиду. Поместим элемент из корня на место последнего элемента массива, а последний элемент просеем среди элементов a₁, a₂,…,a_n-1. Элемент из корня отправим на место предпоследнего элемента, а предпоследний элемент просеем среди элементов a₁, a₂,…,a_n-2. Продолжая процесс, в итоге получим отсортированный по убыванию массив A.

Ниже приводится программа пирамидальной сортировки.

Program Piramida; { пирамидальная сортировка }

Uses Crt;

Const M=100; { например }

Type Index=0..m;

Var

A: array [1..M] of integer;

L, R, N: index;

I, J, K, X: integer;

B: boolean;

Procedure Vvod(var n: Index);

{ N-фактическое число элементов }

Begin

B:=True; N:=0;

While B do

begin

Write('Введите ключ (-1 - конец): ');

ReadLn(L);

if L>=0 then

begin

N:=N+1;

A[N]:=L;

end

else B:=False

end;

End;

Procedure Vivod;

Begin

WriteLn;

For I:=1 to N do

Write(' ', A[I])

End;

Procedure Proseiv;

{ просеивание элемента A[K] в пирамиде A[K+1], A[K+2], …, A[R] }

Begin

B:=True; I:=K; J:=2*K; X:=A[K];

While (J<=R) and B do

begin

if J<R then { иначе один преемник у A[K] }

if A[J]>A[J+1] then J:=J+1;

if X>A[J] then

begin { спуск на уровень }

A[I]:=A[J]; I:=J; J:=2*J

end

else B:=False

{ в 2 последних операторах IF знаки сравнения '<', }

{ если в корень пирамиды посылается MAX значение }

end;

A[I]:=X;

End;

Begin { основная программа }

ClrScr;

Vvod(N);

K:=(N div 2)+1; R:=N;

While K>1 do

begin

K:=K-1;

Proseiv

end;

{ далее сортировка пирамиды на месте }

{ сейчас K=1 }

While R>1 do

begin

X:=A[1]; A[1]:=A[R]; A[R]:=X; R:=R-1;

Proseiv

end;

Vivod;

ReadLn

End.

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

Среднее число пересылок элементов M в методе пирамидальной сортировки составляет (n log ₂ n)/2.

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

Пусть элементы массива A расположены по убыванию. Для изменения порядка сортировки можно первый элемент массива поменять с последним, второй с предпоследним и так далее. Этот принцип лежит в основе сортировки Хоара.

Выберем случайным образом некоторый элемент массива X=a_k. Будем перемещаться по массиву слева направо, увеличивая индекс i, до выполнения условия a_i ³ X. Затем пойдем справа налево, уменьшая индекс j, до выполнения условия a_j £ X. Если выполнится условие i £ j, поменяем местами a_i и a_j. Продолжим этот процесс, пока индексы i и j не перехлестнутся, то есть до выполнения условия i > j. В результате из массива будут выделены две части, в первой из которых значения элементов будут не больше X, а во второй не меньше X. К обеим частям массива применим ту же процедуру.

В качестве случайного элемента можно выбрать средний элемент массива. Рассмотрим описанную процедуру на примере массива 60, 63, 10, 51, 51, 51, 85, 3, 24, 55. Разделяющим элементом является пятый элемент массива, равный 51. Стрелками показаны обмениваемые элементы.

60 63 10 51 51 51 85 3 24 55

В результате получим массив 24, 3, 10, 51, 51, 51, 85, 63, 60, 55. Значение i окажется равным 6, а j примет значение 4. Далее будем по отдельности сортировать первые 4 и последние 5 элементов массива A.

Ниже приведен рекурсивный вариант программы, выполняющей сортировку Хоара.

Program QSort; { быстрая сортировка Хоара }

Uses Crt;

Const M=100;

Type index=0..m;

Var

A: array [1..M] of integer;

K, R, N: index;

I, J, L, X, W: integer;

B: boolean;

Procedure Vvod(var N: index);

{ N-фактическое число элементов }

Begin

B:=True; N:=0;

While B do

begin

Write('Введите ключ (-1 - конец): ');

ReadLn(L);

if L>=0 then

begin

N:=N+1;

A[N]:=L

end

else B:=False

end;

End;

Procedure Vivod;

Begin

WriteLn;

For I:=1 to N do

Write(' ', A[I])

End;

Procedure Sort(K, R: index);

Begin

I:=K; { нижний индекс }

J:=R; { верхний индекс }

X:=A[(K+R) div 2];

Repeat

While A[I]<X do I:=I+1;

While A[J]>X do J:=J-1;

if I<=J then { A[I]>=X>=A[J] }

begin

W:=A[I]; A[I]:=A[J]; A[J]:=W;

I:=I+1; J:=J-1 { стало A[I-1]<=X<=A[J+1] }

end

Until I>J;

{ A[L]<=X для L=K,K+1,...,J }

{ A[L]>=X для L=I,...,R }

if K<J then Sort(K, J);

if I<R then Sort(I, R)

End;

Begin

ClrScr;

Vvod(n);

Sort(1, N);

Vivod;

ReadLn

End.

Можно реализовать сортировку Хоара и без использования рекурсии. Пары индексов (k, r), задающих границы сортировки, поместим в стек. Разделив часть массива, определенную парой из вершины стека, заменим эту пару двумя новыми парами индексов. Сначала в стеке будет пара (1, n), затем после первого разделения содержимым стека будут пары (1, j) и (i, n) и так далее. Очевидно, в стеке не может быть более n пар. В процессе сортировки некоторые части исчерпываются, что ведет к уменьшению числа элементов стека.

Разделяющий элемент массива не обязан оставаться на своем месте. Полезно проверить, что массив 60, 63, 10, 51, 24, 55, 90 после первого разделения примет порядок 24, 51, 10, 63, 60, 55, 90. Значение i будет равно 4, а j станет равным 3. Выделенные части массива определяются границами индексов (1, 3) и (4, 7).

Сортировка Хоара примерно вдвое быстрее пирамидальной сортировки. Среднее число пересылок элементов M в этом методе составляет ln2*(nlog ₂ n)/3.

Приведем данные Вирта, показывающие сравнительную эффективность методов сорировки. Испытания проводились на массиве из 2048 элементов, фиксировалось время в секундах. Элементы массива располагались в трех порядках: по возрастанию значений, в случайном порядке и по убыванию значений. Судя по результатам, была выбрана машина с низким быстродействием, но важны не абсолютные значения затраченного времени, а соотношение приведенных значений для различных методов. Вместе с методами внутренней сортировки указаны характеристики по методу простого слияния, который является типичным представителем внешней сортировки. Для сравнения этого метода с методами внутренней сортировки данные размещались в оперативной памяти. Описание метода простого слияния будет приведено ниже.