Изучай Haskell во имя добра! (Липовача) - страница 44
>5 будет находиться на четвёртой позиции, потому что есть три числа меньше и три числа больше 5. Теперь, если мы отсортируем списки >[1,4,3] и >[9,6,7], то получится отсортированный список! Мы сортируем эти два списка той же самой функцией. Рано или поздно мы достигнем пустого списка, который уже отсортирован – в силу своей пустоты. Проиллюстрируем (цветной вариант рисунка приведён на форзаце книги):
Элемент, который расположен на своём месте и больше не будет перемещаться, выделен оранжевым цветом. Если вы просмотрите элементы слева направо, то обнаружите, что они отсортированы. Хотя мы решили сравнивать все элементы с «головами», можно использовать и другие элементы для сравнения. В алгоритме быстрой сортировки элемент, с которым производится сравнение, называется опорным. На нашей картинке такие отмечены зелёным цветом. Мы выбрали головной элемент в качестве опорного, потому что его легко получить при сопоставлении с образцом. Элементы, которые меньше опорного, обозначены светло-зелёным цветом; элементы, которые больше, – темно-зелёным. Желтоватый градиент демонстрирует применение быстрой сортировки.
Определение
>quicksort :: (Ord a) => [a] –> [a]
>quicksort [] = []
>quicksort (x:xs) =
> let smallerSorted = quicksort [a | a <– xs, a <= x]
> biggerSorted = quicksort [a | a <– xs, a > x]
> in smallerSorted ++ [x] ++ biggerSorted
Давайте немного «погоняем» функцию – так сказать, испытаем её в действии:
>ghci> quicksort [10,2,5,3,1,6,7,4,2,3,4,8,9]
>[1,2,2,3,3,4,4,5,6,7,8,9,10]
>ghci> quicksort "съешь ещё этих мягких французских булок, да выпей чаю"
>" ,ааабвгдеееёзииийккклмнопрсстууфхххцчшщъыьэюя"
Ура! Это именно то, чего я хотел!
Думаем рекурсивно
Мы уже много раз использовали рекурсию, и, как вы, возможно, заметили, тут есть определённый шаблон. Обычно вы определяете базовые случаи, а затем задаёте функцию, которая что-либо делает с рядом элементов, и функцию, применяемую к оставшимся элементам. Неважно, список ли это, дерево либо другая структура данных. Сумма – это первый элемент списка плюс сумма оставшейся его части. Произведение списка – это первый его элемент, умноженный на произведение оставшейся части. Длина списка – это единица плюс длина «хвоста» списка. И так далее, и тому подобное…
Само собой разумеется, у всех упомянутых функций есть базовые случаи. Обычно они представляют собой некоторые сценарии выполнения, при которых применение рекурсивного вызова не имеет смысла. Когда имеешь дело со списками, это, как правило, пустой список. Когда имеешь дело с деревьями, это в большинстве случаев узел, не имеющий потомков.