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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 61: Строка 61:
== Ссылки ==
== Ссылки ==
Теория:
Теория:
* [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://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://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-ой порядковой статистики]
* [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-ой порядковой статистики]
* [http://brestprog.neocities.org/lections/sort.html brestprog.neocities.org — Сортировка]
* [https://algorithmica.org/ru/sorting algorithmica.org — Сортировки]
* [http://algorithmica.org/tg/quicksort algorithmica.org — Быстрая сортировка (см. последнюю часть конспекта)]
* [https://algs4.cs.princeton.edu/lectures/keynote/23Quicksort.pdf algs4.cs.princeton.edu/lectures 2.3 Quicksort]
* [http://algs4.cs.princeton.edu/lectures/23Quicksort.pdf algs4.cs.princeton.edu/lectures — 2.3 Quicksort]
* [http://brilliant.org/wiki/quick-sort/ Brilliant.org — Quicksort]
* [http://brilliant.org/wiki/quick-sort/ Brilliant.org — Quicksort]
Демонстрация:
Демонстрация:
* [http://www.sorting-algorithms.com/quick-sort Sorting Algorithm Animations — Quick Sort]
* [http://www.sorting-algorithms.com/quick-sort Sorting Algorithm Animations Quick Sort]
* [http://visualgo.net/sorting.html VisuAlgo — Sorting]
* [http://visualgo.net/sorting.html VisuAlgo Sorting]
Код:
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/Sort.java CodeLibrary — 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 — 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 — 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]
* 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 — Курс «Поиск и сортировка» — часть 4]
* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru — Курс «Поиск и сортировка» — часть 4]

Версия от 10:22, 9 ноября 2021

Алгоритм

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

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

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

Если в качестве опорного выбирать любой фиксированный элемент, всегда можно составить контртест, на котором время работы будет квадратичным. Чтобы избежать худшего случая, требуется в качестве опорного выбирать случайный элемент в рассматриваемом диапазоне. Можно показать, что ожидаемая сложность при этом составит 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);
}

Ссылки

Теория:

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

Код:

Задачи: