Алгоритм

Итак, сигнатура функции будет следующей:

quicksort :: (Ord a) => [a] –> [a]

Ничего удивительного тут нет. Базовый случай? Пустой список, как и следовало ожидать. Отсортированный пустой список – это пустой список. Затем следует основной алгоритм: отсортированный список – это список, в котором все элементы, меньшие либо равные «голове» списка, идут впереди (в отсортированном порядке), посередине следует «голова» списка, а потом – все элементы, большие «головы» списка (также отсортированные). Заметьте, в определении мы упомянули сортировку дважды, так что нам, возможно, придётся делать два рекурсивных вызова в теле функции. Также обратите внимание на то, что мы описали алгоритм, просто дав определение отсортированному списку. Мы не указывали явно: «делай это, затем делай то…» В этом красота функционального программирования! Как нам отфильтровать список, чтобы получить только те элементы, которые больше «головы» списка, и те, которые меньше? С помощью генераторов списков.

Если у нас, скажем, есть список [5,1,9,4,6,7,3] и мы хотим отсортировать его, этот алгоритм сначала возьмёт «голову», которая равна 5, и затем поместит её в середину двух списков, где хранятся элементы меньшие и большие «головы» списка. То есть в нашем примере получается следующее: [1,4,3] ++ [5] ++ [9,6,7]. Мы знаем, что когда список будет отсортирован, число 5 будет находиться на четвёртой позиции, потому что есть три числа меньше и три числа больше 5. Теперь, если мы отсортируем списки [1,4,3] и [9,6,7], то получится отсортированный список! Мы сортируем эти два списка той же самой функцией. Рано или поздно мы достигнем пустого списка, который уже отсортирован – в силу своей пустоты. Проиллюстрируем (цветной вариант рисунка приведён на форзаце книги):

Элемент, который расположен на своём месте и больше не будет перемещаться, выделен оранжевым цветом. Если вы просмотрите элементы слева направо, то обнаружите, что они отсортированы. Хотя мы решили сравнивать все элементы с «головами», можно использовать и другие элементы для сравнения. В алгоритме быстрой сортировки элемент, с которым производится сравнение, называется опорным. На нашей картинке такие отмечены зелёным цветом. Мы выбрали головной элемент в качестве опорного, потому что его легко получить при сопоставлении с образцом. Элементы, которые меньше опорного, обозначены светло-зелёным цветом; элементы, которые больше, – темно-зелёным. Желтоватый градиент демонстрирует применение быстрой сортировки.