Root One

数学中心のブログです。

C++のソート

C++のソートについてまとめてみました。

ソートと重複要素削除 (外部サイト)

ソートの難しいところ

1次元のソートは簡単ですが、難しいのは多次元のソートです。

例えば、

1 7
2 3
1 2
2 7
2 2
1 3

 というデータを月順にソートすると

1 7
1 2
1 3
2 3
2 7
2 2

というような結果が得られますが、これを日にち順にソートしなおすと

1 2
2 2
1 3
2 3
1 7
2 7

 というように、月の順序まで変わってしまう可能性があります。

日付順のソートをしたい場合は、このようなことが起きてしまうとまずい

わけですが、Excelであれば、ソートの優先度を「月、日」の順に設定することが

できて、上のようなことを回避することができます。

C++では、このような優先度別ソートは、sort関数の第3引数を調整すると可能です。

sortの第3引数はどのように順序をつけるかを定める関数を指定するところになるのですが、この関数の設定法はいくつか考えられます。

今回のケースであれば、重みを付けてソートするのがおすすめです。

重みを付けるとは

「日」は最大で31にしかならないことを考慮して、

M月D日であれば

M*31+D

という値を考えるということです。(Mの重みを31倍にした.)

こうして、M*31+Dを基準にしてソートしてみると、

自動的に月が日よりも優先されてソートされることになります。

実際のコード例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class MyDate {
public:
	int Month;
	int Day;
	MyDate(int month, int day) {
		Month = month;
		Day = day;
	};
	int getValue() const {
		return Month * 31 + Day;
	}
};

ostream& operator <<(ostream& ost, const MyDate& p) {
	ost <<  p.Month << "月" << p.Day << "日";
	return ost;
}

int main() {
	vector<MyDate> dates = { MyDate(1,7),MyDate(2,3),MyDate(1,2),
		                     MyDate(2,7),MyDate(2,2),MyDate(1,3) };
	cout << "ソート前のデータ" << endl;
	for (auto d : dates) {
		cout << d << endl;
	}
	sort(dates.begin(), dates.end(), [](const MyDate& d1, const MyDate& d2)-> bool {return d1.getValue() < d2.getValue(); });
	cout << "ソート後のデータ" << endl;

	for (auto d : dates) {
		cout << d << endl;
	}

}

実行結果.

 ソート前のデータ
1月7日
2月3日
1月2日
2月7日
2月2日
1月3日
ソート後のデータ
1月2日
1月3日
1月7日
2月2日
2月3日
2月7日

プログラムのポイント

ostream& operator <<(ostream& ost, const MyDate& p) {
	ost <<  p.Month << "月" << p.Day << "日";
	return ost;
}

は自作クラスのMyDateの変数をcoutで表示できるようにするもので、ここはソートには直接関係しない部分です。

今重要なのは、MyDateクラスのgetValue関数で、ここが重みを付けたデータの和を考えるものとなっています。そしてこれをもとに

sort(dates.begin(), dates.end(), [](const MyDate& d1, const MyDate& d2)-> bool {return d1.getValue() < d2.getValue(); });

でソートを昇順に行っています。

上のケースは、M月D日というものでしたが、

Y年M月D日

といったケースにも応用できます。その場合はgetValue関数を

Y*12*31 + M*31+D

と設定してソートすればOKです。(12は月の最大値.)

ただし、値が大きくなってくると、オーバーフローに気をつける必要がありそうです。