C++のsortとstable_sortの違い

概要

sortには同位の場合に、その順番を保障する安定したソートと保障していない安定しないソートの二種類がある。

STLで提供されているsortは安定しないソートで、stable_sortは安定しているソートである。

sortで安定したソートを実現したい場合は、比較用の関数で同位だったら、元の並び順で比較してやれば安定する。

検証コード

#include <iostream>  // cout, endl
#include <algorithm> // stable_sort, for_each
#include <vector>
#include <time.h>     // for clock()
#include <string>

using namespace std;
struct test
{
    int order;
    int key;
};

bool CustPredicate(test elem1, test elem2)
{
    if (elem1.key > elem2.key)
        return false;

    if (elem1.key < elem2.key)
        return true;
    return false; // trueにするとDebugでAssert。同値の場合、順序が逆になる
    // https://support.microsoft.com/en-us/kb/949171
}

bool CustPredicate2(test elem1, test elem2)
{
    if (elem1.key > elem2.key)
        return false;

    if (elem1.key < elem2.key)
        return true;
    // 同じ場合は元の並び順で決める
    return elem1.order < elem2.order;
}

vector<test> createList(size_t sz)
{
    std::vector<test> list;
    // データ数が少ないと、安定してないソートでも安定しているように見えるので注意
    for (size_t i = 0; i < sz; ++i){
        test t;
        t.order = i;
        t.key = i % 3;
        list.push_back(t);
    }
    return list;
}


int main() {
    {
        vector<test> list = createList(32);
        cout << "\n不安定なソート 32件-----------------------------------\n";
        sort(list.begin(), list.end(), &CustPredicate);
        for (size_t i = 0; i < list.size(); ++i){
            cout << "(" << list[i].key << ":" << list[i].order << ")";
        }
    }
    {
        vector<test> list = createList(33);
        cout << "\n不安定なソート 33件-----------------------------------\n";
        sort(list.begin(), list.end(), &CustPredicate);
        for (size_t i = 0; i < list.size(); ++i){
            cout << "(" << list[i].key << ":" << list[i].order << ")";
        }
    }
    {
        vector<test> list = createList(32);
        cout << "\n安定なソート 33件-----------------------------------\n";
        stable_sort(list.begin(), list.end(), &CustPredicate);
        for (size_t i = 0; i < list.size(); ++i){
            cout << "(" << list[i].key << ":" << list[i].order << ")";
        }
    }
    {
        vector<test> list = createList(33);
        cout << "\n安定なソート 33件-----------------------------------\n";
        stable_sort(list.begin(), list.end(), &CustPredicate);
        for (size_t i = 0; i < list.size(); ++i){
            cout << "(" << list[i].key << ":" << list[i].order << ")";
        }
    }
    {
        vector<test> list = createList(33);
        cout << "\n不安定なソートを比較関数でなんとかする 33件-----------------------------------\n";
        stable_sort(list.begin(), list.end(), &CustPredicate2);
        for (size_t i = 0; i < list.size(); ++i){
            cout << "(" << list[i].key << ":" << list[i].order << ")";
        }
    }
    size_t sort_size = 500000;
    {
        vector<test> list = createList(sort_size);
        cout << "\n不安定ソートの速度-----------------------------------\n";
        clock_t start = clock();    // スタート時間
        sort(list.begin(), list.end(), &CustPredicate2);
        clock_t end = clock();     // 終了時間
        std::cout << "\nduration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n";
    }
    {
        vector<test> list = createList(sort_size);
        cout << "\n安定ソートの速度-----------------------------------\n";
        clock_t start = clock();    // スタート時間
        stable_sort(list.begin(), list.end(), &CustPredicate2);
        clock_t end = clock();     // 終了時間
        std::cout << "\nduration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n";
    }
    {
        vector<test> list = createList(sort_size);
        cout << "\n比較関数で安定させるソート-----------------------------------\n";
        clock_t start = clock();    // スタート時間
        sort(list.begin(), list.end(), &CustPredicate2);
        clock_t end = clock();     // 終了時間
        std::cout << "\nduration = " << (double)(end - start) / CLOCKS_PER_SEC << "sec.\n";
    }
    cout << endl << endl;


}

結果

VS2013 + Windows7

不安定なソート 32件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)
不安定なソート 33件-----------------------------------
(0:0)(0:21)(0:30)(0:3)(0:12)(0:27)(0:6)(0:15)(0:24)(0:9)(0:18)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:14)(2:23)(2:8)(2:17)(2:26)(2:5)(2:20)(2:29)(2:2)(2:11)(2:32)
安定なソート 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)
安定なソート 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)(2:32)
不安定なソートを比較関数でなんとかする 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)(2:32)
不安定ソートの速度-----------------------------------

duration = 0.12sec.

安定ソートの速度-----------------------------------

duration = 0.081sec.

比較関数で安定させるソート-----------------------------------

duration = 0.109sec.

VisualStudioのC++だとsort関数は32件までは挿入ソートをしているので安定している。
それいこうは、クイックソート。
stable_sortも32件までは挿入ソートで、それ以降はマージソート
速度的には、stable_sortの方が早い。そのかわり、マージソートなのでメモリを消費している。

stable_sortでassertが出る場合

vs2005以降でstable_sortを使うとAssertがでる場合がある。
これは同値の場合にtrueを返してしまっているため。
https://support.microsoft.com/en-us/kb/949171

trueを返すと同位の場合、逆順にならんでしまう。

Debian7 + g++ 4.7.4

不安定なソート 32件-----------------------------------
(0:24)(0:0)(0:15)(0:18)(0:12)(0:21)(0:9)(0:6)(0:27)(0:3)(0:30)
(1:25)(1:16)(1:22)(1:28)(1:19)(1:31)(1:13)(1:10)(1:7)(1:4)(1:1)
(2:17)(2:14)(2:20)(2:11)(2:23)(2:8)(2:26)(2:5)(2:29)(2:2)
不安定なソート 33件-----------------------------------
(0:0)(0:18)(0:15)(0:21)(0:12)(0:24)(0:9)(0:27)(0:6)(0:30)(0:3)
(1:25)(1:28)(1:22)(1:19)(1:31)(1:1)(1:16)(1:13)(1:10)(1:7)(1:4)
(2:17)(2:14)(2:20)(2:11)(2:23)(2:8)(2:26)(2:5)(2:29)(2:2)(2:32)
安定なソート 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)
安定なソート 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)(2:32)
不安定なソートを比較関数でなんとかする 33件-----------------------------------
(0:0)(0:3)(0:6)(0:9)(0:12)(0:15)(0:18)(0:21)(0:24)(0:27)(0:30)
(1:1)(1:4)(1:7)(1:10)(1:13)(1:16)(1:19)(1:22)(1:25)(1:28)(1:31)
(2:2)(2:5)(2:8)(2:11)(2:14)(2:17)(2:20)(2:23)(2:26)(2:29)(2:32)
不安定ソートの速度-----------------------------------

duration = 0.256623sec.

安定ソートの速度-----------------------------------

duration = 0.253698sec.

比較関数で安定させるソート-----------------------------------

duration = 0.252346sec.

g++の場合、件数が32件でも不安定になっているので、おそらく、件数によるアルゴリズムの切り替えはしてないくさい。（あるいはもっと件数が小さい）

そして、stable_sortとsortの速度差がVisualStudioC++より小さい。

おそらく、処理系によって実装の方法が違っているっぽい。