std::stable_sort

プログラミング問題においてデータを整列する時、「もし二つのデータの順位評価が同じであれば順番を変えてはいけない」という条件がつく場合がある。

 

その際にはstd::stable_sortを使うことができる。

 

一般的に使われるstd::sortとは違い、std::stable_sortは整列後、同じ順位を持つ二つのデータ間の相対的な位置を維持する機能がある。

 

ヘッダー

<algorithm>

 

時間複雑度

O(N(log N)^2)

 

テスト

500000個のランダムなデータを用いて作動時間を比較した。

格tuple (a b)において、aは比較対象、bは元のインデックスを表している。

インデックスは大小比較で無視されるようにcomparer関数を作成した。

 

std::stable_sortの場合、インデックスbの順番が維持されていることがわかる。

その代わり、約3.4倍の時間を使っている。

 

コード

#include <iostream>
#include <vector>
#include <random>
#include <chrono>
#include <algorithm>

using namespace std;

using vii = vector<pair<int, int>>;

bool comparer(const pair<int, int>& a, const pair<int, int>& b) {
    return a.first < b.first;
}

int main() {
    unsigned int seed{ 12345U };
    mt19937 rng{ seed };
    uniform_int_distribution<> dist(0, 10);

    vii data{};
    for (int i = 0; i < 500000; ++i) {
        data.push_back({ dist(rng),i });
    }

    cout << "Before\n";
    for (int i = 0; i < 10; ++i) {
        const auto& v = data[i];
        cout << '(' << v.first << " " << v.second << ") ";
    }
    cout << "...\n";

    {
        vii copy{ data };
        auto tic = chrono::high_resolution_clock::now();
        sort(copy.begin(), copy.end(), comparer);
        auto toc = chrono::high_resolution_clock::now();
        auto dur = chrono::duration<double, milli>(toc - tic);

        cout << "std::sort\n";
        for (int i = 0; i < 10; ++i) {
            const auto& v = copy[i];
            cout << '(' << v.first << " " << v.second << ") ";
        }
        cout << "...\n";
        cout << "Tic = " << dur.count() << "[ms]\n";
    }

    {
        vii copy{ data };
        auto tic = chrono::high_resolution_clock::now();
        stable_sort(copy.begin(), copy.end(), comparer);
        auto toc = chrono::high_resolution_clock::now();
        auto dur = chrono::duration<double, milli>(toc - tic);

        cout << "std::stable_sort\n";
        for (int i = 0; i < 10; ++i) {
            const auto& v = copy[i];
            cout << '(' << v.first << " " << v.second << ") ";
        }
        cout << "...\n";
        cout << "Tic = " << dur.count() << "[ms]\n";
    }

    return 0;
}