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

(обменная сортировка с разделением)

Это улучшенный метод, основанный на принципе обмена. Неожиданно оказалось, что усовершенствованный «пузырёк» даёт лучший результат из всех известных до настоящего времени методов сортировки. Он обладает столь блестящими характеристиками, что его изобретатель Хоар окрестил его “быстрой сортировкой”, QuickSort (1962г.).

В методе Бетчера последовательность сравнений предопределена; она не зависит от фактического состояния файла (т.е. от того, насколько он уже упорядочен). Разумно предположить, что метод сортировки будет эффективнее, если последовательность сравнений элементов зависит от результатов предыдущих сравнений (т.е. будет учитываться состояние файла).

Q-sort основана на том факте, что для достижения наибольшей эффективности желательно производить обмены элементов на больших расстояниях.

Алгоритм.

массив

i=1 → ← j=N

Пусть имеются два указателя i и j. Причём вначале: i=1, j=N.

Сравним k i и k j (k i: k j).

Если обмен не нужен, то уменьшаем j на 1 и повторяем этот процесс.

После первого обмена увеличим i на 1 и будем продолжать сравнения, увеличивая i, пока не произойдёт ещё один обмен, тогда уменьшим j и т.д., пока не станет i=j. К этому моменту запись Ri(Rj) займёт свою окончательную позицию, и исходный файл будет разделён на два подфайла:

(R₁,…R_{i -1})R_i(R_i+1,…,R_n).

Эти подфайлы надо сортировать независимо (тем же методом).

В процессе сортировки образуется множество подфайлов, которые можно сортировать параллельно, независимо друг от друга.

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

Каждый из подфайлов сортируют методом Q-sort за исключением очень коротких.

Поиск по сайту: