Объяснение быстрой сортировки менее чем за 5 минут

Объяснение самого быстрого алгоритма сортировки, быстро

В области сортировки король - быстрая сортировка!

Quicksort - это рекурсивный алгоритм «разделяй и властвуй», который считается самым быстрым в своем классе. Он может похвастаться средней временной сложностью O (n log n) (в нотации big-o), что по сравнению с его аналогами довольно быстро. Нотация Big-O - это способ измерения того, насколько хорошо алгоритм масштабируется или работает по мере увеличения объема данных, которые он обрабатывает.

Ниже приведена диаграмма быстрой сортировки по сравнению с лучшими алгоритмами сортировки. Как видите, он идет первым:

Это делает быструю сортировку фаворитом на собеседованиях на доске и обязательным требованием для любого начинающего программиста. В этой статье мы объясним, как это работает, используя JavaScript в качестве основного языка.

Как это работает?

Quicksort использует точку поворота, значение, которое часто определяется как средний или последний элемент массива. Алгоритм сравнивает каждый элемент массива с точкой поворота, перестраивая каждый так, чтобы значения на одной стороне (слева) были меньше, а значения на другой стороне (справа) больше. Затем он разделяет обе стороны и рекурсивно запускает один и тот же процесс на каждой стороне, пока массив не будет отсортирован.

Это помогает увидеть алгоритм, а затем понять, что внутри него происходит:

Возьмем, например, следующий массив: originalArray = [4, 5, 1, 3, 2]

• Мы можем установить точку поворота как последний элемент 2: pivot = 2.
• Затем мы сравниваем первый элемент этого массива с точкой поворота: 4 ≤ 2?
• Помните, что мы хотим переместить все элементы, которые меньше точки поворота, влево от него и сделать противоположное с правой стороны. Поскольку 4 больше 2, мы помещаем его в новый массив с именем rightSide: rightSide = [4]
• Проделаем то же самое с 5: 5 ≤ 2? Нет, итак: rightSide=[4, 5]
• 1 ≤ 2? Да, поэтому мы перемещаем его в массив с именем leftSide: leftSide = [1]
• 3 ≤ 2? No => rightSide=[4, 5, 3]
• Мы достигли конца массива, поэтому прекращаем цикл.

Пока у нас есть:

leftSide = [1], pivot = 2, and rightSide = [4, 5, 3]

Возвращаясь к правой стороне, мы имеем:

• Наша новая точка поворота теперь равна 3: pivot = 3
• 4 ≤ 3? No, => `5 ≤ 3? No, => rightSide = [4, 5]
• leftSide = [] (поскольку ни один элемент не был меньше 3)

leftSide = [], pivot = 3, rightSide = [4, 5]

Продолжаем рекурсию в правую часть:

• pivot = 5
• 4 ≤ 5? Да, = ›leftSide = [4]
• rightSide = []

leftSide = [4], pivot = 5, rightSide = []

Теперь мы рекурсивно пытаемся отсортировать левую часть:

• Поскольку массив leftSide содержит только один элемент, сортировать нечего, поэтому мы возвращаем его.

Возврат из рекурсии

Учитывая, что базовый случай для массива rightSide был достигнут, функция будет возвращаться через каждую рекурсию. В каждой рекурсии будет сформирован новый массив (newArray) с использованием возвращаемых значений leftSide, pivot и rightSide в указанном порядке.

Таким образом, получаем следующее:

• Третья глубина рекурсии: помните, что рекурсия произошла в массиве rightSide. Следовательно, имеем: return newArray([1], 2, [4, 5])
• Вторая глубина рекурсии: return newArray([1], 2, [3, 4, 5])
• Первая глубина рекурсии: return newArray([1, 2, 3 , 4, 5])

Мы можем резюмировать алгоритм в псевдокоде следующим образом:

• Установите точку поворота как последний элемент в массиве.
• Сравните крайний левый элемент с точкой поворота - если она больше точки поворота, вставьте его в новый массив с именем right. Сделайте обратное для левой стороны.
• Рекурсивно перебирайте левый и правый массивы, пока не дойдете до последнего элемента, и в этом случае его длина будет 1. Затем вы возвращаете это значение.
• Функция развернет рекурсию с обеих сторон, сортируя каждую сторону в процессе, так что последнее возвращаемое значение станет полностью отсортированным массивом.

Вот два самых коротких, но лучших объяснения алгоритма быстрой сортировки, которые я смог найти. Очень рекомендую посмотреть их:

Алгоритм, который мы рассмотрели в этой статье, возможно, является одним из самых простых и интуитивно понятных для быстрой сортировки. Однако есть много подходов к быстрой сортировке, которые дают различные характеристики на диаграмме сложности big-O. Вы можете ознакомиться с приведенными ниже ресурсами, если хотите их изучить: