Page 93 - Bkhargava_-_Grokaem_algoritmy

92 Глава 4. Быстрая сортировка

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

def quicksort(array):
if len(array) < 2: 6aюв1o1iii CJ1yчai: массивы с О и 1 эпементом
return array " ................ . уже "отсортированы"
else:
pivot = array[0] " " .......... " .. Рекурсивный СJ1учай
less = [i for i in array[l : ] if i <• pivot] ..С· · · ········· · · Подмассмв всех эпементов,
меньших опорного
greater " [ i for i in array [ 1 : ] i f i > pi vot] ..С· ....... ... Подмассмв всех эпементов,
боnьwмх опорного
return quicksort(less) + [pivot] + quicksort(greater)

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

Снова об «О-большом»

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

SllHAPHЫA
ПPllMEP ПРОСТОА SЫC.TPAJI C.OPTllPO&KA ~UАЧА О КОМ-
AЛrOPllTMA: ПOllC.K ПOllC.K C.OPTllPO&KA &ЫБОРОМ MllllOJl~EPE
l=~lLLLL

PAJMEP 0~)
MAc.C.ll&A O(l~ i.) O(r- ~h) • O(rt) Q(n!)
1~ .fl.3 с. 1 с. 3.Зс 19} с 4: Z.а.ня
19)ф (1.ьс 1~ с. 6~А- с. 1&.6 MllH 2.<J )( 1Р\~Е.Т
10~~ 1с. 1910 с. <f't6 с 2":#.~ ЧАС 1.Z:fy,!o~ЛsE'т

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

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

www.trk.kg