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

Рассмотрим усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех трех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных до сего времени методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал алгоритм быстрой сортировкой [1,3, 9, 10, 13].

Сортировка основана на том факте, что для достижения наибольшей эффективности желательно производить обмен чисел на больших расстояниях. В массиве выбирается некоторый элемент, называемый разрешающим. Затем он помещается в то место массива, где ему полагается быть после упорядочивания всех элементов. В процессе отыскания подходящего места для разрешающего элемента производятся перестановки элементов так, что слева от него находятся элементы, меньшие разрешающего, а справа — большие (предполагается, что массив сортируется по возрастанию). Тем самым массив разбивается на две части: не отсортированные элементы слева от разрешающего элемента и не отсортированные элементы справа от него. Чтобы отсортировать эти два меньших подмассива, алгоритм вызывает сам себя.

Запишем алгоритм: если надо сортировать больше одного элемента, то выбрать в массиве разрешающий элемент;

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

Ключевым элементом быстрой сортировки является алгоритм переупорядочения. Для его реализации используем указатель left на крайний левый элемент массива. Указатель движется вправо, пока элементы, на которые он показывает, остаются меньше разрешающего. Указатель right поставим на крайний правый элемент списка и движется влево, пока элементы, на которые он показывает, остаются больше разрешающего. Движение указателей останавливается, как только встречаются элементы, порядок расположения которых относительно разрешающего неправильный. Эти числа меняются местами и движение указателей возобновляется. Процесс продолжается до тех пор, пока right не окажется слева от left. Тем самым будет определено правильное место разрешающего элемента.

Рассмотрим сортировку на примере массива:

10,4,2,14,67,2,11,33,1,15. Пусть крайний левый элемент — разрешающий. Установим left на следующий за ним элемент; right — на последний (рис. 3.15).

Рис. 3.15

Теперь алгоритм должен определить правильное положение элемента 10 и по ходу дела поменять местами неправильно расположенные элементы. Указатель left перемещается до тех пор, пока не покажет элемент больше 10; right движется, пока не покажет элемент меньше 10. Эти элементы меняются местами (рис. 3.16).

Рис. 3.16. Массив после первого шага сортировки

Левый и правый элементы меняются местами; встречное же движение указателей продолжается (рис. 3.17).

Рис. 3.17

Следующий шаг сортировки элементов показан на рис. 3.18.

Рис. 3.18

Перестановка элементов показана на рис. 3.19.

Рис. 3.19

После очередного шага указатели перейдут друг через друга. Это значит, что найдено положение разрешающего элемента (рис. 3.20).

Рис. 3.20

Осуществляется перестановка разрешающего элемента с элементом, на который указывает right (рис. 3.21).

Рис. 3.21

Разрешающий элемент находится в нужном месте: элементы слева от него имеют меньшие значения; справа — большие. Алгоритм рекурсивно вызывается для сортировки элементов слева от разрешающего и справа от него.