Не прошло и года, как мы добрались до разговора об алгоритмах сортировки. Это классика мира программирования. Чтобы более продвинутые подписчики не скучали, будем писать qsort на Haskell.
Почему вообще важно знать сортировки? Например, потому что они дают приложению предсказуемость — понимание того, где и какие данные лежат. Если вы держите дом в порядке, вы не тратите время на поиск нужных вещей: просто подходите и берёте их с ожидаемого места. В программировании ровно та же идея — поддерживать порядок.
Один из самых быстрых и известных алгоритмов — qsort (quick sort). Его шаги:
1️⃣Выбираем опорный элемент (pivot).
2️⃣Исходный массив делится на два подмассива:
⬛в левом элементы меньше опорного,
⬛в правом — больше.
3️⃣Каждый подмассив сортируется отдельно, то есть для каждого из них мы снова возвращаемся к шагу 1.
Давайте на примере:
[5, 9, 12, 2, 8, 3, 15, 0, 13, 4]⬛выбираем опорный элемент, пусть это будет 6
⬛левый подмассив:
[5, 2, 3, 0, 4]⬛правый подмассив:
[9, 12, 8, 15, 13]⬛итого:
[5, 2, 3, 0, 4] [6] [9, 12, 8, 15, 13]⬛переключаемся на левый подмассив
⬛выбираем опорный элемент 3
⬛получаем:
[2, 0] [3] [5, 4]снова идём в левый: опорный 2
⬛получается:
[0] [2] []⬛дальше идти некуда — массивы либо пустые, либо из одного элемента
⬛возвращаемся уровнем выше:
[0, 2, 3] [5, 4]⬛сортируем правую часть →
[0, 2, 3, 4, 5]⬛возвращаемся ещё выше:
[0, 2, 3, 4, 5, 6] [9, 12, 8, 15, 13]⬛повторяем то же самое для правой части
⬛в итоге получаем:
[0, 2, 3, 4, 5, 6, 8, 9, 12, 13, 15]Визуализация.
Что должен заметить опытный читатель:
⬛рекурсию;
⬛то, что выбираю опорный элемент так, чтобы слева и справа было примерно одинаковое количество элементов — беру медиану. А вот на визуализации берут физически последний элемент массива. Есть разные стратегии выбора pivot’а, и на разных входных данных они будут давать разные результаты. Попробуйте поиграться: случайный элемент, первый элемент массива, физически средний элемент;
⬛нет никакого требования к внутреннему порядку элементов в подмассивах относительно исходного. Главное — слева меньше, справа больше. Обязательно нужно думать о минимизации перестановок.
Ну что ж, давайте писать код. Повторите предыдущие темы про рекурсию, концепцию точечной пары и списка.
Напишем код прямо так, как обсуждали в алгоритме:
qsort [] = []
qsort (x:xs) = qsort small ++ mid ++ qsort large
where
small = [y | y <- xs, y < x]
mid = [y | y <- xs, y == x] ++ [x]
large = [y | y <- xs, y > x]Если список пустой — останавливаем рекурсию.
Если что-то есть, пусть первый элемент будет опорным. Тогда итоговый отсортированный массив — это:
⬛qsort от чисел меньше x,
⬛потом сам x,
⬛потом qsort от чисел больше x.
Изи!
Но с точки зрения вычислений — полный отстой. Например, потому что
small и large — это всегда новые списки.Haskell знаменит наличием «магического» понятия — монада. Не уверена, что до конца понимаю этот термин и могу нормально его объяснить. Заметка на полях: отличная идея для одной из будущих бесед.
Когда училась в университете, один уважаемый человек и талантливый программист говорил, что если кто-то объяснит ему, что такое монада, то он чуть ли не автоматом поставит зачёт. Конечно, студенты ежегодно пытались. И вот очередная попытка: к доске выходит мальчик и говорит:
«А что тут непонятного? Монада — это моноид в категории эндофункторов».
Господи, прости, не помню точную формулировку и корректное определение — это всё, что зачем-то осталось в моей памяти 🙈.
И человек искренне считал, что дальнейшие пояснения не нужны.
Haskell — чистый функциональный язык. Что это значит? Функции не имеют никаких сайд-эффектов. Следствие — неизменяемость данных.
Так можем ли тогда сделать сортировку без дополнительной памяти, если список нельзя менять? Да. На помощь приходят монады.
Это не грязный хак, не подумайте. Под ними лежит настоящая математика, которая доказывает «чистоту».
И вот как раз с помощью монад мы напишем qsort на следующей неделе. Попробуем обойтись без детального объяснения монад.
Не переключайтесь.
#бабанюра_программирует