C++ STLのstable_sort()関数の使い方と安定ソートの仕組みを解説

C++のSTL（標準テンプレートライブラリ）に含まれるstable_sort()は、指定された範囲の要素を昇順に並べ替えるソートアルゴリズムです。この関数が「安定（stable）」と呼ばれるのは、値が等しい要素同士の相対的な順序が、ソート後も維持されるためです。

この特性を活かすと、複数のキーを持つデータを段階的にソートする処理が実現できます。例えば、まず名前をキーとして要素を昇順にソートし、その後にセグメント（区分）をキーとして再度ソートすると、同じセグメント内では名前順の並びが保たれたままになります。通常のsort()ではこの順序の維持が保証されないため、安定性が必要な場面ではstable_sort()が適しています。

stable_sort()のサンプルコード

以下は、C++プログラムでstable_sort()アルゴリズムを使って配列を昇順にソートする例です。

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = { 11, 15, 18, 19, 16, 17, 13, 20, 14, 12, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    stable_sort(arr, arr + n);
    cout << "Array after sorting is =";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}

実行結果

このC++プログラムを実行すると、配列の要素が以下のように昇順にソートされて出力されます。

Array after sorting is= 10 11 12 13 14 15 16 17 18 19 20

sort()との違いと計算量

sort()の平均計算量はO(N log N)である一方、stable_sort()は追加のメモリが十分に確保できる場合はO(N log N)、確保できない場合はO(N (log N)²)で動作します。パフォーマンスよりも「等しい要素の順序を保つこと」が重要な場合は、stable_sort()を選択するとよいでしょう。