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

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

... 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;

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

var i, j, k: integer;

x, b: typel;

Begin

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

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 (n log ₂ n), не более чем n /2 перемещений.

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

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

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

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

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

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

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

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

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

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