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

Одним из наиболее простых и естественных методов внутренней сортировки является сортировка с простыми включениями. Идея алгоритма очень проста. Пусть имеется массив ключей 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^2).

t:integer;

begin

for j:=2 to N do

begin

i := j;

while M[i] < M[i-1] do

begin

t:=M[i];

M[i]:=M[i-1];

M[i-1]:=t;

i := i-1

end

end

end;

2) Сортировка Шелла

Дальнейшим развитием метода сортировки с включениями является сортировка методом Шелла, называемая по-другому сортировкой включениями с уменьшающимся расстоянием.

Идея алгоритма. Сначала в исходной последовательности сортируются между собой элементы, отстоящие друг от друга на расстоянии n/2 элементов, затем на расстоянии n/4 и т.д. до тех пор пока не получим 2 последовательности, элементы которых отстоят друг от друга на расстоянии 1-го элемента. После этого делаем сортировку этой полученной последовательности выбранным методом и на выходе имеем уже полностью отсортированную последовательность.

В качестве самой сортировки элементов в группе можно использовать различные алгоритмы простой сортировки: вставками, выбором, пузырьком и проч.

Пример. Имеется последовательность [2, 3, 9, 2, 8, 4, 6, 8, 11, 12, 4, 6], n=12. Символом d - будем обозначать расстояние между сортируемыми элементами на каждом шаге (на первом шаге d = n/2, на втором d = d/2 и т.д.)

1 шаг. d = n/2 = 6. => Получаем 6 сортируемых групп(имеют одинаковый цвет): [2, 3, 9, 2, 8, 4, 6, 8, 11, 12, 4, 6] После сортировки в пределах каждой группы, имеем: [2, 3, 9, 2, 4, 4, 6, 8, 11, 12, 8, 6]

2 шаг. d = d/2 = 3. => Получаем 3 сортируемых группы(имеют одинаковый цвет): [2, 3, 9, 2, 4, 4, 6, 8, 11, 12, 8, 6] После сортировки в пределах каждой группы, имеем: [2, 3, 4, 2, 4, 6, 6, 8, 9, 12, 8, 11]

3 шаг. d = d/2 = 1(целочисленное деление) => заключительный шаг. Сортируем всю последовательность: [2, 3, 4, 2, 4, 6, 6, 8, 9, 12, 8, 11] в итоге получим:[2, 2, 3, 4, 4, 6, 6, 8, 8, 9, 11, 12]

При этом производительность алгоритма пропорциональна - О(n^2), но количество перестановок по сравнению с простыми методами вставкой, выбором или пузырьком - заметно сокращается. Дополнительная память - не используется (не считая счетчиков циклов и проч.). (Сложность алгоритма: O(n log n))