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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показаны 4 промежуточные версии этого же участника)
Строка 1: Строка 1:
== Алгоритм ==
Делим массив на половины, сортируем их рекурсивно, сливаем отсортированные части за Θ(N).
Сложность Θ(NlogN) (logN уровней рекурсии, на каждом из которых при слиянии выполняется Θ(N) действий).
Требуется Θ(N) дополнительной памяти (вспомогательный массив t).
void mergeSort(vector<int> &a, vector<int> &t, int l, int r) {
    if (l == r)
        return;
    int m = l + (r - l) / 2;
    mergeSort(a, t, l, m);
    mergeSort(a, t, m + 1, r);
    for (int i = l; i <= r; i++)
        t[i] = a[i];
    int ai = l, bi = m + 1;
    for (int i = l; i <= r; i++) {
        if (bi > r || ai <= m && t[ai] <= t[bi])
            a[i] = t[ai++];
        else
            a[i] = t[bi++];
    }
}
== Подсчёт инверсий за &Theta;(NlogN) ==
{{Changed|long long}} mergeSort(vector<int> &a, vector<int> &t, int l, int r) {
    if (l == r)
        return {{Changed|0}};
    int m = l + (r - l) / 2;
    {{Changed|1=long long inversionCount = 0;}}
    {{Changed|1=inversionCount +=}} mergeSort(a, t, l, m);
    {{Changed|1=inversionCount +=}} mergeSort(a, t, m + 1, r);
    for (int i = l; i <= r; i++)
        t[i] = a[i];
    int ai = l, bi = m + 1;
    for (int i = l; i <= r; i++) {
        if (bi > r || ai <= m && t[ai] <= t[bi]) {
            a[i] = t[ai++];
        } else {
            {{Changed|1=inversionCount += m - ai + 1;}}
            a[i] = t[bi++];
        }
    }
    {{Changed|return inversionCount;}}
}
== Ссылки ==
== Ссылки ==
Теория:
Теория:
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC neerc.ifmo.ru/wiki &mdash; Сортировка слиянием]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC neerc.ifmo.ru/wiki Сортировка слиянием]
* [http://brestprog.neocities.org/lections/sort.html brestprog.neocities.org &mdash; Сортировка]
* [https://brestprog.by/topics/sort/l brestprog.by — Сортировка]
* [http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf algs4.cs.princeton.edu/lectures &mdash; 2.2 Mergesort]
* [https://algorithmica.org/ru/sorting algorithmica.org — Сортировки]
* [https://algs4.cs.princeton.edu/lectures/keynote/22Mergesort.pdf algs4.cs.princeton.edu/lectures 2.2 Mergesort]
* [http://brilliant.org/wiki/merge/ Brilliant.org — Mergesort]
Демонстрация:
Демонстрация:
* [http://www.sorting-algorithms.com/merge-sort Sorting Algorithm Animations &mdash; Merge Sort]
* [http://www.sorting-algorithms.com/merge-sort Sorting Algorithm Animations Merge Sort]
* [http://visualgo.net/sorting.html VisuAlgo &mdash; Sorting]
* [https://visualgo.net/en/sorting VisuAlgo Sorting]
Код:
Код:
* [http://github.com/indy256/codelibrary/blob/master/java/src/Sort.java CodeLibrary &mdash; Sorting algorithms]
* [https://github.com/indy256/codelibrary/blob/master/cpp/sort/sort.cpp indy256/codelibrary/cpp/sort/sort.cpp]
* [http://github.com/indy256/codelibrary/blob/master/java/src/Inversions.java CodeLibrary &mdash; Number of inversions in O(NlogN)]
* [https://github.com/indy256/codelibrary/blob/master/java/misc/Inversions.java indy256/codelibrary/java/misc/Inversions.java]
* [http://github.com/ADJA/algos/blob/master/Other/MergeSort.cpp Algos &mdash; Merge sort]
* [http://github.com/ADJA/algos/blob/master/Other/MergeSort.cpp ADJA/algos/Other/MergeSort.cpp]
* algs4.cs.princeton.edu/code &mdash; [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/Merge.java top-down mergesort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MergeBU.java bottom-up mergesort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MergeX.java optimized mergesort]
* algs4.cs.princeton.edu/code [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/Merge.java top-down mergesort], [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/MergeBU.java bottom-up mergesort], [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/MergeX.java optimized mergesort]
Задачи:
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru &mdash; Курс &laquo;Поиск и сортировка&raquo; &mdash; часть 7]
* [http://informatics.mccme.ru/course/view.php?id=3 informatics.mccme.ru &mdash; Курс &laquo;Поиск и сортировка&raquo; &mdash; часть 7]

Текущая версия от 10:22, 9 ноября 2021

Алгоритм

Делим массив на половины, сортируем их рекурсивно, сливаем отсортированные части за Θ(N).

Сложность Θ(NlogN) (logN уровней рекурсии, на каждом из которых при слиянии выполняется Θ(N) действий).

Требуется Θ(N) дополнительной памяти (вспомогательный массив t).

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

    int m = l + (r - l) / 2;
    mergeSort(a, t, l, m);
    mergeSort(a, t, m + 1, r);

    for (int i = l; i <= r; i++)
        t[i] = a[i];

    int ai = l, bi = m + 1;
    for (int i = l; i <= r; i++) {
        if (bi > r || ai <= m && t[ai] <= t[bi])
            a[i] = t[ai++];
        else
            a[i] = t[bi++];
    }
}

Подсчёт инверсий за Θ(NlogN)

long long mergeSort(vector<int> &a, vector<int> &t, int l, int r) {
    if (l == r)
        return 0;

    int m = l + (r - l) / 2;
    long long inversionCount = 0;
    inversionCount += mergeSort(a, t, l, m);
    inversionCount += mergeSort(a, t, m + 1, r);

    for (int i = l; i <= r; i++)
        t[i] = a[i];

    int ai = l, bi = m + 1;
    for (int i = l; i <= r; i++) {
        if (bi > r || ai <= m && t[ai] <= t[bi]) {
            a[i] = t[ai++];
        } else {
            inversionCount += m - ai + 1;
            a[i] = t[bi++];
        }
    }

    return inversionCount;
}

Ссылки

Теория:

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

Код:

Задачи: