ソート

Ⅲ．ソート

比較演算

　　この章では，ソート（並べ替え）に対するアルゴリズについて説明します．ソートを行うためには，データの比較が必要です．int や double に対しては，比較演算子（ < ，> など）によって簡単に比較が可能です（ 38 行目～ 41 行目）．また，文字列の場合も，char を使用した通常の文字列に対しては不可能ですが，C++ 標準ライブラリ内の string クラスに対しては，比較演算子を使用して比較が可能です（ 43 行目～ 47 行目）．

　　しかし，一般に，比較演算子をそのまま使用してクラスのオブジェクト同士を比較することは不可能です．比較を行う関数を使用しても可能ですが，比較演算子をそのまま使用できれば非常に便利です．そのため，以下のプログラムにおいては，比較演算子 > を多重定義する（ 23 行目～ 29 行目）ことによってそれを実現しています（ 49 行目～ 53 行目）．string クラスに対して比較演算子を使用できるのも，比較演算子に対する多重定義が行われているからです．どのような方法で比較を行っても構いませんが，ここでは，メンバー変数 n の値が等しいときはメンバー変数 str の比較によって，そうでない場合は，n の大小関係によって比較を行っています．また，この例においては，演算子の多重定義をメンバー関数で行っていますが，フレンド関数を利用することも可能です．後に，ヒープソートに対する節で示しますように，関数オブジェクトやラムダ式を使用して比較を行うことも可能です．
```
01	/****************************/
02	/* 比較演算                 */
03	/*      coded by Y.Suganuma */
04	/****************************/
05	#include <iostream>
06	#include <string>
07	
08	using namespace std;
09	
10	/********************/
11	/* クラスTestの定義 */
12	/********************/
13	class Test {
14			string str;
15			int n;
16		public:
17				// コンストラクタ
18			Test (string s, int m) {
19				str = s;
20				n   = m;
21			}
22						// > 演算子のオーバーロード
23			bool operator> (Test t)
24			{
25				if (n == t.n)
26					return (str > t.str) ? true : false;
27				else
28					return (n > t.n) ? true : false;
29			}
30	};
31	
32	/****************/
33	/* main program */
34	/****************/
35	int main ()
36	{
37				// 整数の比較
38		if (10 > 1)
39			printf("true\n");
40		else
41			printf("false\n");
42				// 文字列(string)の比較
43		string x = "abc", y = "xyz";
44		if (x > y)
45			printf("true\n");
46		else
47			printf("false\n");
48				// クラスTestのオブジェクトの比較
49		Test t1(x, 10), t2(y, 1);
50		if (t1 > t2)
51			printf("true\n");
52		else
53			printf("false\n");
54	
55		return 0;
56	}
			
```
38 行目～ 41 行目

　　通常の整数どうしの比較です．

43 行目～ 47 行目

　　string クラスのオブジェクトどうしの比較です．通常の文字列に対しては，標準関数の strcmp を使用する必要があります．

43 行目～ 47 行目

　　クラス Test のオブジェクトどうしの比較です．一般的には，このような比較に対して，通常の比較演算子を使用することはできません．しかし，このプログラムにおいては，23 行目～ 29 行目に記述してあるように，演算子 > のオーバーロードによってこのような比較を可能にしています．この結果，2 つのオブジェクトのメンバー変数 n の値が等しいときは str の比較によって，また，n が等しくないときはその大小関係によって，比較が行われます．

（出力）　このプログラムによって，以下に示すような結果が得られます．
true false true

バブルソート

　　実行速度が遅いため，ここで述べるバブルソートと次節で述べる選択ソートに対しては，100,000 個（ヒープソートとクイックソートの場合は 5,000,000 個）のデータを乱数によって生成し，それを昇順及び降順にソートし，データの生成時間（ data の後ろ）及びソートに要した時間（ sort の後ろ）を出力しています．なお，昇順及び降順は，関数名を引数として渡すことによって制御しています（ 72 行目，82 行目と対応する関数）．勿論，前章で述べた比較演算子の多重定義を使用しても可能です．バブルソートの手順は以下に示すとおりです．

配列 data に n 個のデータが入っているものとする．　i = 0, 1, ･･･, n-1
i 番目のデータと i+1 番目のデータを比較し，もし，

data[i+1] < data[i]　（昇順の場合）

であればそれらのデータを交換する．　i = 0, 1, ･･･, n-2

→ この結果，data[n-1] に最も大きなデータが入ることになる
次に，n-1 個のデータに対し上の処理を繰り返す．
同様に，n-2，n-3，・・・個のデータに対して同じ処理を繰り返す

01	/****************************/
02	/* バブルソート             */
03	/*      coded by Y.Suganuma */
04	/****************************/
05	#include <stdio.h>
06	#include <time.h>
07	#include "MT.h"
08	
09	/*****************************/
10	/* データの比較（昇順）      */
11	/* a > bの場合に０以外（真） */
12	/*****************************/
13	int ascend(int a, int b)
14	{
15		return a > b;
16	}
17	
18	/*****************************/
19	/* データの比較（降順）      */
20	/* a < bの場合に０以外（真） */
21	/*****************************/
22	int descend(int a, int b)
23	{
24		return a < b;
25	}
26	
27	/*************************************/
28	/* ２つのデータを交換する            */
29	/*      a,b : ２つのデータのアドレス */
30	/*************************************/
31	void swap(int *a, int *b)
32	{
33		int temp = *a;
34		*a       = *b;
35		*b       = temp;
36	}
37	
38	/*********************************/
39	/* バブルソート                  */
40	/*      n : データの数           */
41	/*      data : データ            */
42	/*      compare : 比較を行う関数 */
43	/*********************************/
44	void bubble(int n, int *data, int (*compare)(int, int))
45	{
46		int sw = 0;
47		if (n > 1) {
48			for (int i1 = 0; i1 < n-1; i1++) {
49				if (compare(data[i1], data[i1+1])) {
50					sw = 1;
51					swap(&data[i1], &data[i1+1]);
52				}
53			}
54		}
55	
56		if (sw > 0)
57			bubble(n-1, data, compare);
58	}
59	
60	#define N 100000
61	
62	int main()
63	{
64				// 初期設定
65		int *data = new int [N];
66		init_genrand((unsigned)time(NULL));
67				// 昇順
68		clock_t tm1 = clock();
69		for (int i1 = 0; i1 < N; i1++)
70			data[i1] = genrand_int31();   // [0,0x7fffffff]
71		clock_t tm2 = clock();
72		bubble(N, data, ascend);
73		clock_t tm3 = clock();
74		printf("昇順（データ数： %d）\n", N);
75		printf("   data %d ms\n", (int)(tm2-tm1));
76		printf("   sort %d ms\n", (int)(tm3-tm2));
77						// 降順
78		tm1 = clock();
79		for (int i1 = 0; i1 < N; i1++)
80			data[i1] = genrand_int31();
81		tm2 = clock();
82		bubble(N, data, descend);
83		tm3 = clock();
84		printf("降順（データ数： %d）\n", N);
85		printf("   data %d ms\n", (int)(tm2-tm1));
86		printf("   sort %d ms\n", (int)(tm3-tm2));
87	
88		return 0;
89	}

44 行目～ 58 行目

　　バブルソートを実行するプログラムです．配列内の n 個のデータに対し，現在のデータと次のデータを比較し（ 49 行目），結果が真であった場合は，それらのデータを入れ替えます（ 51 行目）．入れ替えが 1 回でも行われた場合は，(n-1) 個のデータに対して同じ操作を繰り返します（ 56，57 行目）．

68，71，73 行目

　　標準関数 clock は，clock への最初の呼び出しがあったときから，使用された CPU 時間の長さ（ミリ秒単位）を返す関数です．

69，70 行目

　　N 個の [0, 0xffffffff] 区間の一様乱数を生成し，配列 data に記憶しています．

72，82 行目

　　データを昇順及び降順に並べています．その区別は，3 番目の引数として関数名を渡すことによって行っています．このようにすることによって，バブルソートを実行するプログラム bubble を変更すること無しに，昇順及び降順のソートが可能になります．

（出力）　このプログラムによって，以下に示すような結果が得られます．

昇順（データ数： 100000）
   data 0 ms
   sort 32471 ms
降順（データ数： 100000）
   data 1 ms
   sort 33073 ms

選択ソート

　　ここでも，バブルソートと同様の処理を行っています．また，選択ソートの手順は以下に示すとおりです．

配列を走査して，最も小さな要素を見つけだす（昇順の場合）．
見つけたら，それを配列の先頭要素と交換する．
上記の操作を配列の 2 番目の要素から始まるサブ配列について繰り返す．

01	/****************************/
02	/* 選択ソート               */
03	/*      coded by Y.Suganuma */
04	/****************************/
05	#include <stdio.h>
06	#include <time.h>
07	#include "MT.h"
08	
09	/*****************************/
10	/* データの比較（昇順）      */
11	/* a > bの場合に０以外（真） */
12	/*****************************/
13	int ascend(int a, int b)
14	{
15		return a > b;
16	}
17	
18	/*****************************/
19	/* データの比較（降順）      */
20	/* a < bの場合に０以外（真） */
21	/*****************************/
22	int descend(int a, int b)
23	{
24		return a < b;
25	}
26	
27	/*************************************/
28	/* ２つのデータを交換する            */
29	/*      a,b : ２つのデータのアドレス */
30	/*************************************/
31	void swap(int *a, int *b)
32	{
33		int temp = *a;
34		*a       = *b;
35		*b       = temp;
36	}
37	
38	/*********************************/
39	/* 選択ソート                    */
40	/*      n : データの数           */
41	/*      data : データ            */
42	/*      compare : 比較を行う関数 */
43	/*********************************/
44	void select(int n, int *data, int (*compare)(int, int))
45	{
46		int i1, m;
47	
48		if (n > 1) {
49	
50			m = 0;
51			for (i1 = 1; i1 < n; i1++) {
52				if (compare(data[m], data[i1]))
53					m = i1;
54			}
55	
56			if (m != 0)
57				swap(&data[0], &data[m]);
58	
59			select(n-1, &data[1], compare);
60		}
61	}
62	
63	#define N 100000
64	
65	int main()
66	{
67				// 初期設定
68		int *data = new int [N];
69		init_genrand((unsigned)time(NULL));
70				// 昇順
71		clock_t tm1 = clock();
72		for (int i1 = 0; i1 < N; i1++)
73			data[i1] = genrand_int31();
74		clock_t tm2 = clock();
75		select(N, data, ascend);
76		clock_t tm3 = clock();
77		printf("昇順（データ数： %d）\n", N);
78		printf("   data %d ms\n", (int)(tm2-tm1));
79		printf("   sort %d ms\n", (int)(tm3-tm2));
80						// 降順
81		tm1 = clock();
82		for (int i1 = 0; i1 < N; i1++)
83			data[i1] = genrand_int31();
84		tm2 = clock();
85		select(N, data, descend);
86		tm3 = clock();
87		printf("降順（データ数： %d）\n", N);
88		printf("   data %d ms\n", (int)(tm2-tm1));
89		printf("   sort %d ms\n", (int)(tm3-tm2));
90	
91		return 0;
92	}

　　プログラム構造は，基本的に，バブルソートの場合とほとんど同じです．選択ソートを行う select 関数内の 51 行目～ 54 行目において，n 個のデータの最小値または最大値を見つけ，見つけた要素を先頭要素と交換します（ 57 行目）．次に，残り (n-1) 個の要素に対して同じことを繰り返します（ 59 行目）．ただし，バブルソートとは異なり，先頭の (n-1) 個のデータではなく，2 番目以降の (n-1) 個のデータを対象とするため，引数として &data[1] を渡しています．

（出力）　このプログラムによって，以下に示すような結果が得られます．

昇順（データ数： 100000）
   data 1 ms
   sort 13680 ms
降順（データ数： 100000）
   data 1 ms
   sort 13711 ms

ヒープソート

　　ヒープという言葉によって，プログラム実行時に任意に確保や解放を繰り返すことができるメモリ領域（ヒープ領域，ヒープメモリ，heap memory ）を指す場合があります．しかし，ここで使用するヒープとは，Ⅳ 章において説明する木構造の一種であり，親ノードの値が子ノードの値より常に大きい（または，小さい）という条件を満たしています．さらに，各ノードが最大で 2 つの子ノードしか持たないバイナリヒープを意味します．ヒープソートは，次に述べるクイックソートよりも多少遅いですが，非常に高速なソートであり，その手順は以下に示すとおりです．

整列対象の配列内にボトムアップでヒープを構築する．
構築されたヒープの先頭要素 [0] と最後の要素 [N-1] を交換する．
先頭要素 [0] から最後の一つ前の要素 [N-2] でヒープを再構成する．
最後の要素を [N-2] として（ N = N - 1 ），手順 B に戻る．
N が 0 となった時点で終了する．

　　上の説明だけでは分かり難いと思いますので，ソート対象のデータ，

int data[] = {1, 4, 2, 9, 0, 2, 8, 7, 3, 5}

を昇順に並べたい場合を例にとって説明します．昇順に並べるためには，ルートノードが最も大きいヒープ（親ノードの値が子ノードの値より常に大きいヒープ）を生成する必要があります．実際，上に示したデータ全体に対してヒープを生成すると以下のようになります．

{9, 7, 8, 4, 5, 2, 2, 1, 3, 0}
	親 [0] 子 [1], [2]
	親 [1] 子 [3], [4]
	親 [2] 子 [5], [6]
	親 [3] 子 [7], [8]
	親 [4] 子 [9]

　　一般に，

data[k] : 親
	data[k1], data[k2] : 子供，k1 = 2k+1, k2 = 2k+2
	子供から見て親は：(k1-1) / 2 = (k2-1) / 2 = k

のような形でヒープが生成されます．なお，以下に示すプログラムでは，C++ 標準ライブラリ内のアルゴリズムである make_heap と sort_heap を利用した場合についても検討しています．また，<utility> ヘッダ内の swap も利用しています．

001	/****************************/
002	/* ヒープソート             */
003	/*      coded by Y.Suganuma */
004	/****************************/
005	#include <stdio.h>
006	#include <time.h>
007	#include <algorithm>
008	#include <utility>
009	#include <functional>
010	#include "MT.h"
011	
012	using namespace std;
013	
014	/*****************************/
015	/* データの比較（昇順）      */
016	/* a > bの場合に０以外（真） */
017	/*****************************/
018	bool ascend(int a, int b)
019	{
020		return a < b;
021	}
022	
023	/*****************************/
024	/* データの比較（降順）      */
025	/* a < bの場合に０以外（真） */
026	/*****************************/
027	bool descend(int a, int b)
028	{
029		return a > b;
030	}
031	
032	/**********************************/
033	/* ヒープの生成                   */
034	/*      n : データの数            */
035	/*      data : データ             */
036	/*      parent : 親のインデックス */
037	/*      compare : 比較関数        */
038	/**********************************/
039	void heap_c(int n, int *data, int parent, bool (*compare)(int, int))
040	{
041				// 子ノードのインデックス
042		int child = (2 * parent) + 1;
043				// 親ノードの値
044		int temp = data[parent];
045				// ヒープの生成
046		while (child < n) {
047					// 値が大きい（小さい）ほうの子ノードを選択する。
048			if (child < n-1 && !compare(data[child + 1], data[child]))
049				child = child + 1;
050					// 親ノードの値が子ノードの値より大きい（小さい）場合は何もしない。
051			if (!compare(temp, data[child]))
052				break;
053			else {   // temp が data[child] 以下（以上）の場合
054					// 親の要素に子を入れる
055				data[(child - 1) / 2] = data[child];
056					// 子ノードのインデックスを進める。
057				child = (2 * child) + 1;
058			}
059		}
060				// 親ノードとなる要素（最後の子供）に値を入れる
061		data[(child - 1) / 2] = temp;
062	}
063	
064	/***************************/
065	/* ヒープソート            */
066	/*      n : データの数     */
067	/*      data : データ      */
068	/*      compare : 比較関数 */
069	/***************************/
070	void heap(int n, int *data, bool (*compare)(int, int))
071	{
072				// ヒープの生成
073				//    data[k] : 親
074				//    data[k1], data[k2] : 子供，k1 = 2k+1, k2 = 2k+2
075				//       子供から見て親は：(k1-1) / 2 = (k2-1) / 2 = k
076				// 例 {1, 4, 2, 9, 0, 2, 8, 7, 3, 5}
077				// 結果 {9, 7, 8, 4, 5, 2, 2, 1, 3, 0}   昇順の場合
078				//    親 [0] 子 [1], [2]
079				//    親 [1] 子 [3], [4]
080				//    親 [2] 子 [5], [6]
081				//    親 [3] 子 [7], [8]
082				//    親 [4] 子 [9]
083		for (int i1 = (n-1) / 2; i1 >= 0; i1--)
084			heap_c(n, data, i1, compare);
085				// ヒープソート実行
086		for (int i1 = n - 1; i1 > 0; i1--) {
087			swap(data[0], data[i1]);   // 先頭を最後と交換
088			heap_c(i1, data, 0, compare);   // 残りの部分に対するヒープの生成
089		}
090	}
091	
092	#define N 5000000
093	
094	int main()
095	{
096					// 初期設定
097		int *data = new int [N];
098		init_genrand((unsigned)time(NULL));
099					// 昇順
100		clock_t tm1 = clock();
101		for (int i1 = 0; i1 < N; i1++)
102			data[i1] = genrand_int31();
103		clock_t tm2 = clock();
104		heap(N, data, ascend);
105		clock_t tm3 = clock();
106		printf("昇順（データ数： %d）\n", N);
107		printf("   data %d ms\n", (int)(tm2-tm1));
108		printf("   sort %d ms\n", (int)(tm3-tm2));
109					// 降順
110		tm1 = clock();
111		for (int i1 = 0; i1 < N; i1++)
112			data[i1] = genrand_int31();
113		tm2 = clock();
114		heap(N, data, descend);
115		tm3 = clock();
116		printf("降順（データ数： %d）\n", N);
117		printf("   data %d ms\n", (int)(tm2-tm1));
118		printf("   sort %d ms\n", (int)(tm3-tm2));
119					// 昇順（sort_heap）
120		tm1 = clock();
121		for (int i1 = 0; i1 < N; i1++)
122			data[i1] = genrand_int31();
123		tm2 = clock();
124		make_heap(data, data+N);
125		sort_heap(data, data+N);
126		tm3 = clock();
127		printf("昇順（sort_heap，データ数： %d）\n", N);
128		printf("   data %d ms\n", (int)(tm2-tm1));
129		printf("   sort %d ms\n", (int)(tm3-tm2));
130					// 降順（sort_heap）
131		tm1 = clock();
132		for (int i1 = 0; i1 < N; i1++)
133			data[i1] = genrand_int31();
134		tm2 = clock();
135		make_heap(data, data+N, descend);   // 関数
136		sort_heap(data, data+N, descend);
137	//	make_heap(data, data+N, greater<int>());   // 関数オブジェクト
138	//	sort_heap(data, data+N, greater<int>());
139	//	make_heap(data, data+N, [](int a, int b){ return a > b; });   // ラムダ式
140	//	sort_heap(data, data+N, [](int a, int b){ return a > b; });
141		tm3 = clock();
142		printf("降順（sort_heap，データ数： %d）\n", N);
143		printf("   data %d ms\n", (int)(tm2-tm1));
144		printf("   sort %d ms\n", (int)(tm3-tm2));
145	
146		return 0;
147	}

039 行目～ 062 行目

　　引数として渡された親（ parent ）に基づき，ヒープを作成するための関数です．親 data[parent] の子は，data[2*parent+1]，data[2*parent+2] になりますが，data[parent] の値が 2 つの子の大きい方より小さい場合は，その子と親を入れ替えます（昇順の場合）．さらに，子がその子を持つ場合は，子とその子の間で同様の処理を繰り返します．例えば，データ，

	data : {1, 4, 2, 9, 0, 2, 8, 7, 3, 5}　　データ数 n = 10

を昇順に並べる場合，083 行目～ 084 行目の処理によって，data の値は以下のように変化します．

i1 4 data 1 4 2 9 5 2 8 7 3 0
i1 3 data 1 4 2 9 5 2 8 7 3 0
i1 2 data 1 4 8 9 5 2 2 7 3 0
i1 1 data 1 9 8 7 5 2 2 4 3 0
i1 0 data 9 7 8 4 5 2 2 1 3 0

086 行目～ 089 行目

　　先頭と最後のデータを入れ替えた後，大きさ i1 の配列に対して，0 を親としたヒープを作成する，といった手順を繰り返しています．例えば，上で述べたデータに対しては，data の値は以下のように変化します．

i1 9 data 8 7 2 4 5 0 2 1 3 9
i1 8 data 7 5 2 4 3 0 2 1 8 9
i1 7 data 5 4 2 1 3 0 2 7 8 9
i1 6 data 4 3 2 1 2 0 5 7 8 9
i1 5 data 3 2 2 1 0 4 5 7 8 9
i1 4 data 2 1 2 0 3 4 5 7 8 9
i1 3 data 2 1 0 2 3 4 5 7 8 9
i1 2 data 1 0 2 2 3 4 5 7 8 9
i1 1 data 0 1 2 2 3 4 5 7 8 9

120 行目～ 144 行目

　　make_heap によってヒープを作成し，sort_heap によってソートしています．124 ～ 125 行目のように，3 番目の引数を省略した場合は，昇順にソートされます．135 ～ 140 行目では，ソート方法を指定しています．135 ～ 136 行目では上と同じように関数 descend を使用し，137 ～ 138 行目では関数オブジェクトを使用し，また，139 ～ 140 行目ではラムダ式を使用しています．

（出力）　このプログラムによって，以下に示すような結果が得られます．

昇順（データ数： 5000000）
   data 22 ms
   sort 1748 ms
降順（データ数： 5000000）
   data 25 ms
   sort 1695 ms
昇順（sort_heap，データ数： 5000000）
   data 22 ms
   sort 1102 ms
降順（sort_heap，データ数： 5000000）
   data 25 ms
   sort 1405 ms

クイックソート

　　クイックソートの手順は以下に示すとおりです．例えば，次のようなデータが与えられたとしまする．このとき，左端のデータ（ 37 ）を枢軸要素と呼び，この要素がソート後の正しい位置にくるように以下の処理を行います（昇順の場合）．

37 2 6 4 89 8 10 12 68 45
1. 配列の右端の要素から順に枢軸要素 ( 37 ) と比較していき 37 より小さな要素があれば，その要素を 37 と交換する．
  
  12 2 6 4 89 8 10 37 68 45
2. 配列の左端（正確には，上で 37 と交換した 12 の直後の要素）から順に枢軸要素 ( 37 ) と比較していき，37 より大きな要素があれば，その要素を 37 と交換する．
  
  12 2 6 4 37 8 10 89 68 45
3. 配列の右端（正確には，上で 37 と交換した 89 の直前の要素）から順に枢軸要素 ( 37 ) と比較していき，37 より小さな要素があれば，その要素を 37 と交換する．
  
  12 2 6 4 10 8 37 89 68 45
4. 以上の結果，37 の左には 37 より大きな要素はなく，またその右側には 37 より小さな要素は無い状態となる．つまり，37 は，ソート後の正しい位置にあることがわかる．
5. 37 の左側の配列（ 12 2 6 4 10 8 ），及び，右側の配列（ 89 68 45 ）に対して以上の処理を再帰的に繰り返す．
［演習３］上に示したアルゴリズムに従って，クイックソートを実行するプログラムを書き，バブルソートや選択ソートと実行時間を比較せよ（標準関数 qsort や C++ 標準ライブラリ内の sort を使用してはいけない）．なお，データ数は，5,000,000 個とする．また，様々なケースに対して正しく動作することを確認すること．