Базовый случай для задачи сортировки можно записать так:
Скопировать кодPYTHON
def quick_sort(input_array):
if len(input_array) < 2:
return input_array
Массив уже отсортирован, нужно просто вернуть его.
В качестве базового случая можно выбирать подмассивы и большей длины. Они сортируются произвольным способом.
Теперь рассмотрим массивы большего размера.
Массив из двух элементов отсортировать легко.
Что делать, если массив состоит из трех элементов?
Задача решается с применением стратегии «разделяй и властвуй». Поэтому сведём массив из трёх элементов к базовому случаю.
Сначала в алгоритме быстрой сортировки выделяют опорный элемент.
Есть разные способы его выбрать. В зависимости от выбора опорного элемента может меняться сложность алгоритма.
Предположим, опорный — первый элемент в массиве.
Затем разбиваем массив на три части: в одной части элементы меньшие либо равные опорному, во второй — опорный элемент, в третьей — большие.
Получаем три подмассива:
- Подмассив с элементами меньше либо равными опорному.
- Опорный элемент.
- Подмассив с элементами больше опорного.
В общем случае два подмассива не отсортированы — они просто выделены из исходного массива. Если бы они были отсортированы, провести сортировку всего массива было бы легко. Нам бы понадобилось просто объединить левый подмассив, опорный элемент и правый подмассив.
Нужно объединить подмассивы с опорным элементом: [13, 17] + [35] + [] = [13, 17, 35]. Получится упорядоченный по неубыванию массив.
Как отсортировать подмассивы? Вы уже знаете как сортировать массивы из двух и менее элементов. Чтобы получить отсортированный массив, применим алгоритм быстрой сортировки к двум подмассивам, затем объединим результаты:
Скопировать кодPYTHON
quicksort([17, 13]) + [35] + quicksort ([])
> [13, 17, 35]
Этот метод работает при любом выборе опорного элемента. Например, вместо 35 возьмем 17.
После разделения оба подмассива состоят из одного элемента. Вы умеете сортировать такие массивы. Получается, можно сортировать массивы из трех элементов.
Алгоритм быстрой сортировки работает вне зависимости от выбора опорного элемента. Последовательность действий всегда одинакова:
- Выбираем опорный элемент.
- Делим массив на два подмассива: слева элементы меньше либо равные опорному, справа — больше.
- Применяем быструю сортировку к двум подмассивам и объединяем результат.
Как насчёт массива из четырех элементов?
Предположим, опорным снова выбран элемент 35.
Левый подмассив состоит из трёх элементов. Вы уже знаете, как его отсортировать.
Следовательно, вы сумеете отсортировать массив из четырёх, пяти и даже шести элементов. Теперь вам под силу сортировка массива с любым количеством элементов.
Например, дан массив из пяти элементов.
Так разобьётся массив в зависимости от выбора опорного элемента:
Все эти подмассивы содержат от нуля до четырёх элементов. А вы знаете, как их отсортировать.
Таким образом, независимо от выбора опорного элемента вы можете рекурсивно вызывать быструю сортировку для двух подмассивов.
Возьмём в качестве опорного элемента 5. Применим быструю сортировку к подмассивам.
Подмассивы отсортированы. Теперь из них можно собрать отсортированный массив. Решение работает даже в случае, если в качестве опорного взять элемент 7:
Таким образом, алгоритм работает независимо от выбора опорного элемента.
Так выглядит код быстрой сортировки:
Скопировать кодPYTHON
def quicksort(array):
if len (array) < 2:
return array
else:
pivot = array[0]
less = [i for i in array[1:] if i <= pivot]
greater = [i for i in array[1:] if i > pivot]
return quicksort(less) + [pivot] + quicksort(greater)
Гоша: Отлично! Будем использовать этот алгоритм для обеих задач, которые пришли от Кондратия! Кажется, с его помощью можно отсортировать населённые пункты в соответствии со значением «треш-индекса», и упорядочить жителей по числу нарушений.