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

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

В этой статье сначала исследуем принцип или стратегию "Разделяй и властвуй" – это хорошо известный рекурсивный метод решения задач. О рекурсии в прошлой статье можно прочитать здесь.

Сам алгоритм не особенно полезен если он решает только задачу одного типа. Стратегия "Разделяй и властвуй" помогает выработать новый подход к решению задач. Сначала стоить понять в чём заключается эта стратегия и такой подход и концу статьи рассмотрим алгоритм быстрой сортировки. Этот алгоритм работает намного быстрее сортировки выбором(о сортировке выбором в этой статье). Также алгоритм быстрой сортировки является хорошим примером элегантного способа решения задачи и написании элегантного кода.

Стратегия "Разделяй и властвуй"

Для начала рассмотрим три примера. Сначала разберём наглядный пример. Потом разберём пример кода, который выглядит не изящно, но, пожалуй воспринимается проще. И в третьем примере уже рассмотрим алгоритм быстрой сортировки, использующий стратегию "разделяй и властвуй".

Представьте, что вы владеете земельным участком размером 1680 метров на 640 метров. Вы хотели бы разделить землю на одинаковые квадратные участки. Участки должны быть настолько большими, насколько это возможно. Как определить наибольший размер квадратного участка? Воспользоваться стратегией "разделяй и властвуй"! Решение задачи будет состоять из двух шагов:

1. Определить базовый случай. Это должен быть простейший случай из всех возможных.
2. Задача делиться или сокращается до тех пор, пока не будет сведена к базовому случаю.

А теперь воспользуемся стратегией "разделяй и властвуй" для решения задачи. Каков самый большой размер квадрата который может получиться? Для начала нужно определить базовый случай. Самая простая ситуация это если длина одной стороны кратна длине другой стороны. Предположим, длина одной стороны составляет 25м, а длина другой 50м. В этом случае размер самого большого участка составит 25м x 25м, и надел после деления будет состоять из двух таких участков. Теперь нужно вычислить рекурсивный случай. В соответствии со стратегией при каждом рекурсивном случае задача должна сокращаться. Как сократить эту задачу? Для начала разместим самые большие участки, которые можно использовать. По длине получится расположить два квадратных участка 640x640 метров и останется не распределённой земля в 400 метров. Тут и наступает что называется "момент истинны". Нераспределённый остаток – это тоже надел земли, который нужно распределить. К нему можно также применить такой же алгоритм. Получается что нужно разделить теперь оставшийся меньший участок размером 640 x 400 метров. Если будет найден этот самый большой участок для остатка, то мы найдем решение для всего размера земли.

"Если будет найден этот самый большой участок для остатка, то мы найдем решение для всего размера земли. В доказательство поищите алгоритм Евклида."

Если дальше делить участок размером 640 на 400 метров, то размеры самого большого квадрата, который можно создать, составляют 400x400 метров. Останется после этого ещё меньший нераспределённый участок размером 400x240 метров. Отсекая поделенную часть, мы приходим к ещё меньшему размеру сегмента, 240x160 метров. После очередного "отсечения" получается ещё меньший сегмент земли. И наконец, мы придём к базовому случаю: 160 на 80. Если разбить этот сегмент на два квадрата 80 на 80, то ничего лишнего уже не останется! Итак, для исходного размера земли (1680 метров на 640 метров) самый большой размер участка будет равен 80 на 80 метров.

Рассмотрим ещё один пример. Имеется массив чисел: 3, 4, 6. Нужно написать код, чтобы просуммировать все числа и вернуть сумму. Сделать это можно с помощью функции например так:

def summ(arr):
  total = 0
  for x in arr:
    total += x
  return total
 
print(summ([3, 4, 6]))

А как сделать то же самое, но уже с помощью рекурсивной функции? Пункт 1: определить базовый случай. Как выглядит самый простой массив, который можно получить? Если будет массив с 0 или 1 элементом, то сумму достаточно просто получить.

Если нужно написать рекурсивную функцию в которой будет задействован массив, то базовым случаем очень часто будет пустой массив или массив из одного элемента.

Пункт 2: каждый рекурсивный вызов должен приближать вас к пустому массиву. Как уменьшить размер задачи? Один из возможных способов:

summ([3, 4, 6]) # => 13
3 + summ([4, 6]) # => 13

Во втором случае функции summ передаётся меньший массив, а результат остаётся такой же. А это означает что мы таким образом сократили размер задачи! Функция summ может работать по следующему правилу или схеме:

1. Функция получает список
2. Если список пуст, вернуть 0. А иначе результат должен быть равен сумме первого элемента массива и суммы остальных элементов массива.

Вот как это выглядит(не забывайте, что при рекурсии сохраняется состояние переменных):

Немного о функциональном программировании. Зачем применять рекурсию, если задачу можно легко решить циклом? Дело в том, что например в языках функционального программирования(Haskell, Lisp, Erlang, APL) циклов не существует, поэтому для написания подобных задач приходится применять рекурсию. Если вы хорошо поймёте рекурсию, вам будет проще работать с функциональными языками программирования. Если вам нравится рекурсия присмотритесь к таким языкам как Haskell, R, F#, Clojure, Scala, Erlang.

Вот ещё код для пары примеров похожих задач:

# Рекурсивная функция для подсчёта элементов в списке
def count(m_list):
  if m_list == []:
    return 0
  return 1 + count(list[1:]) 

# Рекурсивная функция для нахождения наибольшего числа в списке
def maxx(m_list):
  if len(m_list) == 2:
    return m_list[0] if m_list[0] > m_list[1] else m_list[1]
  s_max = maxx(m_list[1:])
  return m_list[0] if m_list[0] > s_max else s_max

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

Быстрая сортировка относится к алгоритмам сортировки и она работает намного быстрее сортировки выбором и часто применяется в реальных прогрпаммах. Быстрая сортировка основана на стратегии "разделяй и властвуй". Воспользуемся быстрой сортировкой для упорядочения массива. Как выглядит самый простой массив, с которым может справиться алгоритм сортировки? Некоторые массивы вообще не нуждаются в сортировке, например: пустой или с одним элементом – они базовый случай. Массивы с одним элементом или пустые нужно сразу возвращать:

def quicksort(arr):
  if len(arr) < 2:
    return arr

Рассмотрим далее массивы большего размера. Массив из двух элементов тоже сортируется без особых проблем. Сравнить нужно только два элемента – если первый меньше второго, значит меняем их местами. А если массив состоит из трёх элементов? То массив уже должен разделяться до тех пор, пока мы не придём к базовому случаю.

Алгоритм быстрой сортировки работает так: сначала в массиве выбирается элемент, который называется опорным. О том как выбирается опорный элемент будет написано далее. Пока предположим, что опорным становится 30 как первый элемент массива: [30, 15, 10]. Теперь нужно найти элементы меньше опорного и больше опорного. Числа меньше опорного это [15, 10], а больше опорного это пустой массив []. Этот процесс называется разделением. Теперь у нас есть:

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

Два подмассива не отсортированы – они просто выделены из исходного массива. Но если бы они были отсортированы, то провести сортировку всего массива было бы несложно. Если подмассивы отсортированы, то их можно просто объединить в порядке: левый подмассивы – опорный элемент – правый подмассив. В примере получилось бы так: [10, 15] + [30] + [] = [10, 15, 30], таким образом получился бы отсортированный массив.

Как отсортировать подмассивы? Нужно применить алгоритм сортировки с базовым и рекурсивным случаем к двум подмассивам, а как только наступит базовый случай – объединить результаты вычислений, получив итоговый отсортированный массив! Это выглядит для примера выше так: quicksort([15, 10]) + [30] + quicksort([]) # => [10, 15, 30].

Также допустим, что изначально был выбран в качестве опорного элемента – элемент 15. При сравнении получаются два подмассива, которые состоят из одного элемента [10] и [30], а дальше всё то же самое, чтобы их объединить в один итоговый отсортированный массив.

Алгоритм для сортировки массива из трёх элементов следующий:

1. Выбрать опорный элемент
2. Разделить массив на два подмассива: элементы, меньше опорного, и элементы, больше опорного.
3. Рекурсивно применить быструю сортировку к двум подмассивам.

Рассмотрим массив из четырёх элементов? Пусть будет массив: [30, 10, 15, 5]. Предположим, что опорным элементом снова выбрали 30. Тогда левый подмассив: [10, 15, 5]. Далее вы уже узнали как сортируется массив из трёх элементов(рекурсивно применить к нему снова быструю сортировку). Соответственно вы можете отсортировать массив из четырёх элементов и так далее, например из пяти элементов. Почему? Допустим имеется массив из 5 элементов: [3, 5, 2, 1, 4]. Вот как выглядят варианты разделения этого массива в зависимости от выбранного элемента:

1. [] + [1] + [3, 2, 5, 4]
2. [1] + [2] + [3, 5, 4]
3. [2, 1] + [3] + [5, 4]
4. [3, 2, 1] + [4] + [5]
5. [3, 2, 1, 4] + [5] + []

Все эти подмассивы будут содержать от 0 до 4 элементов. И для них выполняется то же самое действие – рекурсивно запускаем алгоритм быстрой сортировки для каждого из подмассивов пока не достигнем базового случая, и наконец просто объединим все подмассивы в один отсортированный массив! Итак, решение работает независимо от выбора опорного элемента. Следуя такой же логике, вы можете отсортировать массив из 6 и более элементов по той же схеме и т.д.

Выше был описан метод доказательство по индукции. Это способ доказательства, что ваш алгоритм рабочий. Каждое индуктивное доказательство состоит из двух частей: базового и индукционного. Подробнее об этом методе вы можете почитать здесь: Математическая индукция. Здесь я лишь упомяну, что это интересный метод доказательства, который согласуется со стратегией "разделяй и властвуй".

Вот как выглядит наш код на Python для быстрой сортировки:

def quicksort(arr):
  if len(arr) < 2:  # базовый случай
    return arr
  # Далее рекурсивный случай
  piv = arr[0]  # опорный элемент
  less = [i for i in arr[1:] if i <= piv]  # подмассив всех элементов меньше или равных опорному
  great = [i for i in arr[1:] if i > piv]  # подмассив всех элементов больше опорного
  return quicksort(less) + [piv] + quicksort(great)  # рекурсивный случай

print(quicksort([10, 5, 30, 15, 20]))  # => [5, 10, 15, 20, 30]

"О-большое"

Алгоритм быстрой сортировки уникален тем, что скорость его зависит от выбора опорного элемента. Вспомним наиболее типовые варианты времени выполнения алгоритмов по концепции "О-большое":

На изображении выше приведены примерные оценки времени выполнения при 10 операциях в секунду. Они не точны, а всего лишь дают представление о том, насколько различается время выполнением того или иного алгоритма. На практике современный ПК конечно способен выполнять гораздо больше чем 10 операций в секунду.

Для каждого времени выполнения приведён также пример алгоритма. В "худшем" случае быстрая сортировка выполняется за время: Другой алгоритм сортировки — сортировка слиянием работает за время: Выходит, что быстрая сортировка ничуть не лучше сортировки выбором! Но это худший случай, а в "среднем" случае быстрая сортировка выполняется за время: Вы можете спросить:

• Что понимать под "худшим" и "средним" случаем?
• Если быстрая сортировка в среднем выполняется за такое же время как и сортировка слиянием. То почему бы не использовать сортировку слиянием всегда? Разве она не быстрее?

Сортировка слиянием

Напишем простую функцию для вывода каждого элемента в списке:

def print_items(myList):
  for item in myList:
    print(item)

Эта функция последовательно переберёт все элементы списка(массива) и выведет их на экран. Так функция перебирает весь список, за время: Предположим далее вы изменили эту функцию и она "засыпает" или делает паузу в работе на 1 секунду перед выводом в консоль элемента списка.

from time import sleep
def print_items_sleep(myList):
  for item in myList:
    sleep(1)
    print(item)

Обе функции проходят по списку один раз, и обе выполняются за время выполнения O(n). Но print_items работает намного быстрее, потому что она не делает паузу перед выводом каждого элемента. Следовательно, при том что обе функции имеют одинаковое "О-большое", реально print_items отрабатывает быстрее! Когда вы используете "О-большое" это означает следующее(для O(n)): Здесь c – некоторый фиксированный промежуток времени для вашего алгоритма. Он называется константой. В функциях из примера время выполнения может составлять 10 миллисекунд * n для print_items против 1,0010 секунды * n для print_items_sleep. Обычно константа игнорируется, потому что если два алгоритма имеют разное время "О-большое", она роли не играет. Для примера возьмём бинарный поиск и простой поиск. Допустим, такие константы присутствуют в обоих алгоритмах: 10мс * n для простого поиска и 1сек * log n для бинарного поиска. На первый взгляд раз константа намного меньше у простого поиска то мы можем подумать что алгоритм быстрее. Но стоит предположить что поиск ведётся по списку из 4 миллиардов элементов. Тогда подставим данные n в формулы мы получим, что время выполнения для простого поиска получится 463 дня, а для бинарного всего лишь 32 секунды(log(4 000 000 000) = 32)!

В некоторых иных случаях константа c может иметь значение. Один из пример — быстрая сортировка и сортировка слиянием. У быстрой сортировки эта константа меньше, чем у сортировки слиянием. Поэтому быстрая сортировка всё равно отработает быстрее чем сортировка слиянием несмотря на "О-большое". И на практике быстрая сортировка срабатывает быстрее, потому что "средний" случай встречается намного чаще "худшего". Что же такое "средний" случай по сравнению с "худшим"?

Средний и худший случай

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

1. [1, 2, 3, 4, 5, 6, 7, 8]
2. [] + [1] + [2, 3, 4, 5, 6, 7, 8]
3. [] + [2] + [3, 4, 5, 6, 7, 8]
4. [] + [3] + [4, 5, 6, 7, 8]
5. [] + [4] + [5, 6, 7, 8]
6. [] + [5] + [6, 7, 8]
7. [] + [6] + [7, 8]
8. [] + [7] + [8]

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

1. [1, 2, 3, 4, 5, 6, 7, 8]
2. [1, 2, 3] + [4] + [5, 6, 7, 8]
3. [1] + [2] + [3] | [5] + [6] + [7, 8]
4. _____________| [ ] + [7] + [8]

Стек в два раза короче! Список элементов каждый раз в два раза короче! И функция быстрее достигает базового случая!

Первый пример это "худший сценарий". Второй – "лучший". В "худшем" случае размер стека описывается как O(n). В "лучшем" случае он составит O(log n). Но каким бы способом не был разделён массив – вы всегда обращаетесь к O(n) его элементам. Получается, что "лучшем" случае весь алгоритм занимает время: В "худшем" случае существуют O(n) уровней стека, поэтому алгоритм занимает время:

А теперь главное: "лучший" случай это "средний" случай. Если вы всегда будите выбирать опорным элементом случайный элемент в массиве, то быстрая сортировка в среднем завершится за время O(n * logn). За одним исключением: если все элементы массива одинаковы, тогда время выполнения будет худшим. Но на сегодняшний день алгоритм быстрой сортировки – один из самых быстрых алгоритмов сортировки, который также является примером для стратегии "разделяй и властвуй".

Попробуйте сами скопировать и запустить код в окне ниже с интерпретатором Python и повторите примеры из статьи чтобы самим увидеть и понять как всё это работает. Для этого в ячейке с кодом нажмите клавиши на клавиатуре Shift+Enter или запустите код через кнопку Run по значку ▶.