Разочарованный обилием непрозрачных и запутанных объяснений, я решил написать свое собственное.

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

Быстрая сортировка — это алгоритм сортировки по принципу "разделяй и властвуй".

Что такое алгоритм сортировки по принципу "разделяй и властвуй"?

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

Вы увидите, что я имею в виду.

Хорошо, а как это работает?

Допустим, у нас есть несортированный массив элементов:

[8, 2, 3, 6, 1, 4]

Быстрая сортировка работает, сначала выбирая элемент pivot. На данный момент мы собираемся сделать это, выбрав последний:

[8, 2, 3, 6, 1, 4]

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

Smaller: [2, 3, 1] Pivot: [4] Larger: [8, 6]

Эти подмассивы называются разделами.

Затем мы применяем тот же процесс к каждому из этих разделов. Для раздела слева снова выберем последний элемент в качестве опорного:

[2, 3, 1]

Затем мы разбиваем остальные элементы на два еще меньших раздела:

Smaller: [] Pivot: [1] Larger: [2, 3]

Хорошо, пока все:

[1] [2, 3] [4] [8, 6]

Вы видите, куда это идет? Быстрая сортировка продолжает применять один и тот же процесс, пока не перейдет к разделам, содержащим отдельные элементы. Покончим с ними:

Smaller: [2] Pivot: [3] Larger: []

Итак, у нас есть:

[1] [2] [3] [4] [8, 6]

И наконец:

Smaller: [] Pivot: [6] Larger: [8]

Это приводит к:

[1] [2] [3] [4] [6] [8]

Эй, посмотри на это! Разбивая исходный массив на все более и более мелкие части, мы приходим к точке, где все в порядке. Вот почему быстрая сортировка — это алгоритм разделяй и властвуй. Процесс сортировки завершен!

Давайте посмотрим на диаграмму, чтобы лучше понять, что произошло. На этот раз мы не будем писать поворотный элемент отдельно:

Сводки выделены зеленым, а разделы, содержащие только один элемент, выделены красным.

Отлично, а как компьютеры на самом деле это делают?

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

Когда мы пишем быструю сортировку с помощью компьютерного кода, мы на самом деле не разделяем массив физически, как это выглядит, как мы делали выше; вместо этого мы просто запоминаем, где начинаются и заканчиваются подмассивы. Здесь есть псевдокод:

function quicksort(array, left, right):
    //Make sure that the partition is large enough to partition.
    if left < right:
        previous_pivot := partition(array, left, right)
        //We call quicksort to the left of the pivot.
        quicksort(array, left, previous_pivot - 1)
        //We then call quicksort to the right of the pivot.
        quicksort(array, previous_pivot + 1, right)
function partition(array, left, right):
    //We choose the rightmost element as the pivot.
    pivot := array[right]
    //This is where the smaller elements will be swapped.
    swap_to := left
    for i := left to right - 1:
        if array[i] < pivot:
            swap array[i] with array[swap_to]
            swap_to := swap_to + 1
    //All of the smaller elements have been moved to the left.
    //We now move the pivot directly to the right of them.
    swap array[right] with array[swap_to]
    //All of the larger elements are now to the right.
    //We return the new index of the pivot.
    return swap_to

Чтобы отсортировать весь массив, мы будем использовать:

quicksort(array, 0, length(array) - 1)

Давайте пошагово рассмотрим, что partition делает с приведенным выше массивом:

[8, 2, 3, 6, 1, 4]

  • Крайний правый элемент выбирается как основной.
  • Определен индекс swap_to, который начинается с крайнего левого элемента (0).
  • Цикл повторяется от самого левого элемента до самого правого элемента.
  • Элементы, которые меньше, чем опорная, заменяются на индекс swap_to.
  • Затем swap_to увеличивается, так что следующий элемент, который меньше точки поворота, перемещается на следующее место.

Рассмотрим, что происходит на каждой итерации цикла. Свопы выделены курсивом:

(swap_to = 0, i = 0): [8, 2, 3, 6, 1, 4] 
(swap_to = 0, i = 1): [2, 8, 3, 6, 1, 4]
(swap_to = 1, i = 2): [2, 3, 8, 6, 1, 4]
(swap_to = 2, i = 3): [2, 3, 8, 6, 1, 4]
(swap_to = 2, i = 4): [2, 3, 1, 6, 8, 4]
(swap_to = 3)

Отлично, поэтому все элементы, которые меньше, чем опорная точка, были перемещены влево. Теперь нам просто нужен последний своп вне цикла:

(swap_to = 3): [2, 3, 1, 4, 8, 6]

Великолепно! Меньшие элементы находятся слева от оси, а большие — справа!

Наконец, возвращается новое местоположение опорной точки, swap_to, так что quicksort знает, где начинаются и заканчиваются разделы.

Теперь, когда массив разбит на разделы, quicksort вызывает себя (это называется рекурсией) для левого и правого разделов. Таким образом, процесс повторяется до тех пор, пока, в конце концов, разделы больше не будут разбиваться, и массив будет полностью отсортирован.

Почему мы всегда выбираем последний элемент в качестве опорного?

Схема разбиения (метод), использованная выше, известна как Схема разбиения Ломуто, которая обычно использует последний элемент в качестве опорного. Это совершенно произвольно, и можно выбрать разные опорные точки. Существуют и другие, более эффективные схемы и другие способы выбора точек опоры, но мы рассмотрим их в другом посте.

Почему быстрая сортировка вместо более простого алгоритма, такого как сортировка выбором или сортировка вставками?

Для больших входных данных быстрая сортировка быстрее, так как в целом выполняется меньше операций. Сортировка выбором и сортировка вставками имеют среднюю временную сложность O(n^2), тогда как средняя временная сложность быстрой сортировки составляет O(n log n).

Однако для небольших входных данных сортировка вставками на самом деле быстрее, чем быстрая сортировка, поскольку рекурсия снижает производительность и использует больше памяти. Из-за этого реализации быстрой сортировки часто прекращают разбиение на разделы, когда разделы становятся достаточно маленькими, и вместо этого используют сортировку вставками или другой алгоритм.

В любом случае, давайте подробнее рассмотрим временную сложность быстрой сортировки.

Временная сложность в лучшем случае

Идеальным случаем быстрой сортировки является то, что каждая операция разбиения на разделы разбивает ввод пополам. Если ось выбрана правильно (это зависит от схемы разбиения), половинки должны быть почти равны по размеру.

Для простоты предположим, что каждый раз мы получаем идеальные половинки: количество раз, когда входные данные могут быть разбиты пополам, представляет собой логарифм по основанию 2 от размера входных данных. Например, 64 входа будут разбиты на разделы размеров 32, 16, 8, 4, 2 и 1, поэтому у нас есть 6 уровней разделения, что является логарифмом по основанию 2 числа 64.

Итак, в этом случае у нас есть log n уровней разбиения, и каждый из этих уровней должен посетить все n входа. Таким образом, наилучшая временная сложность быстрой сортировки составляет O(n log n).

Средняя временная сложность

Предполагая, что опорная точка выбрана правильно, это будет довольно близко к лучшему сценарию. Таким образом, средняя временная сложность быстрой сортировки также составляет O(n log n).

Временная сложность в худшем случае

Наихудшим случаем быстрой сортировки является то, что точка опоры является самым маленьким или самым большим элементом во входных данных. В этом случае существует O(n) уровней разделения, так как размеры разделов каждый раз уменьшаются только на 1. Поскольку для каждого уровня требуется O(n) шагов, временная сложность быстрой сортировки в наихудшем случае составляет O(n^2).

Фактически, именно поэтому выбор первого или последнего элемента в качестве опорного так плох для уже отсортированных массивов, так как это всегда будет самый маленький или самый большой элемент.

Как сортировать элементы, не являющиеся числами?

Легкий! Мы используем функцию, которая определяет, является ли элемент «меньше» или «больше» другого. Например, если мы сортируем строки в алфавитном порядке, нам нужна функция, которая сообщает нам, что такая строка, как "baa", «больше», чем "aaa". Все остальное делается как обычно.

Что я слышал о «нестабильности» быстрой сортировки?

Допустим, вместо чисел мы сравнивали такие пары:

[(4, "a"), (2, ""), (4, "b"), (3, "")]

Каждый элемент этого массива представляет собой пару, содержащую число и строку. Давайте представим, что мы применили к этому массиву быструю сортировку, сравнив только числа в каждой паре. Если бы мы применяли схему разбиения Lomuto, первая операция разбиения выглядела бы так:

(swap_to = 0, i = 0): [(4, "a"), (2, ""), (4, "b"), (3, "")]
(swap_to = 0, i = 1): [(2, ""), (4, "a"), (4, "b"), (3, "")]
(swap_to = 1, i = 2): [(2, ""), (4, "a"), (4, "b"), (3, "")]
(swap_to = 1): [(2, ""), (3, ""), (4, "b"), (4, "a")]

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

Обратите внимание, что пара (4, "a") изначально была до (4, "b"), но оказалась после. Согласно сравнению, которое мы используем, две пары равны, поэтому быстрая сортировка не заботится о сохранении их порядка. Поскольку быстрая сортировка не гарантирует сохранения порядка элементов, которые считаются равными, она считается нестабильной.

Хм, возможно, пятилеткам просто не суждено полностью понять алгоритмы сортировки…

Если вам понравилось это объяснение, пожалуйста, выразите свою признательность, похлопав в ладоши! ❤︎