Page 87 - Bkhargava_-_Grokaem_algoritmy

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

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

def quick sor t(array):
if len(array) < 2:
return array

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

~ СР~6НИ6~ЕМ Л.6~ ЭЛЕМЕНП.
ЕСЛИ ПЕР&ЫК ЭЛЕМЕНТ МЕНЬШЕ
&ТОРоrо, МЕНЯЕМ И)( МЕСПМИ

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

\ зз lts (1Ф \

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

~

ОПОРНЫК
ЭЛЕМЕНТ

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

www.trk.kg