Конспект

Генерация перестановок и рекурсивные сортировки

Ключевые тезисы

• Рекурсия — мощный инструмент для перебора всех вариантов (например, всех перестановок).
• Генерация всех чисел в n-ричной системе счисления — более простая задача, которая помогает понять логику генерации перестановок.
• Две основные рекурсивные сортировки — быстрая сортировка (Тони Хоара) и сортировка слиянием — используют принцип «разделяй и властвуй».

Генерация всех чисел в n-ричной системе счисления

Задача: сгенерировать все числа длины m в системе счисления с основанием n (с лидирующими нулями).

Алгоритм (рекурсивный):

1. Базовый случай: Если длина оставшейся части числа (m) равна 0, вывести текущий префикс.
2. Рекурсивный шаг: Для каждой возможной цифры digit от 0 до n-1:
   • Добавить digit в конец текущего префикса.
   • Вызвать функцию рекурсивно для префикса и длины m-1.
   • Удалить последнюю цифру (digit) из префикса, чтобы подготовиться к следующей итерации.

Пример: Для двоичной системы (n=2) и длины 3 алгоритм выведет: 000, 001, 010, 011, 100, 101, 110, 111.

Генерация всех перестановок

Задача: сгенерировать все возможные перестановки n чисел (например, от 1 до n).

Алгоритм (модификация предыдущего):

1. Базовый случай: Если позиций для расстановки не осталось (m == 0), вывести текущую перестановку (префикс).
2. Рекурсивный шаг: Перебираем все числа от 1 до n. Для каждого числа:
   • Проверяем, не использовалось ли оно уже в текущем префиксе (функция search).
   • Если число еще не использовано, добавляем его в префикс.
   • Вызываем рекурсивно функцию для генерации оставшейся части перестановки.
   • Удаляем добавленное число из префикса (возвращаем состояние).

Количество перестановок n чисел равно n! (n-факториал).

Рекурсивные сортировки

Быстрая сортировка (Тони Хоара)

• Принцип: «Разделяй и властвуй». Сортирующее действие выполняется на прямом ходу рекурсии.
• Идея:
  1. Выбирается барьерный (опорный) элемент из массива.
  2. Массив переупорядочивается так, чтобы все элементы меньшие опорного оказались слева, равные — в середине, большие — справа.
  3. Рекурсивно применяется тот же алгоритм к левой и правой частям (равные элементы уже отсортированы).
• Характеристики:
  • Средняя сложность: O(n log n).
  • Худший случай (плохой выбор опорного элемента): O(n²).
  • Память: Может работать без дополнительной памяти (in-place).

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

• Принцип: «Разделяй и властвуй». Сортирующее действие выполняется на обратном ходу рекурсии.
• Идея:
  1. Массив рекурсивно разбивается на две примерно равные части.
  2. Предполагается, что две полученные половинки уже отсортированы (это обеспечивается рекурсивными вызовами).
  3. Происходит слияние (merge) двух отсортированных половинок в один отсортированный массив. Процесс слияния использует два указателя и требует дополнительного временного массива.
• Характеристики:
  • Сложность: Гарантированная O(n log n) для любых входных данных.
  • Память: Требует O(n) дополнительной памяти для временного массива.

Выводы

• Рекурсия естественным образом подходит для задач полного перебора (генерации комбинаций, перестановок).
• Ключевые эффективные алгоритмы сортировки (быстрая и слиянием) основаны на рекурсивном принципе «разделяй и властвуй», но различаются в деталях: моменте выполнения работы, устойчивости и использовании памяти.