Procedure Sift;
End;
Begin
End;
Begin
Repeat
Begin
End
End
Begin
Begin
Begin
End
Begin
Begin
End;
End;
Begin
Begin
Begin
End;
Begin
Begin
For i:=2 To n Do
x:=a[i];r:=a[i]; a[0]:=x; j:=i;
While x<a[j-1] Do
Begin a[j]:=a[j-1]; j:=j-1; end;
a[j]:=r
End;{Straight_Insertion}{сортировка прямым включением}
Сортировка бинарными включениями.
Алгоритм сортировки прямыми включениями можно легко улучшить, пользуясь тем, что готовая последовательность a[1],...,a[i-1], в которую нужно включить новый элемент, уже упорядочена. Поэтому место включения можно найти значительно быстрее, применив бинарный поиск, который исследует средний элемент готовой последовательности и продолжает деление пополам, пока не будет найдено место включения. Модифицированный алгоритм сортировки называется сортировкой бинарными включениями.
Procedure Binary_Insertion(n:word;Var a: array[1..100] of integer);
Var i,j,l,r,m:word;
x:integer;
For i:=2 To n Do
x:=a[i]; l:=1; r:=i-1;
While l<=r Do
m:=(l+r) div 2;
If x < a[m] Then r:=m-1
Else l:=m+1
For j:=i-1 DownTo l Do a[j+1]:=a[j];
a[l]:=x
End;{Binary_Insertion}{сортировка бинарным вкючением}
Сортировка выбором
Прямой выбор.
Для i=1..n-1 выполняется следующий элементарный алгоритм: среди элементов ai..n выбираем минимальный am и переставляем местами элементы i-й и m-й. В результате на первое место станет самый минимальный, на второе – следующий минимальный и т.д.
Procedure Straight_Selection(n:word;Var a array[1..100] of integer);
Var i,j,k:word;
x:integer;
For i:=1 To n-1 Do
m:=i;
For j:=i+1 To n Do
If a[m] > a[j] Then m:=j;
x:=a[i]; a[i]:=a[m]; a[m]:=x
End;{Straight_Selection} {сортировка простым выбором}
Обменные сортировки
Сортировка прямого обмена (пузырьковая).
Это метод, в котором обмен двух элементов является основной характеристикой процесса. Алгоритм сортировки простым обменом основан на принципе сравнения и обмена пары соседних элементов до тех пор, пока не будут рассортированы все элементы. Для i=1..n-1 выполняется следующий элементарный алгоритм: начиная от n до i последовательно проверяем упорядоченность двух соседних элементов a[j] и a[j-1], и если они не упорядочены, то меняем их местами. В результате такого обмена минимальный элемент перемещается на место i.
Критерием окончания является отсутствие обменов при очередном проходе.
Во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур - количество элементов массива (n), на выходе - упорядоченный массив элементов (а).
Procedure Bubble_Sort(n:word;Var a: array[1..100] of integer);
Var i,j:word;
x:integer;
For i:=1 To n-1 Do
For j:=n DownTo i Do
If a[j-1]>a[j] Then
x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x
End;{Bubble_Sort}
Шейкерная сортировка.
Улучшение алгоритма - это запоминать, производится ли на данном проходе какой-либо обмен. Если нет, то это означает, что алгоритм может закончить работу. Этот процесс улучшения можно продолжить, если запомнить не только сам факт обмена, но и место (индекс) последнего обмена.
Однако внимательный программист заметит здесь странную асимметрию: один неправильно расположенный "пузырек" в "тяжелом" конце рассортированного массива всплывет на место за один проход, а неправильно расположенный элемент в "легком" конце будет опускаться на правильное место только на один шаг на каждом проходе. Изменение направления сортировки в каждом из проходов алгоритма поиска называют шейкерной сортировкой.
Для того чтобы тяжелые элементы сразу попадали вниз, пузырьковую сортировку выполняют так, чтобы направление прохода было снизу вверх, следующий проход - сверху вниз и так далее.
Procedure Shaker_Sort(n:word;Var a:array [1..100] of integer);
Var j,k,l,r:word;
x:integer;
l:=2; r:=n; k:=n;
For j:=r DownTo l Do {проход снизу-вверх}
If a[j-1]>a[j] Then
x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j;
l:=k+1;
For j:=l To r Do {проход cверху-вниз}
If a[j-1]>a[j] Then
x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x; k:=j;
r:=k-1;
Until l>r
End;{Shaker_Sort}
Пирамидальная сортировка.
Предположим, что дана пирамида с элементами hl+1, ..., hr для некоторых значений l и r и нужно добавить новый элемент x для того, чтобы сформировать расширенную пирамиду hl, ..., hr. Новый элемент x сначала помещается в вершину дерева, а затем “просеивается” по пути, на котором находятся меньшие по сравнению с ним элементы, которые одновременно поднимаются вверх; таким образом, формируется новая пирамида.
В процедуре Heap_Sort вызывается процедура Sift, которая реализует алгоритм формирования пирамиды.
Procedure Heap_Sort(n:word;Var a: array [1..100] of integer);
Var l,r:word;x:integer;