Описание. Эту сортировку называют быстрой, потому что на практике она оказывается самым быстрым алгоритмом сортировки из тех

Введение в алгоритм

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

Эту сортировку называют быстрой, потому что на практике она оказывается самым быстрым алгоритмом сортировки из тех, что оперируют сравнениями (т.е. из класса обменных сортировок). Время его работы для массива из п чисел в худшем случае составляет Q(n ²), на практике этот алгоритм является одним из самых быстрых: математическое ожидание времени работы составляет O (n ×log n), причём множитель при n ×log n довольно мал. Кроме того, быстрая сортировка не требует дополнительной памяти и сохраняет эффективность для систем с виртуальной памятью.

Этот алгоритм является ярким примером реализации принципа «разделяй и властвуй». Как показывают теоретические выкладки, наиболее эффективным в общем случае оказывается разделение задачи на две равные по сложности части, что здесь и делается.

На каждом шаге алгоритма сначала выбирается «средний» элемент, затем переставляются элементы массива так, что массив разделился на две части. Первая часть содержит элементы, меньше «среднего» и, возможно, равные ему. Вторая часть содержит элементы больше «среднего» и, возможно, равные ему. После такого деления массива остается только отсортировать его части по отдельности, с которыми поступаем аналогично (делим на две части). И так до тех пор, пока эти части не окажутся состоящими из одного элемента, а массив из одного элемента всегда отсортирован. В случае, когда массив содержит только одинаковые элементы, выбор «среднего» элемента не производится и сортировка не осуществляется.

Быстрая сортировка (quicksort), как и сортировка слиянием, основана на принципе «разделяй и властвуй». Сортировка участка A [ p.. r ] происходит следующим образом.

• Элементы массива А переставляются так, чтобы любой из элементов А [ p ] ,..., A [ q ]был не больше любого из элементов A [ q + 1],..., А [ r ], где q – некоторое число в интервале р ≤ q < r. Эта операция называется разделением (partition).