概要
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++より小さい。
おそらく、処理系によって実装の方法が違っているっぽい。