На этом шаге рассмотрим быструю сортировку.
Быстрая сортировка относится к алгоритмам сортировки. Она работает намного быстрее сортировки выбором и часто применяется в реальных программах. Например, в стандартную библиотеку С входит функция с именем qsort, реализующая быструю сортировку. Быстрая сортировка также основана на стратегии "разделяй и властвуй".
Воспользуемся быстрой сортировкой для упорядочения массива. Как выглядит самый простой массив, с которым может справиться алгоритм сортировки? Некоторые массивы вообще не нуждаются в сортировке.
Пустые массивы и массивы, содержащие всего один элемент, станут базовым случаем. Такие массивы можно просто возвращать в исходном виде - сортировать ничего не нужно:
def quicksort(arr): if len(arr) < 2: return arr
Теперь перейдем к массивам большего размера. Массив из двух элементов тоже сортируется без особых проблем.
А как насчет массива из трех элементов?
Помните: мы используем стратегию "разделяй и властвуй". Следовательно, массив должен разделяться до тех пор, пока мы не придем к базовому случаю. Алгоритм быстрой сортировки работает так: сначала в массиве выбирается элемент, который называется опорным.
О том, как выбрать хороший опорный элемент, мы еще поговорим. А пока предположим, что опорным становится первый элемент массива. Теперь мы находим элементы, меньшие опорного, и элементы, большие опорного.
Этот процесс называется разделением. Теперь у вас имеются:
- подмассив всех элементов, меньших опорного;
- опорный элемент;
- подмассив всех элементов, больших опорного.
Два подмассива не отсортированы - они просто выделены из исходного массива. Но если бы они были отсортированы, то провести сортировку всего массива было бы несложно.
Если бы подмассивы были отсортированы, то их можно было бы объединить в порядке "левый подмассив - опорный элемент - правый подмассив" и получить отсортированный массив. В нашем примере получается [10, 15] + [33] + [] = [10, 15, 33], то есть отсортированный массив.
Как отсортировать подмассивы? Базовый случай быстрой сортировки уже знает, как сортировать массивы из двух элементов (левый подмассив) и пустые массивы (правый подмассив). Следовательно, если применить алгоритм быстрой сортировки к двум подмассивам, а затем объединить результаты, получится отсортированный массив!
На следующем шаге продолжим рассматривать быструю сортировку.
