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

Метод был предложен английским программистом Хоором. Он использует тот факт, что число перестановок в массиве может резко сократиться, если менять местами элементы, находящиеся на большом расстоянии. Алгоритм является разновидностью «пузырьковой» сортировки и реализует метод «разделяй и властвуй». Для этого обычно в середине массива выбирается один элемент (опорный). Далее слева от опорного располагают все элементы, меньше его, а справа – больше. Затем тот же прием применяют к половинкам массива. Процесс заканчивается, когда в частях массива останется по одному элементу.

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

Таким образом, когда процессы встречаются, любой элемент в первой части меньше любого во второй. Это значит, что их уже сравнивать друг с другом не придется. Остается только провести такую же операцию по отношению к полученным половинам, и так далее, пока в очередной части массива не останется один элемент. Это будет означать, что массив отсортирован. Очевидно, что наиболее удобный способ реализации рассмотренного метода – рекурсивный.

Общий алгоритм можно представить так.

1. Из массива выбирается некоторый опорный элемент, например,

Опорный = a[n/2].

2. Запускается процедура разделения массива, которая перемещает все элементы, меньшие, либо равные Опорному, влево от него, а все, большие, или равные Опорному, - вправо.

3. Теперь массив состоит из двух подмассивов, причем длина левого меньше, либо равна длине правого.

4. Для обоих подмассивов, если в них больше двух элементов, рекурсивно заполняется та же процедура.

В конце получится полностью отсортированная последовательность.

Уточненный рекурсивный алгоритм процедуры быстрой сортировки

Исходные данные: Массив А; Левая_граница (0); Правая_граница (n-1)

1. Индекс в начале, i = Левая_граница.

2. Индекс в конце, j =Правая_граница.

3. Опорный = A[(Левая_граница + Правая_граница) / 2].

4. Повторять

4.1. Движение слева направо:

Пока A[i] < Опорный

i = i + 1

4.2. Движение справа налево:

Пока A[j] > Опорный

j = j - 1.

4.3. Поменять местами A[i] и A[j].

4.4. i = i + 1.

4.5. j = j - 1.

Пока Левая_граница < Правая_граница.

5. Если Левая_граница < j, то отсортировать А от Левая_граница до j,

6. Если i > Правая_граница, то отсортировать А от i до Правая_граница.

7. Вывести массив А.

Сложность алгоритма зависит от выбора опорного элемента. Наилучшим считается значение так называемой медианы. Это – элемент, который меньше или равен половине элементов массива и больше или равен другой половине. Нахождение такого элемента требует выполнения дополнительных операций.

Число сравнений и пересылок при реализации быстрой сортировки в худшем случае пропорционально n², т.е. его временная сложность равна О(n²), а в среднем и лучшем - О(n log n). Вообще рассмотренный метод является одним из наиболее эффективных, о чем говорит его название. Причем, наилучшие характеристики он обеспечивает для массивов, имеющих случайные значения.