На этом шаге мы рассмотрим несколько рекурсивных решений такой сортировки.
Этот и следующий шаг содержит несколько классических задач, которые имеют изящные рекурсивные решения.
Сортировки выбором - один из самых простых способов сортировки элементов списка. Для заданного списка из n чисел предложить метод его сортировки в порядке возрастания. Алгоритм начинается с поиска и размещения наименьшего элемента списка в первой позиции выходного списка. На втором шаге метод ищет минимальный элемент среди оставшихся 1...(n - 1) элементов и помещает его во вторую позицию списка вывода. Эта процедура выполняется (n - 1) раз, пока в итоге массив не отсортируется. Ясно, что в конце k-го шага наименьшие k чисел уже отсортированы, а после (n - 1) шага будет полностью отсортирован весь список.
Теперь рассмотрим линейно-рекурсивную версию алгоритма. Во-первых, размер задачи - это длина списка (n). Начальное условие выполняется, когда список состоит из одного элемента и не нуждается в сортировке, являясь, очевидно, её результатом. Кроме того, если вход пуст, алгоритм может вернуть ещё и пустой список. Таким образом, для начального условия метод возвращает результат при n ≤ 1.
Для вывода рекурсивного условия декомпозиция должна уменьшать размер задачи на 1, когда наименьший элемент списка исключается из него. Это можно сделать двумя способами. Во-первых, элемент можно менять местами с первым элементом списка. Это, естественно, не меняет результата (сортированного списка), но позволяет после обмена местами исключить первый элемент списка. Поэтому если входной список [7, 5, 3, 8, 4], он превращается в [3, 5, 7, 8, 4] после обмена местами 3 и 7. В этом случае входом подзадачи размера n - 1 был бы список [5, 7, 8, 4], а рекурсивная схема для этого частного примера могла бы быть такой:
Чтобы решить исходную задачу, рекурсивное правило должно добавить исключённый наименьший элемент ([3]) в начало выходного списка подзадачи (заметьте, что результаты - это сортированные списки). В примере 4.13 приведена реализация метода с использованием функции min() для определения наименьшего значения в списке, метода index(), возвращающего позицию элемента в списке, и операции + (конкатенация) для объединения списков. Важной деталью этого алгоритма является то, что он должен создать новую копию входного списка (в строке 5), чтобы не изменить его при вызове метода. В частности, без этой копии метод поменял бы местами первый и наименьший элементы списка.
1 2 3 4 5 6 7 8 9 10 11 |
def select_sort_rec(a): if len(a) <= 1: return a else: b = list(a) min_index = b.index(min(b)) aux = b[min_index] b[min_index] = b[0] b[0] = aux return [aux] + select_sort_rec(b[1:]) |
Другой способ уменьшения размера задачи - исключение наименьшего элемента прямым удалением его из списка. В этом случае рекурсивная схема была бы такой:
Её единственное отличие от предыдущей схемы - порядок следования элементов во входном параметре подзадачи. Но он совершенно не влияет на рекурсивное правило, где также нужно добавлять удалённый наименьший элемент ([3]) к списку вывода подзадачи. В примере 4.14 приведена возможная реализация функции, использующая для удаления наименьшего элемента метод remove(). В строке 5 также создаётся копия входного списка, чтобы не изменить его очередным вызовом метода.
1 2 3 4 5 6 7 8 9 |
def select_sort_rec_alt(a): if len(a) <= 1: return a else: b = list(a) n = min(b) b.remove(n) return [n] + select_sort_rec_alt(b) |
Наконец, оценка времени выполнения этих алгоритмов задаётся формулой (3.24), так как поиск (и удаление) наименьшего элемента списка требует порядка n операций. Таким образом, алгоритмы работают за время Θ(n2).
На следующем шаге мы рассмотрим схему Горнера.