Быстрая сортировка: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показано 9 промежуточных версий этого же участника)
Строка 1: Строка 1:
== Алгоритм ==
Выбираем в массиве опорный элемент. За &Theta;(N) делим массив на части: (<= опорного), (опорный), (>= опорного). Левую и правую части сортируем рекурсивно.
В лучшем случае, если опорный элемент будет делить массив примерно пополам, получим сложность O(NlogN), как у сортировки слиянием.
С другой стороны, если опорный элемент каждый раз выбирать неудачно (близко к минимуму или максимуму), то одна из половин будет почти пустой, а сложность деградирует до O(N<sup>2</sup>).
Если в качестве опорного выбирать любой фиксированный элемент, всегда можно составить контртест, на котором время работы будет квадратичным. Чтобы избежать худшего случая, требуется в качестве опорного выбирать случайный элемент в рассматриваемом диапазоне. Можно показать, что ожидаемая сложность при этом составит O(NlogN); константа у быстрой сортировки, как правило, меньше, чем у других сортировок с подобной асимптотической сложностью.
minstd_rand generator;
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 <= j && a[i] < a[l])
            i++;
        while (i <= j && 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;
{{Changed|int}} quickSort(vector<int> &a, int l, int r, {{Changed|1=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]);
    {{Changed|1=if (k < j)}}
        {{Changed|1=return quickSort(a, l, j - 1, k);}}
    {{Changed|1=if (k == j)}}
        {{Changed|1=return a[j];}}
    {{Changed|1=else}}
        {{Changed|1=return quickSort(a, j + 1, r, k);}}
}
== Ссылки ==
== Ссылки ==
Теория:
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 neerc.ifmo.ru/wiki &mdash; Быстрая сортировка]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%91%D1%8B%D1%81%D1%82%D1%80%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0 neerc.ifmo.ru/wiki Быстрая сортировка]
* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures &mdash; 2.3 Quicksort]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_k-%D0%BE%D0%B9_%D0%BF%D0%BE%D1%80%D1%8F%D0%B4%D0%BA%D0%BE%D0%B2%D0%BE%D0%B9_%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B8 neerc.ifmo.ru/wiki — Поиск k-ой порядковой статистики]
* [https://algorithmica.org/ru/sorting algorithmica.org — Сортировки]
* [https://algs4.cs.princeton.edu/lectures/keynote/23Quicksort.pdf algs4.cs.princeton.edu/lectures 2.3 Quicksort]
* [http://brilliant.org/wiki/quick-sort/ Brilliant.org — Quicksort]
Демонстрация:
Демонстрация:
* [http://www.sorting-algorithms.com/quick-sort Sorting Algorithm Animations &mdash; Quick Sort]
* [http://www.sorting-algorithms.com/quick-sort Sorting Algorithm Animations Quick Sort]
* [http://visualgo.net/sorting.html VisuAlgo &mdash; Sorting]
* [http://visualgo.net/sorting.html VisuAlgo Sorting]
Код:
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/Sort.java CodeLibrary &mdash; Sorting algorithms]
* [https://github.com/indy256/codelibrary/blob/master/java/sort/Quicksort.java indy256/codelibrary/java/sort/Quicksort.java]
* [http://github.com/indy256/codelibrary/blob/master/java/src/NthElement.java CodeLibrary &mdash; Kth order statistic in O(N) on average]
* [https://github.com/indy256/codelibrary/blob/master/java/sort/NthElement.java indy256/codelibraryjava/sort/NthElement.java]
* [http://github.com/ADJA/algos/blob/master/Other/QuickSort.cpp Algos &mdash; Quick sort with random pivot element]
* [https://github.com/ADJA/algos/blob/master/Other/QuickSort.cpp ADJA/algos/Other/QuickSort.cpp]
* algs4.cs.princeton.edu/code — [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick.java.html quicksort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Quick3way.java.html quicksort with 3-way partitioning], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/QuickX.java.html optimized quicksort]
Задачи:
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru &mdash; Курс &laquo;Поиск и сортировка&raquo; &mdash; часть 4]
* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru &mdash; Курс &laquo;Поиск и сортировка&raquo; &mdash; часть 4]

Текущая версия от 02:35, 11 ноября 2022

Алгоритм

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

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

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

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

minstd_rand generator;

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 <= j && a[i] < a[l])
            i++;
        while (i <= j && 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);
}

Ссылки

Теория:

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

Код:

Задачи: