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

А вот как выглядит программный код быстрой сортировки:
Б
def quicksort(array):
if len(array) < 2:
return array <
else:
pivot = array[0] -< Рекурсивный случай
less = [i for i in array[l:] if i <= pivot] ■<■■■
азовый случай: массивы с О и 1 элементом уже "отсортированы"
Подмассив всех элементов, ' меньших опорного
greater = [i for i in array[l:] if i > pivot] ■< Подмассив всех элементов,
^{r J} больших опорного
return quicksort(less) + [pivot] + quicksort(greater) print quicksort([10, 5, 2, 3])
Снова об «О-большом»
А
ПРИМЕР БИНАРНЫЙ ПРОСТОЙ
АЛГОРИТМА: "ОИСК ПОИСК


БЫСТРАЯ
СОРТИРОВКА


СОРТИРОВКА ЗАДАЧА О КОМ­ВЫБОРОМ МИВОЯЖЕРЕ



100
1000


0.6 с 1с


1(Й с Щ с


664-с ЯЯбс


1ь.6 мин
21Л час


2-4*10^

лгоритм быстрой сортировки уникален тем, что его скорость зависит от выбора опорного элемента. Прежде чем рассматривать быструю сорти­ровку, вспомним наиболее типичные варианты времени выполнения для «О-большое».
Оценки для медленного компьютера, выполняющего 10 операций в секунду
На графиках приведены примерные оценки времени при выполнении 10 операций в секунду. Они не претендуют на точность, а всего лишь дают
представление о том, насколько различается время выполнения. Конечно, на практике ваш компьютер способен выполнять гораздо больше 10 опера­ций в секунду.
Для каждого времени выполнения также приведен пример алгоритма. Возьмем алгоритм сортировки выбором, о котором вы узнали в главе 2. Он обладает временем 0(п²), и это довольно медленный алгоритм.
Другой алгоритм сортировки — так называемая сортировка слиянием — работает за время 0(п log п). Намного быстрее! С быстрой сортировкой дело обстоит сложнее. В худшем случае быстрая сортировка работает за время 0(п²).
Ничуть не лучше сортировки выбором! Но это худший случай, а в среднем быстрая сортировка выполняется за время 0(п log п). Вероятно, вы спро­сите:

• 
  что в данном случае понимается под «худшим» и «средним» случаем?
  
• 
  если быстрая сортировка в среднем выполняется за время 0(п log п), а сортировка слиянием выполняется за время 0(п log п) всегда, то по­чему бы не использовать сортировку слиянием? Разве она не быстрее?
  

Сортировка слиянием и быстрая сортировка
Допустим, у вас имеется простая функция для вывода каждого элемента в списке:
def print_items(list): for item in list: print item
Эта функция последовательно перебирает все элементы списка и выво­дит их. Так как функция перебирает весь список, она выполняется за вре­мя 0(п). Теперь предположим, что вы изменили эту функцию и она делает секундную паузу перед выводом:
from time import sleep def print_items2(list): for item in list: sleep(l) print item
П
В 10


priht-/terns : 2 4-6 В
print<П»Ш> 2 <ПША>


4-<пауза>


6 <ПАУЗА>


S 10

еред выводом элемента функция делает паузу продолжительностью в 1 секунду. Предположим, вы выводите список из пяти элементов с ис­пользованием обеих функций:
Обе функции проходят по списку один раз, и обе выполняются за вре­мя 0(п). Как вы думаете, какая из них работает быстрее? Я думаю, print_ items работает намного быстрее, потому что она не делает паузу перед вы­водом каждого элемента. Следовательно, даже при том, что обе функции имеют одинаковую скорость «О-большое», реально print_items работает быстрее. Когда вы используете «О-большое» (например, О(п)), в действи­тельности это означает следующее:
c*h
v
ФИКСИРОВАННЫ* ПРОМЕЖУТОК ВРЕМЕНИ
J-
Здесь с — некоторый фиксированный промежуток времени для вашего алгоритма. Он называется константой. Например, время выполнения может составлять 10миллисекунд * п для print_items против 1 секунды * п для print_items2.
Обычно константа игнорируется, потому что если два алгоритма имеют разное время «О-большое», она роли не играет. Для примера возьмем би­нарный и простой поиск. Допустим, такие константы присутствуют в обоих алгоритмах.
Л
ПРОСТО* поиск


БИНАРНЫ* ПОИСК

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