При “пузырьковой” сортировке производились обмены ключей (элементов массива) в соседних позициях. При пирамидальных сортировках такой обмен совершался между ключами в позициях, жестко связанных друг с другом соответствующим бинарным деревом. Здесь будет рассмотрен алгоритм профессора вычислительной математики Оксфордского университета в Англии Ч. Хоара, использующий несколько иной механизм выбора значений для обменов. Этот алгоритм называют или сортировкой с разделением, или быстрой сортировкой. В первом случае подчеркивается положенный в его основу метод последовательного дробления массива на части, а во втором - неожиданная эффективность. В подавляющем большинстве реальных случаев использование “быстрой сортировки” дает лучшие временные результаты по сравнению с другими методами. Однако следует иметь в виду, что для нее нет гарантированной трудоемкости типа O(n×log₂(n)) операций сравнений и обменов, где n - количество элементов массива. Более того, в иных ситуациях трудоемкость достигает O(n²) операций и не может быть снижена. Исходя из сказанного, в особо критических ситуациях, где результат должен выдаваться в жестко очерченном интервале времени, применять быструю сортировку следует весьма осмотрительно. По образному выражению Н. Вирта, “… быстрая сортировка напоминает азартную игру, где следует заранее рассчитать, сколько можно позволить себе проиграть в случае невезения” [21, c.102].

Перейдем к сути метода. Пусть одномерный массив задан вектором v = (v₀   v₁  ...  v_n-1) и x - какой-либо компонент v. Сначала обсудим, как обменами элементов достичь разбиения v на две части v1 и v2 так, чтобы в v1 оказались элементы, не превосходящие x, а в v2 - не меньшие x. Сделать это можно с помощью следующего простого и эффективного алгоритма.

Просмотрим v, двигаясь по компонентам слева направо, пока не найдем элемент v_i ³ x. Затем просмотрим v, двигаясь по компонентам справа налево, пока не найдем элемент v_j £ x. Если i £ j, то поменяем местами элементы v_i и v_j и применим описанную процедуру просмотра с обменами к части v от v_i+1 до v_j-1. Продолжая описанный процесс, пока i £ j, получим требуемое разделение исходного массива v. Обратим внимание на следующие обстоятельства. Выбранный для сравнения элемент x служит барьером для двух текущих разнонаправленных просмотров, а простота проверяемых условий оправдывает возможные излишние обмены элементов.

Пример. Пусть в массиве v:

зафиксирован элемент x=14. Просматриваем S слева направо, пока не найдем v_i ³ 14. Получим v₁=23 (i=1). Далее просматриваем v справа налево, пока не найдем v_j£ 14. Получим v₉=7 (j=9). Меняем местами v₁ и v₉. Продолжая этот процесс, придем к последовательности

Теперь можно непосредственно перейти к сортировке v. Нам остается сделать лишь один шаг. После разделения массива v на две части - v1 и v2 - для завершения решения задачи остается отдельно отсортировать v1 и v2. Но сделать это можно, например, рекурсивно продолжая разделение как v1, так и v2.

адача 6. Составить рекурсивную программу-функцию быстрой сортировки массива, заданного вектором v = (v₀   v₁  ...  v_n-1).

Решение. Описанный выше алгоритм реализуется программой quicksort(v). Она обращается к рекурсивной функции quickso(v, s1, s2), построенной в соответствии с ранее описанным алгоритмом, где позиция элемента x для разделения выбирается равной floor((s1+s2)/2). С помощью quickso(v, s1, s2) можно отсортировать массив v на любом участке индексов его элементов от s1 до s2. При обращении к этой функции c фактическими параметрами s1=0 и s2=rows(v)-1 сортировке подвергается весь массив. База рекурсии в quickso() соответствует получению для разделения отрезка массива длины, равной единице, то есть совпадению s1 и s2. Декомпозиция - это и есть процесс разделения текущего отрезка массива.

Контрольный пример:

Подробный анализ быстродействия быстрой сортировки, проведен в [22, с.118]. В соответствии с ним, общее число сравнений при реализации алгоритма в среднем равно n×log₂(n), а общее число обменов - (n×log₂(n))/6. Однако остается разочаровывающая проблема наихудшего случая, и к тому же для небольших значений n эта сортировка “пробуксовывает”, то есть неэффективна. Но ничто не мешает использовать для упорядочивания различные комбинированные способы, например проводить разделение до определенного момента, а затем полученные малые массивы сортировать каким-либо иным способом. Именно так часто и поступают.