Премиум

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

Базовый Algorithms
≈ 2 мин чтения

Разбить массив вокруг опорного элемента

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

static int partition(int[] a, int left, int right) {
    int pivot = a[right];
    int boundary = left;

    for (int i = left; i < right; i++) {
        if (a[i] <= pivot) {
            int tmp = a[i];
            a[i] = a[boundary];
            a[boundary] = tmp;
            boundary++;
        }
    }

    int tmp = a[boundary];
    a[boundary] = a[right];
    a[right] = tmp;
    return boundary;
}

После partition опорный элемент уже находится на окончательной позиции. Слева от него лежат значения не больше pivot, справа — больше. Затем quick sort рекурсивно повторяет ту же операцию для левой и правой частей.

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

Если разбиения получаются достаточно сбалансированными, глубина рекурсии составляет порядка log n, а суммарная работа — O(n log n). Но если pivot снова и снова оказывается почти минимальным или максимальным, получаются крайне неравные части и время может ухудшиться до O(n²).

Почему выбор pivot важен

Сам алгоритм разбиения остаётся тем же, но стратегия выбора pivot сильно влияет на вероятность плохих разбиений. На практике используют разные приёмы выбора, чтобы не зависеть от одного очевидного расположения данных.

Quick sort обычно работает внутри исходного массива, но рекурсия всё равно использует память стека вызовов. При удачных разбиениях это около O(log n), а при крайне неудачных может вырасти до O(n).
Назад Далее