Sorting Algorithms
(misc/sorting.hpp)

• View this file on GitHub
• Last update: 2024-01-08 00:27:17+09:00
• Include: #include "misc/sorting.hpp"

Description

いくつかのソーティングアルゴリズムの実装．主にインタラクティブ問題での使用を想定しており，時間計算量よりも比較回数を重視している．

• void merge_sort(vector<T> arr, int l, int r, Compare cmp)
  • リスト $\mathrm{arr}$ の区間 $[l, r)$ を比較関数 $\mathrm{cmp}$ によってマージソートする
  • 時間計算量: $O(n \log n)$
• void merge_insertion_sort(vector<T> arr, Compare cmp)
  • 要素に重複のないリスト $\mathrm{arr}$ を比較関数 $\mathrm{cmp}$ によってソートする
  • 時間計算量: $O(n^2 \log n)$ ($O(n (\log n)^2)$ に高速化可能)

Note

比較ソートの最悪比較回数の情報理論的下界は $\lceil \log_2 n! \rceil \approx n\log_2 n - 1.443 n$ 回である．

マージソートの最悪比較回数は $n\log_2 n-0.915n$ から $n\log_2 n-n$ の間になることが知られている．

マージ挿入ソートの最悪比較回数は $n\log_2 n-1.415n$ 程度であることが知られている．マージ挿入ソートは，最悪比較回数が情報理論的下界に最も近いソーティングアルゴリズムの一つである．

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <map>
#include <vector>

template <typename T, typename Compare>
void merge_sort(std::vector<T>& arr, int l, int r, Compare cmp) {
    if (r - l == 1) return;

    int m = (l + r) / 2;
    merge_sort(arr, l, m, cmp);
    merge_sort(arr, m, r, cmp);

    std::vector<T> res;
    res.reserve(r - l);
    int i = l, j = m;
    while (i < m && j < r) {
        if (cmp(arr[i], arr[j])) {
            res.push_back(arr[i++]);
        } else {
            res.push_back(arr[j++]);
        }
    }

    while (i < m) res.push_back(arr[i++]);
    while (j < r) res.push_back(arr[j++]);

    for (int k = 0; k < r - l; ++k) arr[l + k] = res[k];
}

// elements need to be distinct
template <typename Compare>
void merge_insertion_sort(std::vector<int>& arr, Compare cmp) {
    int n = arr.size();
    if (n <= 1) return;

    std::map<int, int> idx;
    for (int k = 0; k < n; ++k) {
        assert(!idx.contains(arr[k]));
        idx[arr[k]] = k;
    }

    // pair elements and recursively sort the bigger ones
    std::vector<int> a;
    for (int k = 0; k < n - 1; k += 2) {
        a.push_back(cmp(arr[k], arr[k + 1]) ? arr[k + 1] : arr[k]);
    }
    merge_insertion_sort(a, cmp);

    // a: sorted
    // b: not sorted
    a.insert(a.begin(), arr[idx[a[0]] ^ 1]);
    std::vector<int> b;
    for (int k = 2; k < (int)a.size(); ++k) {
        b.push_back(arr[idx[a[k]] ^ 1]);
    }
    if (n % 2 == 1) {
        b.push_back(arr.back());
    }

    // insert b into a
    int s = 0, prev = 0;
    for (int i = 0; s < (int)b.size(); ++i) {
        int g = std::min((1 << (i + 1)) - prev, (int)b.size() - s);
        for (int k = g - 1; k >= 0; --k) {
            int x = b[s + k];
            // the first element guaranteed to be bigger than x
            int right = a.size();
            if ((idx[x] ^ 1) < n) {
                // this takes O(n)
                // it can be made O(log n) with a Fenwick tree
                right = std::ranges::find(a, arr[idx[x] ^ 1]) - a.begin();
            }
            // search insertion point
            int lb = -1, ub = right;
            while (ub - lb > 1) {
                int m = std::midpoint(lb, ub);
                if (cmp(x, a[m]))
                    ub = m;
                else
                    lb = m;
            }
            a.insert(a.begin() + ub, x);
        }
        s += g;
        prev = g;
    }

    arr = a;
}

#line 2 "misc/sorting.hpp"
#include <algorithm>
#include <cassert>
#include <map>
#include <vector>

template <typename T, typename Compare>
void merge_sort(std::vector<T>& arr, int l, int r, Compare cmp) {
    if (r - l == 1) return;

    int m = (l + r) / 2;
    merge_sort(arr, l, m, cmp);
    merge_sort(arr, m, r, cmp);

    std::vector<T> res;
    res.reserve(r - l);
    int i = l, j = m;
    while (i < m && j < r) {
        if (cmp(arr[i], arr[j])) {
            res.push_back(arr[i++]);
        } else {
            res.push_back(arr[j++]);
        }
    }

    while (i < m) res.push_back(arr[i++]);
    while (j < r) res.push_back(arr[j++]);

    for (int k = 0; k < r - l; ++k) arr[l + k] = res[k];
}

// elements need to be distinct
template <typename Compare>
void merge_insertion_sort(std::vector<int>& arr, Compare cmp) {
    int n = arr.size();
    if (n <= 1) return;

    std::map<int, int> idx;
    for (int k = 0; k < n; ++k) {
        assert(!idx.contains(arr[k]));
        idx[arr[k]] = k;
    }

    // pair elements and recursively sort the bigger ones
    std::vector<int> a;
    for (int k = 0; k < n - 1; k += 2) {
        a.push_back(cmp(arr[k], arr[k + 1]) ? arr[k + 1] : arr[k]);
    }
    merge_insertion_sort(a, cmp);

    // a: sorted
    // b: not sorted
    a.insert(a.begin(), arr[idx[a[0]] ^ 1]);
    std::vector<int> b;
    for (int k = 2; k < (int)a.size(); ++k) {
        b.push_back(arr[idx[a[k]] ^ 1]);
    }
    if (n % 2 == 1) {
        b.push_back(arr.back());
    }

    // insert b into a
    int s = 0, prev = 0;
    for (int i = 0; s < (int)b.size(); ++i) {
        int g = std::min((1 << (i + 1)) - prev, (int)b.size() - s);
        for (int k = g - 1; k >= 0; --k) {
            int x = b[s + k];
            // the first element guaranteed to be bigger than x
            int right = a.size();
            if ((idx[x] ^ 1) < n) {
                // this takes O(n)
                // it can be made O(log n) with a Fenwick tree
                right = std::ranges::find(a, arr[idx[x] ^ 1]) - a.begin();
            }
            // search insertion point
            int lb = -1, ub = right;
            while (ub - lb > 1) {
                int m = std::midpoint(lb, ub);
                if (cmp(x, a[m]))
                    ub = m;
                else
                    lb = m;
            }
            a.insert(a.begin() + ub, x);
        }
        s += g;
        prev = g;
    }

    arr = a;
}

Back to top page