Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - страница 19

Следовательно, вы можете отсортировать массив из четырех элементов. А если вы можете отсортировать массив из четырех элементов, то вы также можете отсортировать массив из пяти элементов. Почему? Допустим, имеется массив из пяти элементов.

Вот как выглядят все варианты разделения этого массива в зависимости от выбранного опорного элемента:

Все эти подмассивы содержат от 0 до 4 элементов. А вы уже знаете, как отсортировать массив, содержащий от 0 до 4 элементов, с использованием быстрой сортировки! Таким образом, независимо от выбора опорного элемента вы можете рекурсивно вызывать быструю сортировку для двух подмассивов.

Например, предположим, что в качестве опорного выбирается элемент 3. Вы применяете быструю сортировку к подмассивам.

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

Итак, решение работает независимо от выбора опорного элемента. Следовательно, вы можете отсортировать массив из пяти элементов. По той же логике вы можете отсортировать массив из шести элементов и т.д.

доказательство по индукции

Вы только что познакомились с методом доказательства по индукции! Это один из способов, доказывающих, что ваш алгоритм работает. Каждое индуктивное доказательство состоит из двух частей: базы (базового случая) и индукционного перехода. Звучит знакомо? Допустим, я хочу доказать, что могу подняться на самый верх стремянки. Если мои ноги стоят на ступеньке, то я могу переставить их на следующую ступеньку, — это индукционный переход. Таким образом, если я стою на ступеньке 2, то могу подняться на ступеньку 3. Что касается базового случая, я сейчас стою на ступеньке 1. Из этого следует, что я могу подняться на самый верх стремянки, каждый раз поднимаясь на одну ступеньку.

Аналогичные рассуждения применимы к быстрой сортировке. Работоспособность алгоритма для базового случая — массивов с размером 0 и 1 — была продемонстрирована. В индукционном переходе я показал, что если быстрая сортировка работает для массива из 1 элемента, то она будет работать для массива из 2 элементов. А если она работает для массивов из 2 элементов, то она будет работать для массивов из 3 элементов и т.д. Из этого можно сделать вывод, что быстрая сортировка будет работать для всех массивов любого размера. Я не буду подробно рассматривать доказательства по индукции, но это интересный метод, который идет рука об руку со стратегией «разделяй и властвуй».

А вот как выглядит программный код быстрой сортировки:

def quicksort(array):

  if len(array) < 2:

    return array      

  else:

    pivot = array[0]  

    less = [i for i in array[1:] if i < pivot]

    greater = [i for i in array[1:] if i > pivot]

    return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

Алгоритм быстрой сортировки уникален тем, что его скорость зависит от выбора опорного элемента. Прежде чем рассматривать быструю сортировку, вспомним наиболее типичные варианты времени выполнения для «O-большое».

Оценки для медленного компьютера, выполняющего 10 операций в секунду

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

Для каждого времени выполнения также приведен пример алгоритма. Возьмем алгоритм сортировки выбором, о котором вы узнали в главе 2. Он обладает временем O(n2), и это довольно медленный алгоритм.

Другой алгоритм сортировки — так называемая сортировка слиянием — работает за время O(n log n). Намного быстрее! С быстрой сортировкой дело обстоит сложнее. В худшем случае быстрая сортировка работает за время O(n2).

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