2. Улучшенные алгоритмы сортировки

2.1. Алгоритм Шелла

В 1959 году Шелл предложил новый алгоритм сортировки. Он является усложнением алгоритма включения. Согласно этому сортировка строится как пошаговый алгоритм. На каждом шаге рассматриваются и сортируются элементы отстоящие друг от друга на расстоянии n.

Пусть k– номер шага,n_k– расстояние между сортируемыми элементами:

n_k, n_k-1, . . . , 1

На последнем этапе сортируется весь массив. Например:

2 10 12 5 1 6 9 4 шаг сравнения

2 9 1 5 6 10 12 2 шаг сравнения

1 5 2 9 6 10 12 1 шаг сравнения

1 2 5 6 9 10 12

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

T_n = n^1,2

O(n^1,2)

Нельзя внутри этого алгоритма использовать алгоритмы, не реагирующие на предварительную отсортированность (Ведь к исходному добавлены еще 5 массивов). Стандартно используется алгоритм включениями.

Для эффктивности алгоритма Шелла шаги не должны быть кратными. Хорошая последовательность шагов: 1, 4, 13, 40, 121…

2.2. Быстрая сортировка Хоара

Недостатком метода «пузырька» является то, что элементы переставляются на очень маленькое расстояние. Более мощным является алгоритм Хоара. Он позволяет перекинуть элементы на большее расстояние. Это улучшенный алгоритм обменной сортировки.

. . . a_i . . .x . . . a_j . . .

обмен

a₁, a₂, … a_k–1, a_k, a_k+1, a_n–1, a_n

i j

a_i > a_k a_j < a_k

В результате первого просмотра выбираем центральный элемент и обозначим его x. В левой части ищем элементы большеx, а в правой – меньше. Затем левая и правая половинки тоже делятся пополам и процесс повторяется вновь для каждой половинки. Процесс будет продолжаться до тех пор, покаi>j. Это рекурсивный алгоритм, в основе которого лежит разделение.

Выбираем x:=a[k]

i:= 1; j:= n;

repeat

while a_i < x do inc(i);

while a_j > x do dec(j);

if i <= j then

begin

b:= a[i]; a[i]:= a[j]; a[j]:= b;

inc(i);

dec(j);

end;

until i > j;

Потом этот алгоритм применяется отдельно к левой и правой части и получаем рекурсивный алгоритм.

Алгоритм:

procedure QuickSort;

procedureSort(l,r:integer); {l,r– левая и правая границы помассива}

var i, j, k: integer;

x, b: typel;

begin

k:= (l+r)div2; { полусумма границы}

x:= a[k];i:= l;j:= r; {поi–слева, поj– справа}

repeat{т.к. многократно}

while a[i] < x do i:= i+1;

while a[j] > x do j:= j+1;

if i <= j then

begin b:= a[i]; a[i]:= a[j];

a[j]:= b; i:=i + 1; j:=j – 1;

end;

until i > j;

if i < r then Sort (i, r);

* if j > l then Sort (l, j);

end;

begin Sort (1, n)

end.

Если a_kоказался максимальным, он перейдет до конца вправо, то будет существовать только левый массив и выполняться только условие *.

Оценка алгоритма: На каждом шаге мы всегда просматриваем i-элементов, а значит иn-операций. В качестве элементаa_k(x) нам удается выбирать элемент, который занимает среднее значение из всех элементов массива.

Предположим, что a_k– медиана – это элемент массива, который обладает следующим свойством:

• количество элементов больше и меньше медианы на 1 (элементы большие и меньшие a_kотличаются на единицу).

• при делении элемент не перемещается (этот средний элемент при проверке никуда не перемещается – он посередине).

На каждом шаге уменьшаем размерность задачи в два раза. В этом случае число шагов (n) дляa_kмедианы имеет:T_n=O(nlog₂ n), не более чемn/2 перемещений.

log₂ n– оценка разбивания массива (дихотомия)

Оценка алгоритма: T_n=O(nlog₂ n)

Во всех случаях мы имеем оценку nlog₂n.

Теоретические исследования показали, что во всех случаях простой случай поиска a_kявляется верным и удобным.

Но существует другая ситуация, которая изменяет оценку алгоритма (minиmax) то оценка:n².

Можно вставить алгоритм поиска медианы, тогда оценка будет alog₂ n, гдеa– коэффициент. Число шагов не изменится. Но нет необходимости искать медиану, т.к. и этот алгоритм имеет хорошую оценку.

Если a_kвзять как максимальное (минимальное), то оценка превращается вn².

Алгоритм n^1,2(алг. Шелла) иn²– они логически сложны. На практике алгоритм с оценкойn²дает лучший результат.

Таким образом самым лучшим из простых является метод простого выбора. Наихудшим алгоритмом является метод простого обмена.

Лучшим из улучшенных простых является метод быстрой сортировки, основанный на рекурсии.