На этом шаге мы рассмотрим рекурсивное решение этой задачи.

    В этой задаче сортировки (скажем, по возрастанию) входом является список a из n элементов, которые можно отсортировать операцией ≤ (или некоторой функцией, позволяющей сравнивать элементы, реализуя полное бинарное отношение следования), а выходом - логическое значение, которое можно выразить как

   n-2            
   ∧ (ai ≤ ai+1) .       (6.1)
   i=0            

    Таким образом, результат равен True, если элементы списка располагаются (не строго) в возрастающем или неубывающем порядке.

    Размер этой задачи - количество элементов списка. Если список содержит один элемент, то результат - очевидно, True. Кроме того, можно считать, что пустой список тоже упорядочен.

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

    f(a) = (а0 ≤ а1) ∧ ... ∧ (а⌊n/2⌋-2 ≤ а⌊n/2⌋-1)  {подзадача 1}
           ∧
           (а⌊n/2⌋-1 ≤ а⌊n/2⌋) ∧ (а⌊n/2⌋ ≤ а⌊n/2⌋+1) ∧ ... ∧ (аn-2 ≤ аn-1) {подзадача 2}

    Очевидно, если весь список отсортирован по возрастанию, то обе его половины тоже должны быть отсортированы по возрастанию. Таким образом, метод может вызвать себя дважды с двумя соответствующими подсписками и выполнить логическую операцию И с их результатами. Наконец, объединение результатов подзадач требует дополнительного шага. В частности, последний элемент первого подсписка а_⌊n/2⌋-1 должен быть не больше первого элемента второго подсписка а_⌊n/2⌋. Это условие также требует ещё одной операции И в рекурсивном условии. В примере 6.1 приведена возможная реализация метода, который работает за время Ο(n), поскольку его стоимость вычисления:

            1,           если n ≤ 1
    T(n) = 
            2T(n/2) + 1, если n > 1

def is_list_sorted(a):
    n = len(a)
    if n <= 1:
        return True
    else:
        return (is_list_sorted(a[0:n // 2]) and    
                a[n // 2 - 1] <= a[n // 2] and    
                is_list_sorted(a[n // 2:n]))

    Со следующего шага мы начнем рассматривать алгоритм сортировки.

Предыдущий шаг Содержание Следующий шаг