Продолжение предыдущей статьи...
Рекурсивные алгоритмы и улучшение известных нам из предыдущей статьи.
Быстрая сортировка
Теперь коснемся третьего улучшения метода, основанного на обмене. Если учесть, что пузырьковая сортировка в среднем была самой неэффективной из всех трех алгоритмов прямой сортировки, то следует ожидать относительно существенного улучшения. Оно, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Его изобретатель Ч. Хоар назвал метод быстрой сортировкой (QuickSort).
Алгоритм. Выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент , затем будем просматривать массив справа, пока не встретим . Теперь Поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена , пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую – с ключами больше (или равными) x.
