Знаменитая быстрая сортировка. В этой статье разберемся как она работает и насколько же она быстра.
Описание:
Быстрая сортировка похожа на алгоритм сортировки слиянием. Она так же основана на принципе «разделяй и властвуй» и использует рекурсию. Отличие заключается в том, что сортируемый массив разделяется на две части относительно какого-то элемента, который называют опорным. При этом в левой половине содержатся все элементы меньшие опорного, а в правой – большие.
Вопрос: Куда мы денем элементы равные опорному?
Конечно, мы можем засунуть эти элементы в любую из половин, но есть смысл слегка модифицировать алгоритм. Добавим третью половину третий массив, в который и поместим все что равно опорному элементу, включая его самого. Зачем? Раз мы все равно нашли элементы равные опорному то зачем их дальше сортировать.
Как мы выбираем опорный элемент? В ранних реализациях брали просто первый элемент, но если массив уже отсортирован, то это сильно снижало производительность. Лучшим вариантом будет выбрать средний элемент массива или случайный. Самым лучшим вариантом будет медиана всех значений, но это достаточно долгий процесс для включения ее в алгоритм сортировки.
Блок-схема:
Программная реализация на языке Python 3.7:
Алгоритмическая сложность:
Примем что в центральной части всегда один элемент и длина массива равна n, тогда в лучшем случае мы проходимся по всему массиву и делим его на примерно равные Левую и Правую части. Проход по всем элементам у нас займет логичные n-операций. Вспоминая уже рассмотренные случаи (1,2), мы знаем, что глубина рекурсии составит log(n). На каждом уровне рекурсии мы полностью проходим по массиву, а значит итоговая сложность – O(n*log(n))
Но в случае если в качестве опорного мы выберем наибольший или наименьший элемент массива, то мы будем делить наш массив на два - 1 и n-1 элементов. Тогда глубина рекурсии достигнет значения n. Итоговая сложность возрастёт до O(n2), но самое плохое - такая глубина рекурсии может привести к исчерпанию памяти (исчерпанию стэка) во время выполнения программы и её отказу(ошибке).
В коде мы выбирали опорный элемент случайно и вот следующий график иллюстрирует скорость работы алгоритма при сортировке одного и того же массива при разных(а возможно и нет, это же рандом) D.
Видно что от выбора опорного элемента скорость может сильно меняться. По-этому говорять что быстрая сортировка имеет вероятностный характер сложности.
Сравним нашу сортировку с другими:
Получается быстрая сортировка не такая уж и быстрая? Не совсем так, здесь рассмотрен случай сортировки уже отсортированного массива, а мы уже обсуждали выше что в таком случае сложность алгоритма может возрасти. Но при сортировке случайных не отсортированных элементов:
Получаем довольно уверенную победу!