На этом шаге мы закончим изучение этого вопроса.
Код
Мы создадим функцию q, которая реализует алгоритм быстрой сортировки в одной строке кода Python и сортирует любой аргумент, переданный в нее в виде списка целых чисел (пример 6.14).
Пример 6.14. Однострочная реализация алгоритма быстрой сортировки с помощью рекурсии
## Данные unsorted = [33, 2, 3, 45, 6, 54, 33] ## Однострочник q = lambda l: q([x for x in l[1:] if x <= l[0]]) + [l[0]] + q([x for x in l if x > l[0]]) if l else [] ## Результат print(q(unsorted))
Можете угадать - последний раз - результаты выполнения фрагмента кода?
Принцип работы
Этот однострочник полностью воспроизводит алгоритм, который мы только что обсуждали. Во-первых, мы создаем новую лямбда-функцию q, принимающую в качестве аргумента список l, который нужно отсортировать. В укрупненном виде структура этой лямбда-функции выглядит следующим образом:
lambda l: q(левый) + опорный_элемент + q(правый) if l else []
При граничном случае рекурсии - когда список пуст и, следовательно, сортируется тривиальным образом - лямбда-функция возвращает пустой список [].
Во всех прочих случаях функция берет в качестве первого элемента списка l опорный_элемент и делит все элементы на два подсписка (левый и правый), в зависимости от того, меньше или больше они, чем опорный_элемент. Для этого мы воспользуемся обычным списковым включением. А поскольку эти два подсписка, вероятно, не отсортированы, мы рекурсивно вызываем алгоритм быстрой сортировки и для них. Наконец, мы объединяем все три списка и возвращаем итоговый отсортированный список. Результат выглядит следующим образом:
## Результат print(q(unsorted)) # [2, 3, 6, 33, 33, 45, 54]
На следующем шаге мы подведем некоторые итоги.
