C++のソートを、標準ライブラリを使って行う方法のメモです。主要なソートをだいたい勉強し終えたので、そろそろ車輪の再発明のフェーズを脱しようという意図です。

安定でないソート

sortを使います。ヘッダファイルで定義されています。sortはクイックソートを元にしているため、高速ですが安定ではありません。
ソートしたいものの先頭のイテレータと末尾のイテレータを指定してあげます。ただし、末尾はソート対象に含まれていないことに注意。

sort(先頭のイテレータ, 末尾のイテレータ)

配列の場合は先頭と末尾へのポインタを指定します。

安定なソート

安定なソートであることが必要な時はstable_sortを用います。ヘッダファイルで定義されています。速度はsortに劣ります。
使い方はsortと同じ。

例

トランプを数字の順にソートする例です。ソートの基準とするメンバをrank（数字を表す）とするために、演算子<をオーバーロードしています。

#include<iostream>
#include<algorithm>
using namespace std;

class Card {
public:
  int rank;
  char suit;
  // < をオーバーロード
  bool operator< (const Card c) const {
    return rank < c.rank;
  }
};

void print(Card A[], int n) {
  for (int i = 0; i < n; i++) {
    if (i > 0) cout << " ";
    cout << A[i].suit << A[i].rank;
  }
  cout << endl;
}

int main() {
  int i, n = 6;
  int ranks[] = {3, 2, 1, 3, 2, 1};
  char suits[] = "DHDSDC";
  Card *c1, *c2;
  c1 = new Card[n];
  c2 = new Card[n];

  // トランプの並び方を設定
  for (i = 0; i < n; i++) {
    c1[i].suit = suits[i];
    c1[i].rank = ranks[i];
    c2[i] = c1[i];
  }
  
  print(c1, n);

  // ソート
  sort(c1, c1+n);
  stable_sort(c2, c2+n);

  print(c1, n);
  print(c2, n);

  return 0;
}

結果

D3 H2 D1 S3 D2 C1
D1 C1 H2 D2 D3 S3
D1 C1 H2 D2 D3 S3

この例ではいずれのソート結果も安定となっています。安定でなくなる例を思いつかなかったのですが、とりあえず使い方の確認はできたということで、これでよしとしておきます。

まとめ

STLで用意されているソートの使い方の基本的なところはわかったと思います。演算子のオーバーロードも機会を見つけてきっちりとやっておきたいところです。

参考

渡部有隆（2015）「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 Ozy・秋葉拓哉協力株式会社マイナビ

プログラミング原人の進化論

オレ　プログラミング　ベンキョウ　スル。マナンダ　コト　カク。

C++の標準ライブラリでソート

安定でないソート

安定なソート

例

まとめ

参考