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

Алгоритм быстрой сортировки (сортировка Хоара), как ни странно, является одним из самых быстрых алгоритмов сортировки. Он немного похож и на пузырьковую сортировку, и на сортировку слиянием, так как тоже использует стратегию "разделяй и властвуй".

Пример кода:

function quickSort(arr, start, end) {
            if (start === undefined) start = 0;
            if (end === undefined) end = arr.length - 1;

            if (start >= end) return;

            // индекс опорного элемента
            let pivot = partition(arr, start, end);

            // рекурсивная сортировка подмассивов
            quickSort(arr, start, pivot - 1);
            quickSort(arr, pivot + 1, end);
          }

          function partition(arr, start, end) {
            // Берем в качестве опорного последний элемент подмассива
            let pivotValue = arr[end];

            // изначально считаем, что pivotValue минимальное значение
            // и должно находиться в начале массива
            let pivotIndex = start;

            // перебираем все элементы
            for (let i = start; i < end; i++) {
              // значения меньше опорного перемещаем перед ним
              if (comparator(arr[i], pivotValue) < 0) {
                swap(arr, i, pivotIndex);
                pivotIndex++;
              }
            }

            // ставим опорный элемент в нужное место
            swap(arr, pivotIndex, end);

            return pivotIndex;
          }

– Сначала в массиве выбирается опорный элемент (пивот). Выбрать его можно любым способом: например, взять первый, средний или случайный элемент. От способа выбора во многом зависит эффективность алгоритма.

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

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

Функция quickSort принимает в качестве аргументов сам массив, а также начальную и конечную позиции, между которыми нужно произвести перестановки (границы подмассива). При первом вызове start и end не указываются, поэтому сортировка происходит для всего массива. При каждом рекурсивном вызове start и end приближаются друг к другу, так как подмассивы уменьшаются.

Вспомогательная функция partition также принимает исходный массив и границы подмассива для сортировки. Она находит опорный элемент для этого подмассива и перемещает остальные элементы согласно алгоритму, а затем возвращает индекс опорного элемента для дальнейшей рекурсивной сортировки.

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

Сложность

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

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