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

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

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

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

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). При его применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге «всплывает» очередной наиболее легкий элемент, а на другом «тонет» очередной самый тяжелый.

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

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 ² . Число же пересылок, вообще говоря, не меняется. Шейкерную сортировку рекомендуется использовать в тех случаях, когда известно, что массив «почти упорядочен».