Рекурсия и сортировки

Настоящая глава начинается с рекурсии, для многих первого трудного места в программировании, после чего рекурсия применяется к самой изученной задаче информатики — сортировке.

Введение. Примеры задач на рекурсию

Пусть требуется найти файл Kormen.pdf в папке C:\books\, заполненной вложенными подпапками, без поиска, встроенного в файловый менеджер. Возможны два варианта.

Первый — обычный обход списком:

   Обходим папки списком, вручную запоминая, куда ещё не заходили:

   очередь: [C:\books]
   → зашли в C:\books, нашли подпапки: algo, physics
   очередь: [algo, physics]
   → зашли в algo, нашли подпапку: sorting
   очередь: [physics, sorting]
   → зашли в physics … и так далее, пока очередь не опустеет

Второй — тот же поиск, записанный рекурсивно:

   найти(C:\books)
   ├── найти(algo)
   │   └── найти(sorting) ──▶ Kormen.pdf найден!
   ├── найти(physics)
   └── найти(math)

На каждом уровне погружения рекурсия добавляет в стек вызовов, рассмотренный в предыдущей главе, очередной блок, хранящий локальные переменные текущего вызова. Найдя нужный файл, функция останавливает углубление и начинает по цепочке, от одного уровня к другому, возвращать полученный результат программе, вызвавшей её первой.

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

Рекурсивный и базовый случаи

Любая корректно работающая рекурсия состоит из двух обязательных частей:

  • рекурсивного случая, запускающего прямой ход рекурсии и её углубление;
  • базового случая, который в нужный момент останавливает это углубление и запускает обратный ход рекурсии.

Рекурсивный случай

Рассмотрим заготовку функции, строящей лестницу из n ступеней:

функция stairs_builder(n):
    построить 1 ступеньку
    print("Осталось построить {n} ступеней.")
    stairs_builder(n - 1)

Вызов функцией самой себя с изменёнными параметрами, stairs_builder(n - 1), и есть рекурсивный случай. Однако программа, написанная таким образом, приведёт к зависанию компьютера: рекурсия, лишённая условия остановки, уйдёт в бесконечный цикл.

На каждом следующем уровне рекурсии число непостроенных ступеней n уменьшается на 1. Но после n = 0 функция, не знающая базового случая, не остановит работу, а вызовется со значением −1, затем с −2 и так далее. При неограниченных ресурсах лестница строилась бы вечно.

Базовый случай

У любой рекурсивной функции должен быть базовый случай, то есть условие, обрывающее цепочку рекурсивных вызовов. Необходимо определить, что происходит в базовом случае и какое значение возвращается наверх.

Рекурсия в stairs_builder() должна остановиться, когда построено заданное количество ступеней, то есть когда счётчик, уменьшаемый на каждом уровне, дойдёт до n = 0. Это и есть базовый случай.

функция stairs_builder(n):
  if n == 0:
    return
  построить 1 ступеньку
  print("Осталось построить {n} ступеней.")
  stairs_builder(n - 1)

Правильное построение рекурсии

Чтобы решить задачу рекурсивным методом, необходимо определить два случая, дополняющих друг друга: базовый и рекурсивный.

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

Базовый случай описывает ситуацию, требующую остановки: результат, возвращаемый функцией здесь, вычисляется явно, без обращения к рекурсивным вызовам.

Частой ошибкой в рекурсии является зацикливание, обычно из-за пропущенного базового случая. Другой распространённой причиной ухода в бесконечный цикл являются параметры, неверно изменённые в рекурсивном случае.

Например, если функция вызывает саму себя, не меняя значение параметра, то даже при заданном базовом случае до него дело не дойдёт. Необходимо убедиться, что при любом наборе параметров, поданном на вход, функция рано или поздно сведётся к одному из базовых случаев.

В большинстве случаев программа, ушедшая в бесконечную рекурсию, не будет работать вечно, а завершится с ошибкой переполнения стека вызовов или с ошибкой сегментации (англ. segmentation fault): каждый вызов, добавленный в стек, расходует память, а она ограничена. Поведение программы зависит и от самого алгоритма, и от используемого компилятора. Подробнее об этом можно прочитать в статье про оптимизацию хвостовой рекурсии (англ. tail call optimization).

Разбор задач. Рекурсивный перебор вариантов

Рекурсия часто применяется для генерации объектов, устроенных единообразно: числовых или скобочных последовательностей.

Генерация последовательностей из 0 и 1

Рассмотрим генерацию всех последовательностей длины n, составленных из нулей и единиц.

Функция принимает число n и строку prefix, накапливающую уже выбранные символы. Вызовем её со значением prefix, равным пустой строке, чтобы далее дописывать в неё 0 и 1. В каждом рекурсивном вызове n означает, сколько символов ещё не дописано. Рекурсия останавливается, когда n = 0: строка, собранная к этому моменту, готова, и это базовый случай рекурсии.

В рекурсивном случае функция вызывает себя дважды, но с разными параметрами: в первый раз к строке prefix приписывается цифра 0, а во второй 1. Значение n, переданное вниз, каждый раз уменьшается на 1, а prefix удлиняется на один символ. Таким образом рекурсия уходит на n уровней в глубину, и каждый её лист отвечает одной построенной последовательности.

Решение этой задачи удобно представлять в виде бинарного дерева, растущего вниз от пустой строки. Переход влево соответствует приписыванию 0, переход вправо — приписыванию 1. Пройдя от корня по всем ветвям, получим все последовательности длины 3, составленные из 0 и 1.

                    «»
              ┌─────┴─────┐
             0             1
          ┌──┴──┐       ┌──┴──┐
         00     01     10     11
        ┌─┴─┐  ┌─┴─┐  ┌─┴─┐  ┌─┴─┐
      000 001 010 011 100 101 110 111

Рекурсия часто используется для перебора вариантов. Пусть имеется n различных предметов, каждый из которых может быть взят или отложен в сторону. Тогда наборов, собираемых из них, ровно \(2^n\). Пронумеруем предметы числами от 1 до \(n\) и опишем набор строкой, где предмет, положенный в рюкзак, помечен цифрой 1, а отложенный — цифрой 0. Таким образом, задача перебора вариантов сводится к уже рассмотренной задаче генерации последовательностей.

def generate(n, prefix):
    if n == 0:
        print(prefix)
        return
    generate(n - 1, prefix + '0')
    generate(n - 1, prefix + '1')

generate(3, '')

000
001
010
011
100
101
110
111

Алгоритмы сортировки. Знакомство

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

Сортировки среди нас

В смартфоне контакты, записанные вперемешку, показываются по алфавиту, а расписание автобусов составляется по времени их отправления. Поисковая система выдаёт список ответов, ранжированный по степени их релевантности запросу.

Роль сортировок в решении задач

Во многих задачах работать с отсортированными данными удобнее, чем с неупорядоченными. Например:

  • найти элемент в массиве быстрее чем за \(O(n)\), воспользовавшись бинарным поиском, возможно только на отсортированных данных;
  • таблицу «10 лучших студентов курса» проще собрать из списка, упорядоченного не по алфавиту, а по среднему баллу.

Нередко сортировка становится узким местом всего решения, поэтому необходимо знать, как массив, полученный на вход, сортируется наиболее эффективно.

Лучшей сортировки в общем случае не существует: для данных разной природы и ограничений, наложенных задачей, выигрывают разные алгоритмы.

Выбор алгоритма сортировки

Сравним два алгоритма, решающих одну и ту же задачу:

  • один работает быстро, но требует \(O(n)\) дополнительной памяти;
  • другой алгоритм медленнее, но ему требуется лишь \(O(1)\) дополнительной памяти.

Пусть в компании стоят старые серверы, свободной памяти на которых почти не осталось. На одном из них лежат данные об удовлетворённости жизнью, собранные по всем городам страны. Для ежемесячного отчёта их необходимо отсортировать и выбрать названия 100 городов с самыми довольными жителями. Отчёт требуется сдать через неделю.

В этом случае предпочтительнее более медленный алгоритм, но эффективный по памяти.

Другая ситуация: команде поручено сделать стенд, показывающий удовлетворённость жителей страны в реальном времени. Под эту задачу был приобретён новый мощный сервер. Каждую секунду на вход программы поступает обновлённый массив со значениями индекса, измеренными по всем городам. Алгоритм должен составить «Топ-5 самых довольных городов» и обновлять этот список без задержек.

Здесь предпочтительнее более быстрый алгоритм, но требующий больше памяти.

При решении задачи имеющиеся ресурсы оцениваются по трём обстоятельствам:

  • Срочность ответа. Если результат сортировки нужен не срочно, подходит более медленный алгоритм, зато не требующий лишней памяти.
  • Объём данных, поступающих на вход. Если в массиве всего 1000 элементов, то любой алгоритм сортировки упорядочит их за неощутимое время. На 5 000 000 элементов разница между алгоритмами становится решающей.
  • Объём доступной памяти. Если свободного места хватает на вторую копию массива, можно собирать отсортированный массив в выделенной памяти, а не переставлять элементы в исходном.

Устойчивость сортировок

Сортировку, сохраняющую взаимный порядок элементов с равным значением сравниваемого признака, называют устойчивой (англ. stable sort). Если же равные элементы могут поменяться местами, сортировку называют неустойчивой. Разница важна, когда данные сортируют несколько раз подряд по разным ключам: устойчивая сортировка сохраняет результат, полученный на предыдущем проходе, а неустойчивая его перемешивает.

Сортировка по ключу

Признак, по которому элементы сравниваются, называют «ключом сортировки». Сортировка по ключу уже применялась выше, когда города упорядочивались по индексу удовлетворённости, посчитанному для каждого из них.

С точки зрения алгоритма сортировки меняется только один этап — операция, сравнивающая элементы.

Обычно функция сортировки принимает вспомогательным аргументом функцию, задающую порядок элементов. Два распространённых способа:

  • В одном варианте передаётся функция одного аргумента key(object). Она даёт значение ключа для каждого объекта, и объекты попарно сравниваются по вычисленным ключам.
  • В другом варианте передаётся функция двух аргументов less(object_1, object_2), сравнивающая два объекта напрямую: она возвращает true, если первый должен стоять раньше второго, и false в противном случае. Такую функцию называют «компаратор» (англ. compare, «сравнивать»).

Компаратор задаёт порядок гибче, чем ключ: сортировку по любому ключу легко переписать через компаратор:

функция less(object_1, object_2):
    return key(object_1) < key(object_2)

Обратное — ключ, восстановленный по компаратору, — удаётся не всегда, и не всякий компаратор работает корректно. Поэтому обычно проще пользоваться функцией, вычисляющей ключ сортировки.

Способ передачи компаратора либо функции вычисления ключа в функцию сортировки, встроенную в конкретный язык, описан в её документации.

Сортировка слиянием

Сортировка слиянием (англ. merge sort) работает за \(O(n \log n)\) даже в худшем случае.

Принцип работы сортировки слиянием

Алгоритм складывается из трёх действий, повторяемых на каждом уровне:

  • Массив разбивается на две части примерно одинакового размера.
  • Если в подмассиве, полученном при разбиении, больше одного элемента, то для него рекурсивно запускается тот же алгоритм, начиная с первого шага.
  • Два упорядоченных массива соединяются в один.

Условием остановки рекурсии служит массив из одного элемента, уже отсортированный по определению: это базовый случай.

   Разбиение:                        Слияние:
        [5 2 9 1]                      [1 2 5 9]
        ┌────┴────┐                    ┌────┴────┐
      [5 2]     [9 1]                [2 5]     [1 9]
      ┌─┴─┐     ┌─┴─┐                ┌─┴─┐     ┌─┴─┐
     [5] [2]   [9] [1]              [5] [2]   [9] [1]

Дерево алгоритма сортировки слиянием: массив разбивается на части примерно равной длины. Каждая часть сортируется рекурсивно, после чего части, приведённые в порядок, объединяются в единый массив

Ниже приведены сначала слияние, собирающее из двух упорядоченных массивов один, затем сама сортировка, состоящая из разбиения и рекурсивного вызова:

def merge(left, right):
    # Идём по обоим массивам сразу, каждый раз забирая меньший из головных элементов
    merged = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        # При равенстве берём элемент из левой части: этим и держится устойчивость
        if right[j] < left[i]:
            merged.append(right[j])
            j += 1
        else:
            merged.append(left[i])
            i += 1
    # Хвост, оставшийся от одного из массивов, дописываем целиком
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


def merge_sort(nums):
    # Массив из одного элемента уже отсортирован: это базовый случай
    if len(nums) <= 1:
        return nums
    middle = len(nums) // 2
    left = merge_sort(nums[:middle])
    right = merge_sort(nums[middle:])
    return merge(left, right)

Сложность алгоритма

Сортировка слиянием даже в худшем случае работает за \(O(n \log n)\).

На каждом шаге прямого хода рекурсии массив разбивается на две примерно равные по размеру части, и разбиение продолжается до тех пор, пока длина массива не станет равной 1. Следовательно, каждый элемент, попадающий в такую цепочку, будет задействован примерно в \(\log_2 n\) вызовах рекурсивной функции.

Иначе можно сказать, что глубина рекурсии составляет \(O(\log_2n)\). Глубиной рекурсии называют максимальную глубину стека вызовов, достигаемую за время её работы.

На каждом шаге обратного хода рекурсии выполняется слияние двух отсортированных массивов, а оно выполняется одним проходом. Следовательно, на каждом уровне рекурсии затрачивается \(O(n)\) операций: сколько бы частей там ни было, вместе они содержат все \(n\) чисел, распределённых по ним при разбиении.

Общая сложность алгоритма \(O(n \cdot \log_2 n)\).

Пространственная сложность алгоритма

На каждом уровне рекурсии слиянию требуется \(O(n)\) дополнительной памяти, куда копируются элементы объединяемых блоков в правильном порядке. Если выделять её на каждом уровне заново, суммарно придётся затратить \(O(n\log{n})\) дополнительной памяти.

Однако вспомогательный массив требуется лишь временно: элементы, собранные в нём, сразу переносятся обратно в исходный, а выделенная память освобождается. В каждый момент времени занято вспомогательное пространство лишь одного, текущего уровня рекурсии, поэтому достаточно \(O(n)\) дополнительной памяти.

Устойчивость алгоритма

Сортировка слиянием устойчива. При равенстве элементов в двух сливаемых массивах приоритет отдаётся элементу, лежащему в левой половине. Так происходит на каждом уровне, вплоть до объединения двух последних половин в целый массив. Поэтому равные элементы в массиве, собранном алгоритмом, стоят друг относительно друга так же, как и в исходном.

Быстрая сортировка

Быстрая сортировка (англ. quick sort) опирается на стратегию «разделяй и властвуй».

Стандартные библиотеки разных языков сделали разный выбор алгоритма сортировки: в C++ std::sort — интроспективная сортировка, то есть быстрая, переходящая в пирамидальную на неудачных входах, а в Python sorted() и list.sort() — Timsort, гибрид сортировки слиянием и вставками, устойчивый и использующий уже упорядоченные фрагменты без дополнительных затрат. Автором быстрой сортировки был Чарльз Хоар, поэтому в честь него quick sort иногда называют сортировкой Хоара.

Принцип работы алгоритма

Любой алгоритм, построенный по этой стратегии, состоит из трёх шагов:

  • разделение данных на части меньшего размера;
  • рекурсивный вызов алгоритма для полученных частей;
  • объединение результатов.

В merge sort шаг разделения прост, а шаг объединения нетривиален. В быстрой сортировке наоборот: разделение на части сложнее, зато части, отсортированные рекурсивно, объединяются дописыванием одного массива после другого.

  • Возьмём исходный массив:
   [7  2  9  4  3  8  1]
  • Выберем какое-нибудь число, например 4, и назовём его опорным. Все элементы, меньшие опоры, переложим в один массив, все большие — в другой, а саму опору (и равные ей) оставим посередине:
   [2  3  1]   4   [7  9  8]
    меньше   опора   больше
  • Отсортируем каждую из частей рекурсивно.
  • Соединим левую часть с правой.

Получен отсортированный массив:

   [1  2  3]   4   [7  8  9]   ──▶   [1  2  3  4  7  8  9]

Число, назначенное опорой, было выбрано произвольно.

Выбор опорного элемента

Если взять опорой максимум, разбиение выродится: слева окажется весь массив, справа пусто. Длина, уменьшенная всего на единицу, даст \(n\) уровней рекурсии, а работы на каждом линейно. Итого \(O(n^2)\), не лучше наивных квадратичных сортировок.

Следовательно, опора должна делить массив примерно пополам. Разумной эвристикой служит элемент, взятый из середины: на отсортированном или почти отсортированном массиве (а такие входы часты) он даёт ровное разбиение. Однако под любое фиксированное правило выбора можно подобрать массив, вырождающий разбиение, и в олимпиадных тестах такие массивы появляются намеренно.

При опоре, выбранной случайно, плохое разбиение зависит не от массива, а от жребия. Гарантии это по-прежнему не даёт: при очень неудачной череде жребиев быстрая сортировка отработает за \(O(n^2)\). Однако вероятность такого исхода исчезающе мала, а в среднем получается \(O(n \log n)\).

Разбиение раскладывает массив на три части: меньшие опоры, равные ей и превосходящие её, — а сама сортировка рекурсивно упорядочивает крайние части и соединяет их со средней:

import random


def partition(nums, pivot):
    # Раскладываем элементы по трём массивам, сравнивая каждый с опорой
    less, equal, greater = [], [], []
    for num in nums:
        if num < pivot:
            less.append(num)
        elif num > pivot:
            greater.append(num)
        else:
            equal.append(num)
    return less, equal, greater


def quick_sort(nums):
    # Массив из нуля или одного элемента уже отсортирован: это базовый случай
    if len(nums) <= 1:
        return nums
    # Опору выбираем случайно, чтобы входные данные не могли выродить разбиение
    pivot = random.choice(nums)
    less, equal, greater = partition(nums, pivot)
    return quick_sort(less) + equal + quick_sort(greater)

Равные опоре элементы, собранные отдельно, попадают на своё место сразу и в рекурсию больше не передаются; без этой предосторожности массив из одинаковых чисел привёл бы алгоритм к бесконечной рекурсии.

Сложность быстрой сортировки

Разбиение массива вокруг опоры выполняется одним проходом за \(O(n)\) операций. Если опора, выбираемая на каждом шаге, делит массив примерно пополам, уровней рекурсии будет \(O(\log n)\), и на каждом суммарно затрачивается \(O(n)\), откуда и получается \(O(n \log n)\) в среднем. При вырожденных разбиениях уровней становится \(n\), и сложность возрастает до \(O(n^2)\).

Схема с тремя новыми массивами стоит \(O(n)\) дополнительной памяти, и от этой платы на практике избавляются. Разбиение выполняют на месте: поддерживается граница «меньших», массив проходится одним проходом, и очередной элемент, меньший опоры, меняется местами с элементом на границе, а в конце опора ставится на место границы.

Памяти такой быстрой сортировке почти не требуется: сверх исходного массива расходуется только стек вызовов, \(O(\log n)\) при удачных разбиениях. Этим она и выигрывает у сортировки слиянием, требующей вспомогательный массив на \(n\) элементов.

Устойчивостью она не обладает: при разбиении элементы перебрасываются через весь массив, и два равных могут поменяться местами. Поэтому там, где исходный порядок равных элементов важен, применяют сортировку слиянием или дописывают в ключ номер, присвоенный элементу изначально.

Сортировка подсчётом

Отсортировать быстрее чем за \(O(n \log n)\) возможно, но лишь для узкого класса задач, устроенных особым образом.

Принцип работы алгоритма

Дан массив чисел:

nums = [5, 7, 1, 0, 1, 5, 11, 1]

Требуется отсортировать его по неубыванию. Известно, что числа в нём обозначают номера месяцев, то есть лежат в диапазоне от 0 до 11.

Заведём массив из 12 элементов, заполненный нулями.

months = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Теперь пройдём по массиву nums и для каждого числа увеличим на 1 счётчик, отвечающий этому месяцу:

months[5] += 1
months[7] += 1
months[1] += 1
months[0] += 1
months[1] += 1
months[5] += 1
months[11] += 1
months[1] += 1

Получим:

months = [1, 3, 0, 0, 0, 2, 0, 1, 0, 0, 0, 1]

Теперь пройдём по массиву months и допишем в nums столько копий каждого номера, сколько единиц накоплено в счётчике, отвечающем этому месяцу:

nums = []
for i in range(len(months)):
    for j in range(months[i]):
        nums.append(i)

Получим:

nums = [0, 1, 1, 1, 5, 5, 7, 11]

Код для случая, когда значения элементов лежат в полуинтервале от 0 до k:

def counting_sort(nums, k):
    # Создаём массив из k элементов, заполненный нулями
    counts = [0] * k
    # Проходим по массиву nums и увеличиваем соответствующий элемент в массиве counts
    for num in nums:
        counts[num] += 1
    # Проходим по массиву counts и добавляем в массив nums столько элементов, сколько встречается в counts
    nums = []
    for i in range(len(counts)):
        for j in range(counts[i]):
            nums.append(i)
    return nums

Алгоритм сортировки подсчётом использует \(O(k)\) дополнительной памяти, где \(k\) — мощность множества значений, которые могут встретиться в массиве. Память, выделенная под вспомогательный массив, и есть вся плата за скорость. Чтобы создать этот массив, необходимо знать диапазон возможных значений. В примере потребовался дополнительный массив всего из 12 элементов.

Элементы здесь ни разу не сравниваются друг с другом, поэтому сортировка подсчётом и обходит границу \(O(n \log n)\), доказанную для сортировок сравнением. Работает она за \(O(n + k)\), и выигрыш сохраняется, только пока \(k\) сопоставимо с \(n\). Сортировать таким способом миллион чисел, разбросанных по диапазону до миллиарда, бессмысленно: массив, заведённый под счётчики, окажется в тысячу раз длиннее исходного.

Устойчивость алгоритма

Приведённая реализация неустойчива: она не переставляет элементы, а собирает массив заново из одних счётчиков, и всё, что было привязано к равным ключам, перемешивается или теряется. Для чисел разницы нет: две единицы неотличимы друг от друга. Если же ключ — номер месяца, взятый у записи с фамилией, порядок записей, попавших в один месяц, оказывается произвольным.

Устойчивый вариант вычисляет по массиву счётчиков префиксные суммы, получая для каждого значения границу, за которой начинается его блок в выходном массиве, а затем проходит исходный массив справа налево и ставит каждый элемент на место, отсчитанное от этой границы. Проход, идущий с конца, и уменьшение границы на каждом шаге вместе и сохраняют исходный порядок равных.

Резюме

  • Рекурсия складывается из базового случая, останавливающего спуск, и рекурсивного, сводящего задачу к меньшей; без базового случая происходит переполнение стека.
  • Сортировка слиянием работает за \(O(n \log n)\) даже в худшем случае и устойчива, но требует \(O(n)\) дополнительной памяти под вспомогательный массив.
  • Быстрая сортировка в среднем также \(O(n \log n)\) и почти не требует памяти, зато на неудачных разбиениях деградирует до \(O(n^2)\) и порядок равных элементов не сохраняет.
  • Опору в быстрой сортировке следует выбирать случайно: любое фиксированное правило можно обойти массивом, подобранным намеренно.
  • Сортировка подсчётом не сравнивает элементы вовсе, благодаря чему обходит границу \(O(n \log n)\), но применима лишь на небольшом диапазоне значений и стоит \(O(k)\) памяти.
  • Устойчивость является критерием выбора: она необходима всякий раз, когда данные сортируют несколько раз подряд по разным ключам.
  • Собственную сортировку в рабочем коде писать незачем, потому что встроенная почти всегда быстрее и лучше отлажена; знать, как она устроена, необходимо, чтобы понимать, чего от неё ожидать.