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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Строка 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 &mdash; Сортировка слиянием]
* [http://brestprog.neocities.org/lections/sort.html brestprog.neocities.org &mdash; Сортировка]
* [https://brestprog.by/topics/sort/l brestprog.by — Сортировка]
* [http://algorithmica.org/tg/sorting algorithmica.org — Сортировки]
* [http://algorithmica.org/tg/sorting algorithmica.org — Сортировки]
* [http://algs4.cs.princeton.edu/lectures/22Mergesort.pdf algs4.cs.princeton.edu/lectures &mdash; 2.2 Mergesort]
* [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://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 &mdash; 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.html top-down mergesort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MergeBU.java.html bottom-up mergesort], [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MergeX.java.html optimized mergesort]
* algs4 [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]

Версия от 14:49, 15 февраля 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;
}

Ссылки

Теория:

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

Код:

Задачи: