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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: «== Ссылки на задачи == * [http://acmp.ru/?main=task&id_task=112 ACMP #112 — Армия] Category:Улучшенные алгоритмы с…»)
 
 
(не показано 12 промежуточных версий этого же участника)
Строка 1: Строка 1:
== Ссылки на задачи ==
== Алгоритм ==
* [http://acmp.ru/?main=task&id_task=112 ACMP #112 — Армия]
Делим массив на половины, сортируем их рекурсивно, сливаем отсортированные части за Θ(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 — Сортировка слиянием]
* [https://brestprog.by/topics/sort/l brestprog.by — Сортировка]
* [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 — Merge Sort]
* [https://visualgo.net/en/sorting VisuAlgo — Sorting]
Код:
* [https://github.com/indy256/codelibrary/blob/master/cpp/sort/sort.cpp indy256/codelibrary/cpp/sort/sort.cpp]
* [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 ADJA/algos/Other/MergeSort.cpp]
* 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]
* [[:Категория: Задачи: Сортировка слиянием|Задачи: Сортировка слиянием]]
* [[:Категория: Задачи: Сортировка|Задачи: Сортировка]]
 
 


[[Category:Улучшенные алгоритмы сортировки]]
[[Category:Улучшенные алгоритмы сортировки]]

Текущая версия от 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;
}

Ссылки

Теория:

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

Код:

Задачи: