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

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

def quicksort(array):

  if len(array) < 2:

    return array         Базовый случай: массивы с 0 и 1 элементом уже "отсортированы"

  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-большом»

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

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

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

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

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

Ничуть не лучше сортировки выбором! Но это худший случай, а в среднем быстрая сортировка выполняется за время O(n log n). Вероятно, вы спросите:

• что в данном случае понимается под «худшим» и «средним» случаем?

• если быстрая сортировка в среднем выполняется за время O(n log n), а сортировка слиянием выполняется за время O(n log n) всегда, то почему бы не использовать сортировку слиянием? Разве она не быстрее?

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

Допустим, у вас имеется простая функция для вывода каждого элемента в списке:

def print_items(list):

  for item in list:

    print item

Эта функция последовательно перебирает все элементы списка и выводит их. Так как функция перебирает весь список, она выполняется за время O(n). Теперь предположим, что вы изменили эту функцию и она делает секундную паузу перед выводом:

from time import sleep

def print_items2(list):

  for item in list:

    sleep(1)

    print item

Перед выводом элемента функция делает паузу продолжительностью в 1 секунду. Предположим, вы выводите список из пяти элементов с использованием обеих функций:

Обе функции проходят по списку один раз, и обе выполняются за время O(n). Как вы думаете, какая из них работает быстрее? Я думаю, print_items работает намного быстрее, потому что она не делает паузу перед выводом каждого элемента. Следовательно, даже при том, что обе функции имеют одинаковую скорость «O-большое», реально print_items работает быстрее. Когда вы используете «O-большое» (например, O(n)), в действительности это означает следующее:

Здесь c — некоторый фиксированный промежуток времени для вашего алгоритма. Он называется константой. Например, время выполнения может составлять 10 миллисекунд * n для print_items против 1 секунды * n для print_items2.

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

Первая реакция: «Ого! У простого поиска константа равна 10 миллисекундам, а у бинарного поиска – 1 секунда. Простой поиск намного быстрее!» Теперь предположим, что поиск ведется по списку из 4 миллиардов элементов. Время будет таким:

Как видите, бинарный поиск все равно работает намного быстрее. Константа ни на что не повлияла.

Однако в некоторых случаях константа может иметь значение. Один из примеров такого рода — быстрая сортировка и сортировка слиянием. У быстрой сортировки константа меньше, чем у сортировки слиянием, поэтому, несмотря на то что оба алгоритма характеризуются временем O(n log n), быстрая сортировка работает быстрее. А на практике быстрая сортировка работает быстрее, потому что средний случай встречается намного чаще худшего.

А теперь ответим на первый вопрос: как выглядит средний случай по сравнению с худшим?

Средний и худший случай

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

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

Стек намного короче! Массив каждый раз делится надвое, поэтому такое количество рекурсивных вызовов излишне. Вы быстрее добираетесь до базового случая, и стек вызовов получается более коротким.

Первый из рассмотренных примеров описывает худший сценарий, а второй — лучший. В худшем случае размер стека описывается как O(n). В лучшем случае он составит O(log n).

Теперь рассмотрим первый уровень стека. Один элемент выбирается опорным, а остальные элементы делятся на подмассивы. Вы перебираете все восемь элементов массива, поэтому первая операция выполняется за время O(n). На этом уровне стека вызовов вы обратились