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

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

1. Выбрать опорный элемент.

2. Разделить массив на два подмассива: элементы, меньшие опорного, и элементы, большие опорного.

3. Рекурсивно применить быструю сортировку к двум подмассивам.

Как насчет массива из четырех элементов?

Предположим, опорным снова выбирается элемент 33.

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

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

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

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

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

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

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

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

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

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

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

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). На этом уровне стека вызовов вы обратились ко всем восьми элементам. Но на самом деле вы обращаетесь к O(n) элементам на каждом уровне стека вызовов!

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

Итак, завершение каждого уровня требует времени O(n).

В этом примере существуют O(log n) (с технической точки зрения правильнее сказать «высота стека вызовов равна O(log n)») уровней. А так как каждый уровень занимает время O(n), то весь алгоритм займет время O(n) * O(log n) = O(n log n). Это сценарий лучшего случая.