Альтернативные методы сортировки
Цель рассмотреть ещё несколько методов сортировки.
Оболочечная Сортировка (Сортировка включениями с убывающем приращением).
Сортировка вставкой работает медленно потому, что она обменивает только смежные элементы. Оболочечная сортировка является простейшим расширением сортировки вставкой которая увеличивает скорость работы алгоритма за счет того, что позволяет обменивать элементы находящиеся далеко друг от друга.
Основной идеей алгоритма является отсортировать все группы файла состоящие из элементов файла отстоящих друг от друга на расстояние h. Такие файлы называются h- сортированными. Когда мы h-сортируем файл по некоторому большому h, мы передвигаем его элементы на большие растояния. Это облегчает работу сортировки для меньших значений h. Процесс заканчивается когда h уменьшается до 1.
procedure Sort;
var i,j,z,k:word;
v:integer;
begin
z:=1;
k:=3;
repeat
z:=z*k+1;
until z>n;
repeat
z:=z div k;
for i:=z+1 to n do
begin
j:=i;
while
(j>z) and (a[j-z]>a[j])
do
begin
v:=a[j];
a[j]:=a[j-z];
j:=j-z;
a[j]:=v;
end;
end;
Until z=1;
end;
Пример:
31 59 54 39 22 83 80 2 6 60
22 59 54 39 31 83 80 2 6 60
22 59 54 2 31 83 80 39 6 60
22 59 54 2 6 83 80 39 31 60
6 59 54 2 22 83 80 39 31 60
6 59 54 2 22 60 80 39 31 83
6 54 59 2 22 60 80 39 31 83
6 54 2 59 22 60 80 39 31 83
6 2 54 59 22 60 80 39 31 83
2 6 54 59 22 60 80 39 31 83
2 6 54 22 59 60 80 39 31 83
2 6 22 54 59 60 80 39 31 83
2 6 22 54 59 60 39 80 31 83
2 6 22 54 59 39 60 80 31 83
2 6 22 54 39 59 60 80 31 83
2 6 22 39 54 59 60 80 31 83
2 6 22 39 54 59 60 31 80 83
2 6 22 39 54 59 31 60 80 83
2 6 22 39 54 31 59 60 80 83
2 6 22 39 31 54 59 60 80 83
2 6 22 31 39 54 59 60 80 83
2 6 22 31 39 54 59 60 80 83
Здесь показано, как оболочечная сортировка обрабатывает файл с шагом в ..., 1093, 364, 121, 40, 13, 4, 1. Могут существовать и другие последовательности - одни лучше, другие хуже.
Свойство 1. Оболочечная сортировка никогда не делает более чем N1.5 сравнений для вышеуказанной последовательности h.
Сортировка подсчетом распределений.
Если известно интервал изменения значений в последовательности и значения часто повторяются, то применим алгоритм сортировки подсчетом распределений.
procedure count1;{a:[7 8 2 9 3 1 5 8 3 3]}
var
i,j: integer;
begin
for j:=0 to M-1 do
count[j]:=0;
for i:=1 to N do
inc(count[a[i]] ); {count:[0 1 1 3
0 1 0 1 2 1
0]);
for j:=0 to M-1 do
count[j]:=count[j-1]+count[j];
{count:[ 0 1 2 5 5
6 6 7 9 10 10]}
for i:=N downto 1 do
begin
b
[count[a[i]]] := a[i];
dec
(count[a[i]]);
end;
a := b; {a:[1 2 3 3 3 5 7 8 8 9]}
end;
Сортировка радикс обменом.
"Ключи" используемые для определения порядка следования записей в файлах во многих задачах сортировки могут быть очень сложные. (Например, представьте себе функцию используемую в телефонном справочнике или библиотечном каталоге.) Поэтому, вполне естественным считается определять методы сортировки в терминах базисных операций "сравнения" двух ключей и "обмены" двух записей. Большинство из методов, которые мы до сих пор изучили, могут быть описаны при помощи этих операций. Однако, во многих задачах можно воспользоваться тем, что ключи могут быть представлены как числа находящиеся в некотором диапазоне. Методы сортировки, которые используют числовые свойства ключей, называются методами радикс сортировки. Такие методы не просто сравнивают ключи: они обрабатывают и сравнивают ключи по частям.
Радикс сортирующие алгоритмы работают с ключами как с числами некоторого основания М, используя их отдельные цифры. К примеру, представьте себе клерка, который должен отсортировать карточки согласно номеру находящемуся в диапазоне от 000 до 999. Один из способов это сделать - это разложить их в 10 кучек: в одну кучку все карточки с номерами меньшими 100, в другую с номерами от 100 до 199 и т.д. После этого операцию повторить для каждой из кучек пока кучка не станет достаточно мала чтобы ее упорядочить. Этот простой пример демонстрирует радикс сортировку для М = 10. Для компьютера более удобным представляется использовать радикс М = 2 (или степени 2) вместо 10.
Все что хранится в памяти компьютера можно представить как бинарное число, поэтому многие приложения могут быть изменены так, чтобы использовались как бинарные числа.
Мы будем считать, что ключи достаточно длины, и стоят того, чтобы дробить их в более мелкие. Этот метод основывается на том факте, что цифры всегда идут по порядку: 0 всегда предшествует 1, и т.д. Такой метод называется сортировка радикс обменом.
Пусть у нас есть способ упорядочить файл по i-му биту так, что сперва идут все ключи в которых этот бит равен 0, а потом все в которых он 1. Это немедленно порождает рекурсивный сортировочный механизм: отсортировать сперва по старшему биту, потом образовавшиеся два подфайла отсортировать независимо друг от друга по следующему биту и т.д.
Сортировка файла по определенному биту очень схожа с процедурой деления в алгоритме быстрой сортировки: найдем 1 слева, 0 справа, обменяем, и повторяем до тех пор, пока указатели сканирования не пересекутся. Это приводит к процедуре сортировки, очень схожей с быстрой сортировкой:
Procedure radixexchange (Left, Right:
word; bitnum :
shortint);
Var
Temp : word;
Index1, Index2 : word;
Begin
If (Right > Left) and ( bitnum >= 0) then
Begin
Index1 := Left;
Index2 := Right;
Repeat
While (((a[Index1] shr bitnum) AND 1) = 0) and (Index1 < Index2)
do
Inc(Index1);
While (((a[Index2] shr bitnum) AND 1) = 1) and (Index1 < Index2)
do
Dec(Index2);
Temp := a[Index1];
A[Index1] := a[Index2];
A[Index2] := Temp
Until (Index2 = Index1);
If (((a[Right] shr bitnum) AND 1) = 0) then
Inc(Index2);
Radixexchange(Left, pred(Index2), pred(bitnum));
Radixexchange(Index2, Right, pred(bitnum))
End
End;
Итак, на сегодняшнем занятии мы рассмотрели ещё несколько методов сортировки.
