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

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

Быстрая сортировка относится к алгоритмам сортировки. Она работает намного быстрее сортировки выбором и часто применяется в реальных программах. Например, в стандартную библиотеку C входит функция с именем qsort, реализующая быструю сортировку. Быстрая сортировка также основана на стратегии «разделяй и властвуй».

Воспользуемся быстрой сортировкой для упорядочения массива. Как выглядит самый простой массив, с которым может справиться алгоритм сортировки (помните подсказку из предыдущего раздела)? Некоторые массивы вообще не нуждаются в сортировке.

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

def quick sor t(array):

  if len(array) < 2:

    return array

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

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

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

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

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

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

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

• опорный элемент;

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

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

Если бы подмассивы были отсортированы, то их можно было бы объединить в порядке «левый подмассив — опорный элемент — правый подмассив» и получить отсортированный массив. В нашем примере получается [10, 15] + [33] + [] =  [10, 15, 33], то есть отсортированный массив.

Как отсортировать подмассивы? Базовый случай быстрой сортировки уже знает, как сортировать массивы из двух элементов (левый подмассив) и пустые массивы (правый подмассив). Следовательно, если применить алгоритм быстрой сортировки к двум подмассивам, а затем объединить результаты, получится отсортированный массив!

quicksort([15, 10]) + [33] + quicksort([])

> [10, 15, 33]        Отсортированный массив

Этот метод работает при любом опорном элементе. Допустим, вместо 33 в качестве опорного был выбран элемент 15.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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