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

Алгоритм

Выбираем в массиве опорный элемент. За Θ(N) делим массив на части: (<= опорного), (опорный), (>= опорного). Левую и правую части сортируем рекурсивно.

В лучшем случае, если опорный элемент будет делить массив примерно пополам, получим сложность O(NlogN), как у сортировки слиянием.

С другой стороны, если опорный элемент каждый раз выбирать неудачно (близко к минимуму или максимуму), то одна из половин будет почти пустой, а сложность деградирует до O(N²).

Если в качестве опорного выбирать любой фиксированный элемент, всегда можно составить контртест, на котором время работы будет квадратичным. Чтобы избежать худшего случая, требуется в качестве опорного выбирать случайный элемент в рассматриваемом диапазоне. Можно показать, что ожидаемая сложность при этом составит O(NlogN); константа у быстрой сортировки, как правило, меньше, чем у других сортировок с подобной асимптотической сложностью.

void quickSort(vector<int> &a, int l, int r) {
    if (l >= r)
        return;

    uniform_int_distribution<int> distribution(l, r);
    swap(a[l], a[distribution(generator)]);

    int i = l + 1, j = r;
    while (1) {
        while (i <= r && a[i] < a[l])
            i++;
        while (j > l && a[j] > a[l])
            j--;
        if (i >= j)
            break;
        swap(a[i++], a[j--]);
    }
    swap(a[l], a[j]);

    quickSort(a, l, j - 1);
    quickSort(a, j + 1, r);
}

K-я порядковая статистика за O(N)

minstd_rand generator;

int quickSort(vector<int> &a, int l, int r, int k) {
    uniform_int_distribution<int> distribution(l, r);
    swap(a[l], a[distribution(generator)]);

    int i = l + 1, j = r;
    while (1) {
        while (i <= r && a[i] < a[l])
            i++;
        while (j > l && a[j] > a[l])
            j--;
        if (i >= j)
            break;
        swap(a[i++], a[j--]);
    }
    swap(a[l], a[j]);

    if (k < j)
        return quickSort(a, l, j - 1, k);
    if (k == j)
        return a[j];
    else
        return quickSort(a, j + 1, r, k);
}

Ссылки

Теория:

• neerc.ifmo.ru/wiki — Быстрая сортировка
• neerc.ifmo.ru/wiki — Поиск k-ой порядковой статистики
• brestprog.neocities.org — Сортировка
• algorithmica.org — Быстрая сортировка (см. последнюю часть конспекта)
• algs4.cs.princeton.edu/lectures — 2.3 Quicksort
• Brilliant.org — Quicksort

Демонстрация:

• Sorting Algorithm Animations — Quick Sort
• VisuAlgo — Sorting

Код:

• CodeLibrary — Sorting algorithms
• CodeLibrary — Kth order statistic in O(N) on average
• Algos — Quick sort with random pivot element
• algs4.cs.princeton.edu/code — quicksort, quicksort with 3-way partitioning, optimized quicksort

Задачи:

• informatics.mccme.ru — Курс «Поиск и сортировка» — часть 4
• Задачи: Сортировка