SHOEISHA iD

※旧SEメンバーシップ会員の方は、同じ登録情報(メールアドレス&パスワード)でログインいただけます

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

特集記事

「ソートも、サーチも、あるんだよ」
~標準C++ライブラリにみるアルゴリズムの面白さ

<algorithm>のソートたち


  • X ポスト
  • このエントリーをはてなブックマークに追加

 僕がこのCodeZineに寄せた記事の中にはソートを題材としたものがいくつか(いくつも?)あります: マージソート、ヒープソート、そしてマルチスレッドで高速化した単純選択ソート。僕がソートをネタにする理由はいたって単純、「楽しいから」なんですね。

  • X ポスト
  • このエントリーをはてなブックマークに追加

 ソートってば期待される結果は極めて単純明快でありながらアルゴリズム次第で実装のややこしさと計算量がドラスティックに変化します。ソートは数理科学の基礎かつキモの一つであり、「アルゴリズムの華」だと思っています。

 ...とは言いながら、実務でソートを書くことはまずもってありません。多くの場合ライブラリで提供されているものを使えば大抵事足りてしまいますからね。C++においてもそこらへんの事情は同じ、標準C++ライブラリの <algorithm> にはソートおよびソートがらみの関数群が数多く用意されています。

 このアーティクルでは標準C++ライブラリの提供するソートをざっくりと眺めてみましょう。

sort: 定番ソートアルゴリズム

 その名のとおりのソートです。ランダムアクセス可能なコンテナ、単純に言えば x[n] によって n番目の要素にアクセスできる(例えば配列, array, vectorなどの)コンテナx の要素を昇順(小さい順)に並び替えてくれます。並び順を決定する要素の大小関係は、コンテナの要素 x, y に対し x < y が真であるとき「x は y より小さい」とします。

// 配列, array, vector を昇順にソートする
int a[N];
array<int,N> ar;
vector<int> v;

sort(a, a+N); // 配列
sort(ar.begin(), ar.end()); // array
sort(v.begin(), v.end()); // vector

 降順(大きい順)にソートしたいとか、シチュエーションに応じてソート・キーを変更したいとか、そんなときにはsort()の第3引数に比較関数オブジェクトを与えます。近頃はラムダ式をサポートする処理系も増えてきたので比較関数オブジェクトを与えるのがずいぶんお手軽になりました。

struct fruit {
  string name;  // 名前
  int    price; // 価格
};

vector<fruit> fruits;

// nameをキーに昇順でソート
sort(fruits.begin(), fruits.end(), 
     [](const fruit& x, const fruit& y) { return x.name < y.name;});

// priceをキーに降順でソート
sort(fruits.begin(), fruits.end(), 
     [](const fruit& x, const fruit& y) { return x.price > y.price;});

 比較関数オブジェクトさえきちんと与えてやればほとんどのソートは sort() でOKです。

 sort() ではソートできないケースの一つが、ソート対象であるコンテナがランダム・アクセスでない場合。代表的なのは list, forward_list のソートです。ご心配なく。list, forward_list はメンバ関数 sort() を持っています:

list<fruit> fruits;

// nameをキーに昇順でソート
fruits.sort([](const fruit& x, const fruit& y) { return x.name < y.name;});

// priceをキーに降順でソート
fruits.sort([](const fruit& x, const fruit& y) { return x.price > y.price;});

stable_sort: 安定なソート

 ある要素の列をソートしたとき、キーが等しい要素の並び(相対的な位置関係)がソートの前後で狂わないとき、そのソートは"安定である"といいます。例えば期末テストの集計を考えてみます。各要素は出席番号と得点の組であり、元データは出席番号の順に並んでいるものとします。この列を得点をキーに降順でソートするとき、同じ得点の複数の要素に対しソート後においても出席番号順に並んでいてほしいなら、安定なソートでないと困るのね。

 ではソートの定番アルゴリズム:sort() が安定であるか調べてみましょう。整数の列:{10,11,12,...,98,99} を一の位をキーに昇順でソートします:

array<int,90> ia;
iota(ia.begin(), ia.end(), 10); // ia = {10,11,12,... }
// 一の位をキーに昇順でソート
sort(ia.begin(), ia.end(), [](int x, int y) { return (x%10) < (y%10);});
for_each(ia.begin(), ia.end(), [](int x) { cout << x << ' ';});

 どうやら安定ではなさそうです。安定であるならソート後の要素は 10,20,30,... のようにキレイに並ぶはずですから。

 安定なソートがご所望なら stable_sort() をお使いください。インターフェースは sort() とまったく同じ。上記コードの sort() を stable_sort() に置き換えると:

 ちなみに、list::sort()、forward_list::sort() は安定です。

会員登録無料すると、続きをお読みいただけます

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

次のページ
partial_sort: 部分的なソート

この記事は参考になりましたか?

  • X ポスト
  • このエントリーをはてなブックマークに追加
特集記事連載記事一覧

もっと読む

この記事の著者

επιστημη(エピステーメー)

C++に首まで浸かったプログラマ。Microsoft MVP, Visual C++ (2004.01~2018.06) "だった"りわんくま同盟でたまにセッションスピーカやったり中国茶淹れてにわか茶...

※プロフィールは、執筆時点、または直近の記事の寄稿時点での内容です

この記事は参考になりましたか?

この記事をシェア

  • X ポスト
  • このエントリーをはてなブックマークに追加
CodeZine(コードジン)
https://codezine.jp/article/detail/6020 2011/07/28 08:09

おすすめ

アクセスランキング

アクセスランキング

イベント

CodeZine編集部では、現場で活躍するデベロッパーをスターにするためのカンファレンス「Developers Summit」や、エンジニアの生きざまをブーストするためのイベント「Developers Boost」など、さまざまなカンファレンスを企画・運営しています。

新規会員登録無料のご案内

  • ・全ての過去記事が閲覧できます
  • ・会員限定メルマガを受信できます

メールバックナンバー

アクセスランキング

アクセスランキング