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

Идея метода. Пусть есть достаточно быстрый способ переставить элементы массива так, чтобы для некого среднего элемента соблюдалось: левее него все элементы только меньше или равны ему, а правее больше либо равны, тогда этот некий элемент уже занял свою окончательную позицию. Средний элемент исключаем из расмотрения и расматриваем таким же образом элементы стоящие слева и справа от него.

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

Qsort(L,R) – процедура среднего элемента

заведем два счетчика i,j

i:=L;      j:=R;

i будет увеличиваться, а j уменьшаться, при чем в одну интерпретацию изменять только один счетчик. Объявляем активным любой из них, каждый раз сравниваем B[i] и B[j]. Если требуется обмен, то мы его производим и меняем активный элементы и активный счетчик. Процедура завершается когда i=j, то есть и будет средний элемент.

3  2  1  6  5  9  4  7  0  8

i                                    j

3  2  1  6  5  8  4  7  0  9

i                 j

3  2  1  6  5  0  4  7  8  9

i           j

Сложность Хоара пропорциональна n*log(n) по основанию 2

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