Page 88 - Bkhargava_-_Grokaem_algoritmy

Быстрая сортировка 87

ЧИСЛА, ЧИСЛА, БОЛЬ/КИЕ. 33
ME.Hbll!ME. 33 (ПУСТОК М~ССМ&)

[ts \1Ф-\ ~ l.s]

f
ОПОРНЬIК
ЭЛЕ.МЕ.НТ

Этот процесс называется разделением. Теперь у вас имеются:

1:1 подмассив всех элементов, меньших опорного;

о опорный элемент;
о подмассив всех элементов, больших опорного.

Два подмассива не отсортированы - они просто выделены из исходного
массива. Но если бы они бъuiu отсортированы, то провести сортировку всего
массива было бы несложно.

Если бы подмассивы были отсортированы, то их можно было бы объеди­
нить в порядке ~левый подмассив - опорный элемент - правый подмас­
сив» и получить отсортированный массив. В нашем примере получается
[ 10, 15] + [ 33] + [] = [ 10, 15, 33], то есть отсортированный массив.
Как отсортировать подмассивы? Базовый случай быстрой сортировки
уже знает, как сортировать массивы из двух элементов (левый подмассив)
и пустые массивы (правый подмассив). Следовательно, если применить
алгоритм быстрой сортировки к двум подмассивам, а затем объединить
результаты, получится отсортированный массив!

quicksort([lS, 10]) + [33) + quicksort([])
> [ 10, 15, 33] .,.." Отсортированный массив

www.trk.kg