C言語 › C++ › 第6回 std::sort
第6回 std::sort で STL の威力を体験 ★目玉
C で「昇順に並べ替えたい」と思ったら qsort と型消去されたコールバック関数 を書く必要があります。C++ の std::sort は 1 行 。しかも同じ内部アルゴリズム（introsort）で、qsort より2〜3 倍速い ベンチマーク結果も珍しくありません。本回はアニメーションで動きを可視化 し、qsort との速度差 と、ラムダによる比較関数の差し替え を体験します。
このページで押さえること
✅ 最低限ここだけ覚える
#include <algorithm>std::sort(v.begin(), v.end()); で昇順ソート計算量は O(n log n)
vector / array / 生配列なんでも使える
⭐ 余裕があれば読む
ラムダで比較関数を差し替える（降順・構造体など）
introsort（quick + heap + insertion のハイブリッド）
安定ソートなら std::stable_sort
C++17 の並列ソート std::execution::par
目次
1. std::sort とは ― まず使ってみる2. qsort vs std::sort の衝撃3. std::sort のアニメーション4. 比較関数の差し替え（ラムダ）5. qsort とのベンチマーク6. 仲間の関数たち ― sort の親戚7. std::sort の中身（introsort）
1. std::sort とは ― まず使ってみる
std::sort は「配列の中身を並び替える関数」
たとえば {5, 2, 8, 1, 9, 3} のような並びを、小さい順 {1, 2, 3, 5, 8, 9} に並べ替える。日常でいう「点数順に並べる」「五十音順に並べる」のプログラム版です。std::sort は 1 行 書くだけでこれをやってくれます。
🔀 ボタンを押して動きを体感しましょう
🎲 シャッフル
▶ std::sort 実行
「std::sort 実行」を押すと、昇順に並び替わります
まずは 3 行だけ
first_sort.cpp C++ 最小例
#include <vector>
#include <algorithm> // ← sort はここにある
int main () {
std::vector <int > v = {5 , 2 , 8 , 1 , 9 , 3 };
std::sort (v.begin (), v.end ()); // ← これだけ
// v は {1, 2, 3, 5, 8, 9}
}
ここまでで覚えること（2 つだけ）：
#include <algorithm> が必要std::sort(v.begin(), v.end()); で v を昇順に並び替える
よくある素朴な疑問
Q. v.begin() と v.end() って何？ 最初 と終わりの次 」を指すものです。今は「v の先頭から末尾まで」と読み替えれば OK。v.begin()+3, v.begin()+7 のように書くと一部だけソートもできます（詳しくは第 13 回「イテレータ」で）。
Q. 降順（大きい順）にしたい場合は？ std::sort(v.begin(), v.end(), std::greater<>{}); か、ラムダ [](int a, int b){ return a > b; }。詳しくは §4 で。
Q. std::string の vector もソートできる？ int でも double でも std::string でも「< で比較できる型」なら OK。
次のセクション以降は「C の qsort との比較」が出ます。 C のコード（void* キャストなど）は細部を読み飛ばして構いません 。「C で書くとこんなに大変だったんだ」という雰囲気を掴めば十分。
2. qsort vs std::sort の衝撃
「int の配列を昇順に並べて表示」というだけのタスク。C と C++ でどう違うか見てみましょう。
sort.c
C
#include <stdio.h>
#include <stdlib.h>
// 比較関数を別に書く必要がある
int cmp (const void * a, const void * b) {
int x = *(const int *)a;
int y = *(const int *)b;
return (x > y) - (x < y);
}
int main (void ) {
int a[] = {5 , 2 , 8 , 1 , 9 , 3 };
size_t n = sizeof (a) / sizeof (a[0 ]);
qsort (a, n, sizeof (int ), cmp);
for (size_t i = 0 ; i < n; ++i)
printf ("%d " , a[i]);
}
sort.cpp
C++
#include <iostream>
#include <vector>
#include <algorithm>
int main () {
std::vector <int > v = {5 , 2 , 8 , 1 , 9 , 3 };
std::sort (v.begin (), v.end ());
for (int x : v) std::cout << x << ' ' ;
}
C++ 側の強み 3 点：
比較関数がデフォルトで < （書かなくていい）
void* を介さないので関数がインライン展開 される（だから速い）範囲 を begin()/end() で指定 ― v.begin()+3, v.begin()+7 で部分ソートもできる
3. std::sort のアニメーション
std::sort は introsort というquicksort ベース のアルゴリズム。下のアニメで実際にどう動くか見てみてください（デモは理解優先のため quicksort のシンプル版を可視化）。
要素数:
🔀 シャッフル
▶ std::sort 実行
↺ リセット
準備完了
色の意味： 青＝未処理／黄＝比較中／赤＝スワップ／紫＝ピボット／緑＝確定済み。実際の std::sort は introsort で、再帰の深さが一定を超えると heapsort に切り替わる ― だからどんな入力でも必ず O(n log n) を保証します。
4. 比較関数の差し替え（ラムダ）
第 3 引数にラムダを渡すと、「何をもって小さいとみなすか」 を自由に定義できます。
下のパターンから選ぶと、実行結果が表示されます。
昇順（既定）
std::sort(v.begin(), v.end());
降順
std::sort(v.begin(), v.end(),
[](int a, int b){ return a > b; });
絶対値で
std::sort(v.begin(), v.end(),
[](int a, int b){ return std::abs(a) < std::abs(b); });
偶数を先に
std::sort(v.begin(), v.end(),
[](int a, int b){ return (a%2==0) > (b%2==0); });
文字列長で
std::sort(s.begin(), s.end(),
[](auto& a, auto& b){ return a.size() < b.size(); });
比較関数を渡すもうひとつの書き方
ラムダの代わりに std::greater<int>{} のような関数オブジェクト も渡せます。単純な逆順ならこちらが簡潔。
ラムダ版 汎用
std::sort (v.begin (), v.end (),
[](int a, int b){ return a > b; });
関数オブジェクト版 定型なら簡潔
#include <functional>
std::sort (v.begin (), v.end (),
std::greater <>{});
5. qsort とのベンチマーク
同じデータを 100 万要素ソートしたときの典型的な測定値（GCC 11, -O2, 環境によって前後します）。std::sort が圧倒的に速い理由は、比較関数がインライン展開される から。qsort は関数ポインタ経由なので、毎回関数呼び出しのコストがかかります。
100 万個のランダムな int をソート（小さいほど速い）
「C より C++ のほうが速い」ことがあるのか： ある。qsort は型を void* で隠すため、どうしても関数ポインタ呼び出し + キャスト のコストがかかります。std::sort はテンプレートで型がコンパイル時に決まるので、比較関数がインライン展開され、汎用性を失わずに最適化が効きます。
⭐
余裕があれば読む ― ここから先は応用
最低限はここまで。残りは sort の親戚と中身の仕組みなので、急ぐなら次章へ。
6. 仲間の関数たち ― sort の親戚
std::sort で十分ではないときに、用途特化 の仲間が揃っています。
std::stable_sort 安定ソート
// 同順位の要素の相対順序が保存される
std::stable_sort (v.begin (), v.end ());
// 計算量は O(n log² n) or O(n log n)
std::partial_sort 上位 K 個だけ
// 先頭 3 要素だけ最小のものを並べる
std::partial_sort (v.begin (),
v.begin ()+3 , v.end ());
// 残りは未定順
std::nth_element K 番目だけ確定
// 中央値の位置に中央値を置く。
// 他はそれより大か小かに仕分けされるだけ
std::nth_element (v.begin (),
v.begin ()+v.size ()/2 , v.end ());
// 中央値は v[v.size()/2]
std::is_sorted ソート済みか確認
if (std::is_sorted (v.begin (), v.end ())) {
// ソート済みなのでスキップ
}
7. std::sort の中身（introsort）
C++ 規格は std::sort に対してどんな入力でも平均 O(n log n) と決めていますが、多くの実装（libstdc++/libc++）は introsort を採用しています。
introsort のおおまかな戦略：
基本は quicksort （高速）
再帰の深さが log n の 2 倍を超えたら（= quicksort がハマりそう）、heapsort に切り替え（最悪保証）
小さい区間（~16 要素）は insertion sort （短い配列で最速）
「最も良いアルゴリズムを局面ごとに使い分ける」ハイブリッド戦略です。あなたが書く普通のソートは、この最先端のロジックを
ただ呼ぶだけ で使えます。
qsort が引き起こす最悪ケース
C の qsort は規格上どのアルゴリズムを使うかは実装依存で、単純な quicksort を使っている実装だと「すでにソート済み」「逆順」「全部同じ値」などで O(n²) に落ちることがあります。std::sort は introsort によって最悪でも O(n log n) が保証されているのが強みです。
確認クイズ
std::sort の理解度を 4 問で確認しましょう。
Q1. std::sort(v.begin(), v.end()); の既定の順序は？
昇順
降順
ランダム
指定が必須でコンパイルエラー
既定の比較は < で「小さい順」です。降順にしたいときは std::greater<>{} を渡すか、[](int a, int b){ return a > b; } のラムダを使います。
Q2. std::sort の平均計算量は？
O(n)
O(n log n)
O(n²)
O(log n)
規格は平均 O(n log n) を要求しています。多くの実装は introsort で「最悪でも O(n log n)」まで保証します。「n² のソート」は C の qsort の一部実装で起こる落とし穴。
Q3. std::sort が C の qsort より一般に速い主な理由は？
GPU を使うから
C++ はマルチスレッドだから
比較関数がインライン展開されるから
C++ の整数型が C より速いから
テンプレートにより型がコンパイル時 に決まり、比較関数が呼び出し箇所にインライン展開されます。qsort は関数ポインタ経由なので毎比較で関数呼び出しコストがかかります。
Q4. 安定ソート（同順位のときの入力順を保つ）が必要なとき、使うべきは？
std::sort
std::partial_sort
std::stable_sort
std::nth_element
std::sort は不安定 （入力順が保たれない）。同順位のレコード順を保ちたいなら std::stable_sort を使います。typical な用途: 「点数でソート、同点なら名前の入力順のまま」。