Алгоритм

Quicksort является быстрым алгоритмом сортировки, который решает задачу используя проблему divide-and-conquer (разделяй и властвуй). Quicksort это рекурсия приводит массив элементов к элементарному виду, т.е. когда алгоритм рекурсивно делит массив на меньшие и еще более меньшие массивы. Quicksort сортирует эти очень маленькие массивы и комбинирует результаты создавая сортированную версию исходного массива. Из-за рекурсивного характера реализацию quicksort несколько трудно понять. Прежде, чем исследовать реализацию, мы вначале рассмотрим идею алгоритма.

Quicksort алгоритм может быть получен в следующих четырех основных шагах. Представленные в контексте сортировки массива, эти шаги следующие.

1. Если размер массива равен нулю или содержит один элемент, то массив отсортирован. Это и есть основной случай.
2. Выберите элемент в середине массива, чтобы использовать его в качестве центра. Это - шаг выбора центра.
3. Создайте два новых массива. Поместите все элементы, которые являются меньше чем элемент центра в один из подмассивов, оставшиеся элементы в другой подмассив. Это - шаг разделения.
4. В подмассиве, который содержит элементы меньше чем центральный, еще раз разделите через уже его центр еще на два подмассива (повтор шагов 2 и 3). Это - рекурсивный шаг дележа.

Рассмотрим решение задачи на примере. Обратимся к рис. 1.

Рисунок 1 Несортированный массив

Так как массив на рисунке 1 содержит больше чем один элемент, quicksort начинает работу с шага 2, выбора центра. Есть много различных стратегий, которые мы можем использовать, чтобы выбрать элемент центра. Остановимся на простейшем, включающий выбор среднего элемента массива как элемент центра. Этот элемент содержит значение 33. После выбора элемента центра quicksort делит остающиеся элементы в два подмассива. Один подмассив содержит элементы разделенного массива, значения которого являются меньше чем 33, другой подмассив содержит элементы, значения которых больше чем 33. Рисунок 2 иллюстрирует этот шаг раздела. Здесь на рисунке круг обозначает элемент центра.

Рисунок 2 Выбор центра и раздел

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

Рисунок 3 Второе разделение уровня

Quicksort алгоритм должен только выбрать элементы центра, которые содержат больше чем один элемент. Теперь в поле зрения у нас четыре подмассива, они на рисунке 3 в нижнем ряду. Считывая числа с лево на право, видим, первый подмассив содержит только один элемент со значением 3. Второй подмассив содержит элементы 12 и 21, и третий подмассив содержит элементы 52 и 53. Четвертый подмассив содержит ноль элементов. Знак пустого множества (круг с диагональной чертой) обозначает, что этот подмассив содержит ноль элементов. Quicksort алгоритм не трогает первый и четвертый подмассивы, так как каждый из них содержит меньше чем два элемента (см. шаг 1). В этой точке эти два подмассива считаются уже отсортированными. Так как второй и третий массивы, содержат больше чем один элемент, то, вероятно, они не находятся в отсортированном порядке. Quicksort должен рекурсивно рассмотреть их и разделить на подмассивы, см рис. 4, нижняя строка.

Рисунок 4 После последнего необходимого раздела

Рекурсивная природа quicksort разделяет исходный массив на еще меньшие подмассивы. В конечном счете разделение приводит к окончательной сортировке всего массива. Рисунок 5 изображает отсортированную версию исходного массива.

Рисунок 5 Сортированный массив