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

Алгоритм

Выбираем в массиве опорный элемент. За Θ(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);
}

Ссылки

Теория:

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

Код:

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

Задачи:

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

Алгоритм

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

Ссылки

Навигация

Поиск