C++ - ソート処理各種テスト！
Updated:
各種ソート処理について C++ で実装して速度を計測してみました。
以下、各種ソート処理の概要と C++ ソースです。
0. 前提条件
- c++ (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3 での作業を想定。
- 各種ソートの試行は以下のように行なった。
- １回のソートに使用するデータの個数は 1,000 個。
- データそれぞれは 0 以上 10,000 未満の整数。
- ソート試行（ループ）回数は、10,000 回。（１回のソートは一瞬であるため）
- 各種ソートのアルゴリズムの詳細については説明しない。（必要なら、別途お調べください）
ここでは、それぞれのアルゴリズムを C++ で実装して試行することに専念している。
1. 各種ソートについて
- 基本交換法（バブル・ソート）
隣接する２項を逐次交換する。原理は簡単だが交換回数が多い。
計算量：\(O(n^{2})\) - 基本選択法（直接選択法）
数列から最大（最小）を探すことを繰り返す。比較回数は多いが交換回数は少ない。
計算量：\(O(n^{2})\) - 基本挿入法
整列された部分数列に対し該当項を適切な位置に挿入することを繰り返す。
計算量：\(O(n^{2})\) - 改良交換法（クイック・ソート）
数列の要素を１つずつ取り出し、それが数列の中で何番目になるかその位置を求める。
計算量：\(O(n log_{2}n)\) - 改良選択法（ヒープ・ソート）
数列をヒープ構造（一種の木構造）にしてソートを行う。
計算量：\(O(n log_{2}n)\) - 改良挿入法（シェル・ソート）
数列を飛び(gap)のあるいくつかの部分数列に分け、そのそれぞれを基本挿入法でソートする。
計算量：\(O(n^{1.2})\)
2. C++ ソースコード作成
以下のように、作成してみた。（ヘッダファイルとメイン、サブとファイルを分割している）
File: sort_test.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/***********************************************************
* ソート処理各種のテスト
**********************************************************/
#include <iostream>
#include "sort.h"
using namespace std;
/*
* メイン処理
*/
int main()
{
try
{
// ==== インスタンス化
Sort objSort;
// ==== ソート処理実行
objSort.exec();
}
catch (...) {
// ==== 異常終了
cout << "例外発生！" << endl;
return -1;
}
// ==== 正常終了
return 0;
}
File: sort.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#ifndef INCLUDED_SORT_H
#define INCLUDED_SORT_H
#include <stdio.h>
#include <time.h>
#define N 1000 // データ個数
#define M 10000 // 値 MAX ( M 未満 )
#define L 10000 // ソート試行回数
/*
* ソートクラス
*/
class Sort
{
// 各種変数
double tt; // 計算時間
clock_t t1, t2; // 計算開始CPU時刻、計算終了CPU時刻
int i, j, k, l; // Loop インデックス
int base[N]; // 元データ用配列
int a[N]; // 作業用配列
int h[N + 1]; // 作業用配列(ヒープ・ソート用)
int min, s, t, gap, m, n, p, w; // ソート処理用ワーク
public:
Sort(); // コンストラクタ
void exec(); // ソート処理実行
private:
void sort_bubble(int *); // 基本交換法(バブル・ソート)
void sort_selection(int *); // 基本選択法(直接選択法)
void sort_insertion(int *); // 基本挿入法
void sort_quick(int *); // 改良交換法(クイック・ソート)
void sort_heap_up(int *); // 改良選択法(ヒープ・ソート)(上方移動)
void sort_heap_down(int *); // 改良選択法(ヒープ・ソート)(下方移動)
void sort_shell(int *); // 改良挿入法(シェル・ソート)
void quick(int *, int, int); // クイック・ソート用再帰関数
void generate_heap_up(int *, int *); // ヒープ・ソート用ヒープ作成(上方移動)関数
void generate_heap_down(int *); // ヒープ・ソート用ヒープ作成(下方移動)関数
void swap(int *, int *); // ヒープ・ソート用スワップ関数
void copy_array(int *, int *); // 配列コピー
void display(int *, double, int); // 結果出力
};
#endif
File: sort.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
#include <cstdlib> // for srand()
#include "sort.h"
using namespace std;
/*
* コンストラクタ
*/
Sort::Sort()
{
// 元になる配列を生成
srand((unsigned int)time(NULL));
printf("#### Base Array\n");
for (i = 0; i < N; i++) {
base[i] = rand() % M;
printf("%5d ", base[i]);
if ((i + 1) % 10 == 0) printf("\n");
}
printf("\n");
}
/*
* 計算
*/
void Sort::exec()
{
// 基本交換法（バブル・ソート）
printf("%-22s", "1 : Bubble Sort");
sort_bubble(base);
// 基本選択法（直接選択法）
printf("%-22s", "2 : Selection Sort");
sort_selection(base);
// 基本挿入法
printf("%-22s", "3 : Insertion Sort");
sort_insertion(base);
// 改良交換法（クイック・ソート）
printf("%-22s", "4 : Quick Sort");
sort_quick(base);
// 改良選択法（ヒープ・ソート）（上方移動）
printf("%-22s", "5-1: Heap Sort(Up)");
sort_heap_up(base);
// 改良選択法（ヒープ・ソート）（下方移動）
printf("%-22s", "5-2: Heap Sort(Down)");
sort_heap_down(base);
// 改良挿入法（シェル・ソート）
printf("%-22s", "6 : Shell Sort");
sort_shell(base);
}
/*
* 基本交換法（バブル・ソート）
*/
void Sort::sort_bubble(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
for (i = 1; i < N - 1; i++) {
for (j = N - 1; j > i; j--) {
if (a[j] < a[j - 1]) {
t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* 基本選択法（直接選択法）
*/
void Sort::sort_selection(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
for (i = 0; i < N - 1; i++) {
min = a[i];
s = i;
for (j = i + 1; j < N ; j++) {
if (a[j] < min) {
min = a[j];
s = j;
}
}
t = a[i];
a[i] = a[s];
a[s] = t;
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* 基本挿入法
*/
void Sort::sort_insertion(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
for (i = 1; i < N; i++) {
for (j = i - 1; j >= 0; j--) {
if (a[j] > a[j + 1]) {
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
} else {
break;
}
}
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* 改良交換法 (クイック・ソート)
*/
void Sort::sort_quick(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
quick(a, 0, N - 1);
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* 改良選択法 (ヒープ・ソート)(上方移動)
*/
void Sort::sort_heap_up(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 初期ヒープ作成(上方移動)
generate_heap_up(h, base);
// ソート処理
n = N; // データ個数
m = N; // n の保存
while (n > 1) {
swap(&h[1], &h[n]);
n--; // 木の終端切り離し
p = 1;
s = 2 * p;
while (s <= n) {
if (s < n && h[s + 1] > h[s]) s++;
if (h[p] >= h[s]) break;
swap(&h[p], &h[s]);
p = s;
s = 2 * p;
}
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(h, tt, 1);
}
/*
* 改良選択法 (ヒープ・ソート)(下方移動)
*/
void Sort::sort_heap_down(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 元の配列を元の木としてコピー
for (i = 1; i <= N; i++)
h[i] = base[i - 1];
// 初期ヒープ作成(下方移動)
generate_heap_down(h);
// ソート処理
n = N; // データ個数
m = N; // n の保存
while (n > 1) {
swap(&h[1], &h[n]);
n--; // 木の終端切り離し
p = 1;
s = 2 * p;
while (s <= n) {
if (s < n && h[s + 1] > h[s]) s++;
if (h[p] >= h[s]) break;
swap(&h[p], &h[s]);
p = s;
s = 2 * p;
}
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(h, tt, 1);
}
/*
* 改良挿入法 (シェル・ソート)
*/
void Sort::sort_shell(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
gap = N / 2;
while (gap >0) {
for (k = 0; k < gap; k++) {
for (i = k + gap; i < N; i += gap) {
for (j = i - gap; j >= k; j -= gap) {
if (a[j] > a[j + gap]) {
t = a[j];
a[j] = a[j + gap];
a[j + gap] = t;
} else {
break;
}
}
}
}
gap /= 2;
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* クイック・ソート用再帰関数
*/
void Sort::quick(int *a, int left, int right)
{
if (left < right) {
s = a[left]; // 最左項を軸にする
i = left; // 軸より小さいグループ
j = right + 1; // 軸より大きいグループ
while (1) {
while (a[++i] < s);
while (a[--j] > s);
if (i >= j) break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
a[left] = a[j];
a[j] = s; // 軸を正しい位置に挿入
quick(a, left, j - 1); // 左部分列に対する再帰呼び出し
quick(a, j + 1, right); // 右部分列に対する再帰呼び出し
}
}
/*
* ヒープ・ソート用ヒープ生成（上方移動）関数
*/
void Sort::generate_heap_up(int *heap, int *base)
{
for (i = 1; i <= N; i++) {
// 元データ配列から１つヒープ要素として追加
heap[i] = base[i - 1];
s = i; // 追加要素の位置
p = s / 2; // 親要素の位置
while (s >= 2 && heap[p] < heap[s]) {
w = heap[p];
heap[p] = heap[s];
heap[s] = w;
s = p; // 追加要素の位置
p = s / 2; // 親要素の位置
}
}
}
/*
* ヒープ・ソート用ヒープ生成（下方移動）関数
*/
void Sort::generate_heap_down(int *heap)
{
n = N; // データ個数
for (i = n / 2; i >= 1; i--) {
p = i; // 親要素の位置
s = 2 * p; // 左の子要素の位置
while (s <= n) {
if (s < n && heap[s + 1] > heap[s]) s++; // 左右子要素の小さい方
if (heap[p] >= heap[s]) break;
swap(&heap[p], &heap[s]); // 交換
p = s; // 親要素の位置
s = 2 * p; // 左の子要素の位置
}
}
}
/*
* ヒープ・ソート用スワップ関数
*/
void Sort::swap(int *a, int *b)
{
t = *a;
*a = *b;
*b = t;
}
/*
* 結果出力
* k = 0 (ヒープ以外用)
* k = 1 (ヒープ用)
*/
void Sort::display(int *a, double tt, int k)
{
// ソート結果確認
// (ソート結果を確認したければ、以下のコメント解除)
//printf("\n");
//for (i = k; i < N + k; i++) {
// printf("%5d ", a[i]);
// if ((i + 1 - k) % 10 == 0) printf("\n");
//}
// 処理時間出力
printf("Time: %6.2lf sec.\n", tt);
}
3. C++ ソースコンパイル
（-Wall は警告出力、-O2 最適化のオプション）
$ g++ -Wall -O2 -o sort_test sort.h sort.cpp sort_test.cpp
何も出力されなければ成功。
4. 実行
$ ./sort_test
#### Base Array
3363 658 6626 6241 6913 524 7298 7813 6854 5659
7515 9857 6991 1365 1699 9280 3575 5902 3565 9067
4318 9795 9867 8825 2972 1451 9100 5907 4745 6697
9229 8108 3707 5855 4350 620 6379 8000 8434 3233
11 2301 9442 7002 3666 1141 6283 3594 3396 9848
9013 4066 9643 8880 2891 8967 6683 8343 1226 1429
1392 455 9537 5100 6310 239 2072 9041 4592 6858
2274 4603 9160 8068 7958 2826 9210 593 2772 8958
441 1785 3024 6437 665 2267 1756 3701 6963 2983
5130 8355 3438 1019 3455 6101 7611 5528 5142 2203
====< 途中省略 >====
560 1082 5720 3416 8565 7506 5820 2002 6923 7262
5790 4352 1380 5314 5603 1346 4262 9839 5431 9088
6807 7771 8492 4661 2574 8774 3475 5575 5246 7110
2425 5806 8192 8146 5575 3109 5652 7747 5112 8927
5009 7254 3280 6389 8920 5235 4087 3182 1427 9518
8622 8234 7289 7114 2895 6216 2241 2722 1791 7487
9832 4216 9645 8025 8714 5220 1134 4367 9319 2598
3294 4328 6204 2926 7069 5125 8162 7508 4659 5941
3378 9634 4175 668 3100 7071 3236 5341 9793 5027
9180 5978 5595 8826 4003 662 398 1489 5029 9718
1 : Bubble Sort Time: 15.92 sec.
2 : Selection Sort Time: 9.12 sec.
3 : Insertion Sort Time: 4.29 sec.
4 : Quick Sort Time: 0.69 sec.
5-1: Heap Sort(Up) Time: 0.68 sec.
5-2: Heap Sort(Down) Time: 0.64 sec.
6 : Shell Sort Time: 0.80 sec.
4. 結果
何回か実行してみた結果、処理の早い順は大体以下のようになった。（「改良選択法」と「改良交換法」は、入れ替わることもあった）
- 改良選択法（ヒープ・ソート（下方移動））
- 改良選択法（ヒープ・ソート（上方移動））
- 改良交換法（クイック・ソート）
- 改良挿入法（シェル・ソート）
- 基本挿入法
- 基本選択法（直接選択法）
- 基本交換法（バブル・ソート）
多方面で使用することのあるアルゴリズムについてでした。
情報処理技術者試験等でよく出題されるアルゴリズムですが、実際に使用する局面も多々ありますし。。。
以上。
Comments