Сортировки массивов. Сортировка прямыми (простыми) вставками с барьером
Задача сортировки
Задача сорт заключаются в упорядочении элементов массива.
В основе быстрой сортировки лежит принцип разбиения. Сначала выбирается
Для того чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент (сравните строки {*} и {**} в приведенных вариантах программы). В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как "барьер", не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х:
for i:= 2 to N do
if a[i-1]>a[i] then
begin a[0]:= a[i]; {*}
j:= i-1;
while a[j]>a[0] do {**}
begin a[j+1]:= a[j];
j:= j-1;
end;
a[j+1]:= a[0];
end;
Эффективность алгоритма ПрВстБар
Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.
В худшем же случае - когда входная последовательность упорядочена "наоборот" - сравнений будет уже (N+1)*N/2, а пересылок (N-1)*(N+3). Таким образом, этот алгоритм имеет сложность ~N2 (читается "порядка эн квадрат") по обоим параметрам.
Пример сортировки
Предположим, что нужно отсортировать следующий набор чисел:
5 3 4 3 6 2 1
Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):
Состояние массива Сдвиги Сравнения Пересылки данных
0 шаг: 5343621
1 шаг: 5343621 1 1+13) 1+24)
2 шаг: 3543621 1 1+1 1+2
3 шаг: 3453621 2 2+1 2+2
4 шаг: 3345621 0 1 0
5 шаг: 3345621 5 5+1 5+2
6 шаг: 2334561 6 6+1 6+2
Результат: 1233456 15 20 25
Сортировка массивов. Пирамидальная сортировка.
Задача сортировки
Задача сорт заключаются в упорядочении элементов массива.
Попытаемся теперь усовершенствовать другой рассмотренный выше простой алгоритм: сортировку простым выбором ПрВыб.
Р. Флойд предложил перестроить линейный массив в пирамиду - своеобразное бинарное дерево, - а затем искать минимум только среди тех элементов, которые находятся непосредственно "под" текущим вставляемым.
Просеивание
Для начала необходимо перестроить исходный массив так, чтобы он превратился в пирамиду, где каждый элемент "опирается" на два меньших. Этот процесс назвали просеиванием, потому что он очень напоминает процесс разделения некоторой смеси (камней, монет, т.п.) на фракции в соответствии с размерам частиц: на нескольких грохотах11) последовательно задерживаются сначала крупные, а затем все более мелкие частицы.
Итак, будем рассматривать наш линейный массив как пирамидальную структуру:
| a[1] | |||||
| a[2] | a[3] | ||||
| a[4] | a[5] | a[6] | a[7] | ||
| a[8] | a[9] | a[10] | a[11] | a[12] | |
Видно, что любой элемент a[i] (1<=i<=N div 2) "опирается" на элементы a[2*i] и a[2*i+1]. И в каждой такой тройке максимальный элемент должен находится "сверху". Конечно, исходный массив может и не удовлетворять этому свойству, поэтому его потребуется немного перестроить.
Начнем процесс просеивания "снизу". Половина элементов (с ((N div 2)+1)-го по N-й) являются основанием пирамиды, их просеивать не нужно. А для всех остальных элементов (двигаясь от конца массива к началу) мы будем проверять тройки a[i], a[2*i] и a[2*i+1] и перемещать максимум "наверх" - в элемент a[i].
При этом, если в результате одного перемещения нарушается пирамидальность в другой (ниже лежащей) тройке элементов, там снова необходимо "навести порядок" - и так до самого "низа" пирамиды:
for i:= (N div 2)downto 1 do
begin j:= i;
while j<=(N div 2) do
begin k:= 2*j;
if (k+1<=N) and (a[k]<a[k+1])
then k:= k+1;
if a[k]>a[j]
then begin x:= a[j];
a[j]:= a[k];
a[k]:= x;
j:= k
end
else break
end
end;