Обменная сортировка

Сортировка включением

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей a[1], a[2],..., a[n]. Для каждого элемента массива, начиная со второго, производится сравнение с элементами с меньшим индексом (элемент a[i] последовательно сравнивается с элементами a[i-1], a[i-2]...) и до тех пор, пока для очередного элемента слева a[j] выполняется соотношение a[j] > a[i], a[i] и a[j] меняются местами. Если удается встретить такой элемент a[j], что a[j] <= a[i], или если достигнута нижняя граница массива, производится переход к обработке элемента a[i+1] (пока не будет достигнута верхняя граница массива).

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

Можно сократить число сравнений, применяемых в методе простых включений, если воспользоваться тем фактом, что при обработке элемента a[i] массива элементы a[1], a[2],..., a[i-1] уже упорядочены, и воспользоваться для поиска элемента, с которым должна быть произведена перестановка, методом двоичного деления. В этом случае оценка числа требуемых сравнений становится O(n log n). Заметим, что поскольку при выполнении перестановки требуется сдвижка на один элемент нескольких элементов, то оценка числа пересылок остается O(n²).

Таблица 3.1 Пример сортировки методом простого включения

Начальное состояние массива	8 23 5 65 44 33 1 6
Шаг 1	8 23 5 65 44 33 1 6
Шаг 2	8 5 23 65 44 33 1 65 8 23 65 44 33 1 6
Шаг 3	5 8 23 65 44 33 1 6
Шаг 4	5 8 23 44 65 33 1 6
Шаг 5	5 8 23 44 33 65 1 65 8 23 33 44 65 1 6
Шаг 6	5 8 23 33 44 1 65 65 8 23 33 1 44 65 65 8 23 1 33 44 65 65 8 1 23 33 44 65 65 1 8 23 33 44 65 61 5 8 23 33 44 65 6
Шаг 7	1 5 8 23 33 44 6 651 5 8 23 33 6 44 651 5 8 23 6 33 44 651 5 8 6 23 33 44 651 5 6 8 23 33 44 65

В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать a[i], т. е. a[i] сравнивается с очередным элементом a[j], а затем либо a[i] вставляется на свободное место, либо a[j] сдвигается (передается) вправо и процесс «уходит» влево. Обратите внимание, что процесс просеивания может закончиться при выполнении одного из двух следующих различных условий:

1. Найден элемент a[j] с ключом, меньшим чем ключ у a[i].

2. Достигнут левый конец готовой последовательности.

FOR i:=2 TO N DO BEGIN

x:=a[i]; j:=i;

WHILE (a[j-1] > x) AND (j > 1) DO BEGIN

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

j:=j-1

END;

a[j]:=x;

END;

Простая обменная сортировка (в просторечии называемая "методом пузырька") для массива a[1], a[2],..., a[n] работает следующим образом. Начиная с конца массива сравниваются два соседних элемента (a[n] и a[n-1]). Если выполняется условие a[n-1] > a[n], то значения элементов меняются местами. Процесс продолжается для a[n-1] и a[n-2] и т.д., пока не будет произведено сравнение a[2] и a[1]. Понятно, что после этого на месте a[1] окажется элемент массива с наименьшим значением. На втором шаге процесс повторяется, но последними сравниваются a[3] и a[2]. И так далее. На последнем шаге будут сравниваться только текущие значения a[n] и a[n-1]. Понятна аналогия с пузырьком, поскольку наименьшие элементы (самые "легкие") постепенно "всплывают" к верхней границе массива. Пример сортировки методом пузырька показан в таблице 2.3.

Таблица 1.3. Пример сортировки методом пузырька

Начальное состояние массива	8 23 5 65 44 33 1 6
Шаг 1	8 23 5 65 44 33 1 68 23 5 65 44 1 33 68 23 5 65 1 44 33 68 23 5 1 65 44 33 68 23 1 5 65 44 33 68 1 23 5 65 44 33 61 8 23 5 65 44 33 6
Шаг 2	1 8 23 5 65 44 6 331 8 23 5 65 6 44 331 8 23 5 6 65 44 331 8 23 5 6 65 44 331 8 5 23 6 65 44 331 5 8 23 6 65 44 33
Шаг 3	1 5 8 23 6 65 33 441 5 8 23 6 33 65 441 5 8 23 6 33 65 441 5 8 6 23 33 65 441 5 6 8 23 33 65 44
Шаг 4	1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Шаг 5	1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Шаг 6	1 5 6 8 23 33 44 65 1 5 6 8 23 33 44 65
Шаг 7	1 5 6 8 23 33 44 65

Для метода простой обменной сортировки требуется число сравнений n(n-1)/2, минимальное число пересылок 0, а среднее и максимальное число пересылок - O(n²).

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

i:=0;

REPEAT

fl:=TRUE; i:=i+1;

FOR j:=1 TO n-i DO

IF a[j] > a[j+1] THEN BEGIN

fl:=FALSE; x:=a[j];

a[j]:=a[j+1]; a[j+1]:=x

END;

UNTIL fl;

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

Таблица 1.4. Пример шейкерной сортировки

Начальное состояние массива	8 23 5 65 44 33 1 6
Шаг 1	8 23 5 65 44 33 1 68 23 5 65 44 1 33 68 23 5 65 1 44 33 68 23 5 1 65 44 33 68 23 1 5 65 44 33 68 1 23 5 65 44 33 61 8 23 5 65 44 33 6
Шаг 2	1 8 23 5 65 44 33 61 8 5 23 65 44 33 61 8 5 23 65 44 33 61 8 5 23 44 65 33 61 8 5 23 44 33 65 61 8 5 23 44 33 6 65
Шаг 3	1 8 5 23 44 6 33 651 8 5 23 6 44 33 651 8 5 6 23 44 33 651 8 5 6 23 44 33 651 5 8 6 23 44 33 65
Шаг 4	1 5 6 8 23 44 33 651 5 6 8 23 44 33 651 5 6 8 23 44 33 651 5 6 8 23 33 44 65
Шаг 5	1 5 6 8 23 33 44 651 5 6 8 23 33 44 651 5 6 8 23 33 44 65

{шейкер-сортировка по убыванию}

L:=2; R:=n; k:=n;

REPEAT

FOR j:=R DOWNTO L DO

IF a[j-1] < a[j] THEN BEGIN

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

END;

L:=k+1;

FOR j:=L TO R DO

IF a[j-1] < a[j] THEN BEGIN

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

END;

R:=k-1;

UNTIL L>R;

Шейкерная сортировка позволяет сократить число сравнений (по оценке Кнута средним числом сравнений является (n² - n(const + ln n)), хотя порядком оценки по-прежнему остается n². Число же пересылок, вообще говоря, не меняется. Шейкерную сортировку рекомендуется использовать в тех случаях, когда известно, что массив "почти упорядочен".

Дата добавления: 2014-01-13