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

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

Представь, что хочешь найти файл Kormen.pdf у себя в папке C:\books\. Как это сделать без использования автоматического поиска? Рассмотрим два варианта.

Вот схема первого варианта решения этой задачи:

Вот схема рекурсивного решения:

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

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

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

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

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

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

Давайте поговорим о них подробнее.

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

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

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

Потому что наша рекурсия уйдёт в бесконечный цикл. На каждом следующем уровне рекурсии число ʜeпостроенных ступеней 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. Вызываем функцию с параметром n и значением prefix, равным пустой строке. Далее будем добавлять в эту строку 0 и 1. В каждом рекурсивном вызове n означает, сколько ещё символов нужно добавить в строку. Рекурсия останавливается, когда n = 0, то есть символы добавлять больше не требуется. Это базовый случай рекурсии.

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

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

Рекурсия часто используется для перебора вариантов. Например, у нас есть 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(n) дополнительной памяти;
  • другой алгоритм медленнее, но ему нужно лишь O(1)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)

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

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

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

Cортировка, которая работает всего за $O(n \log n)$. Она называется сортировка слиянием (англ. merge sort).

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

Cоставные части алгоритма сортировки слиянием:

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

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

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

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

Сортировка слиянием даже в худшем случае работает за $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) и использует стратегию «разделяй и властвуй».

Встроенные функции сортировки во многих языках программирования используют модификации именно алгоритма быстрой сортировки, поскольку на практике она нередко работает даже быстрее сортировки слиянием. Автор этого алгоритма — Чарльз Хоар. Поэтому в честь него quick sort иногда называют сортировкой Хоара.

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

Алгоритм быстрой сортировки использует стратегию «разделяй и властвуй». Любой такой алгоритм состоит из трёх шагов:

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

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

  • Возьмём исходный массив.
  • Выберем какое-нибудь число. Все элементы, меньшие, чем это число, переложим в один массив. Все элементы, большие или равные этому числу, — в другой. Тогда элементы слева будут меньше элементов справа.
  • Отсортируем каждую из частей рекурсивно.
  • Склеим левую часть с правой.

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

У этого алгоритма очень простая идея. Но есть несколько моментов, которые в алгоритме придётся прояснить. Мы должны выбрать какое-нибудь число. А какое именно число мы выбираем?

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

Если мы выберем слишком большое число, то мы получим очень несбалансированное разбиение. Например, если мы выберем максимальный элемент, то получим два пустых массива и один массив с одним элементом. В этом случае мы получим очень неэффективный алгоритм, который будет работать за $O(n^2)$. Поэтому мы должны выбирать опорный элемент так, чтобы получить сбалансированное разбиение. Например, можно выбирать средний элемент. Но это не всегда работает. Например, если массив отсортирован, то мы получим сбалансированное разбиение, но неэффективный алгоритм. Поэтому мы будем выбирать случайный элемент. Это позволит нам получить сбалансированное разбиение и эффективный алгоритм. Но в этом случае мы не сможем гарантировать, что алгоритм будет работать за $O(n log n)$. В худшем случае он будет работать за $O(n^2)$. Но в среднем он будет работать за $O(n log n)$.

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

... и почему она нестабильна

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

В начале спринта мы разобрали алгоритм, который в худшем случае имеет квадратичную сложность — сортировка вставками. Потом поговорили о быстрой сортировке, которая на практике работает быстрее и имеет сложность в среднем $O(n \log n)$, но в худшем случае работает за $O(n^2)$. А ещё разобрали сортировку слиянием, сложность которой даже в худшем случае — $O(n \log 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:

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 столько элементов, сколько встречается в months:

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 элементов.