4. Сортировка прямым обменом

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

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

Проход метода начинается с конца сортируемого массива. Ключ последнего элемента a[HighIndex] сравнивается с ключом предпоследнего элемента a[HighIndex-1]. Если

a[HighIndex].Key < a[HighIndex-1].Key,

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

Алгоритм пузырьковой сортировки иллюстрируется результатами выполнения проходов на тех же, что и ранее, ключах:

Простейшей реализацией пузырьковой сортировки является подпрограмма BubbleSort, показанная ниже:

Рrocedure BubbleSort;

Var i, j: Integer;

x: TElement;

flag: boolean;

Вegin

For i:= 1 To HighIndex Do Begin

// Начало прохода

flag:= True;

For j:= HighIndex DownTo i Do

If a[j-1].Key > a[j].Key Then Begin

flag:= False;

x:=a[j-1];

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

a[j]:=x

end;

// Если обменов не было, то закончить

If flag Then Break;

End;

End;

В подпрограмме BubbleSort используется булева переменная flag, которая устанавливается в True в начале каждого прохода. Если при выполнении очередного прохода не было выполнено ни одного обмена, это означает, что массив a упорядочен. В этом случае переменная flag не изменяет своего значения и происходит выход из подпрограммы BubbleSort.

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

12, 18, 42, 44, 55, 67, 94, 06

будет рассортирован при помощи метода пузырька за один проход, а сортировка массива

94, 06, 12, 18, 42, 44, 55, 67

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

Из рисунка видно, что в результате первого прохода наверх переместился самый «легкий» ключ 06. А самый «тяжелый элемент», имеющий ключ 94, переместился на свое место уже на втором проходе, чего не наблюдалось при рассмотрении пузырьковой сортировки.

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

Можно показать, что среднее расстояние, на которое должен переместиться каждый из N элементов во время сортировки,  это N/3 мест. Это число дает ключ к поиску усовершенствованных, т. е. более эффективных, методов сортировки. Все простые методы в принципе перемещают каждый элемент на одну позицию на каждом элементарном шаге. Поэтому они требуют порядка N² таких шагов. Любое улучшение должно основываться на принципе пересылки элементов за один шаг на большое расстояние.

Текст подпрограммы шейкерной сортировки приводится ниже.

Procedure ShakerSort;

Var j, k ,L ,R: Integer;

x: TElement;

flag: boolean;

Begin

L:=1; R:= HighIndex; k:= R;

Repeat

flag:= true;

For j:=R DownTo L Do Begin

If a[j-1].Key > a[j].Key Then Begin

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

k:=j; flag:= false;

end;

End;

If flag Then Break;

L:=k+1;

flag:= True;

For j:=L To R Do

If a[j-1].Key > a[j].Key Then Begin

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

k:=j; flag:= false;

end;

If flag Then Break;

R:=k-1;

Until L > R

End;