mk-mode BLOG

このブログは自作の自宅サーバに構築した Debian GNU/Linux で運用しています。
PC・サーバ構築等の話題を中心に公開しております。(クローンサイト: GitHub Pages

ブログ開設日2009-01-05
サーバ連続稼働時間
Reading...
Page View 合計
Reading...
今日
Reading...
昨日
Reading...

C++ - ソート処理各種テスト!

[ プログラミング, 数学 ] [ C言語 ]

こんばんは。

各種ソート処理について C++ で実装して速度を計測してみました。

以下、各種ソート処理の概要と C++ ソースです。

0. 前提条件

  • c++ (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3 での作業を想定。
  • 各種ソートの試行は以下のように行なった。
    • 1回のソートに使用するデータの個数は 1,000 個。
    • データそれぞれは 0 以上 10,000 未満の整数。
    • ソート試行(ループ)回数は、10,000 回。(1回のソートは一瞬であるため)
  • 各種ソートのアルゴリズムの詳細については説明しない。(必要なら、別途お調べください)
    ここでは、それぞれのアルゴリズムを C++ で実装して試行することに専念している。

1. 各種ソートについて

  • 基本交換法(バブル・ソート)
    隣接する2項を逐次交換する。原理は簡単だが交換回数が多い。
    計算量:
  • 基本選択法(直接選択法)
    数列から最大(最小)を探すことを繰り返す。比較回数は多いが交換回数は少ない。
    計算量:
  • 基本挿入法
    整列された部分数列に対し該当項を適切な位置に挿入することを繰り返す。
    計算量:
  • 改良交換法(クイック・ソート)
    数列の要素を1つずつ取り出し、それが数列の中で何番目になるかその位置を求める。
    計算量:
  • 改良選択法(ヒープ・ソート)
    数列をヒープ構造(一種の木構造)にしてソートを行う。
    計算量:
  • 改良挿入法(シェル・ソート)
    数列を飛び(gap)のあるいくつかの部分数列に分け、そのそれぞれを基本挿入法でソートする。
    計算量:

2. C++ ソースコード作成

以下のように、作成してみた。(ヘッダファイルとメイン、サブとファイルを分割している)

SortTest.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
/***********************************************************
 * ソート処理各種のテスト
 *
 * コンパイル方法:
 * $ g++ -Wall -O2 -o SortTest Sort.h Sort.cpp SortTest.cpp
 **********************************************************/
#include <iostream>
#include "Sort.h"

using namespace std;

/*
 * メイン処理
 */
int main()
{
    try
    {
        // ==== インスタンス化
        Sort objSort;

        // ==== ソート処理実行
        objSort.exec();
    }
    catch (...) {
        // ==== 異常終了
        cout << "例外発生!" << endl;
        return -1;
    }

    // ==== 正常終了
    return 0;
}
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
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++) {
        // 元データ配列から1つヒープ要素として追加
        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++ ソースコンパイル

以下のコマンドで C++ ソースをコンパイルする。
-Wall は警告出力、-O2 最適化のオプション)

1
$ g++ -Wall -O2 -o SortTest Sort.h Sort.cpp SortTest.cpp

何も出力されなければ成功。

4. 実行

実際に実行してみる。

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
$ ./SortTest

#### 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. 結果

何回か実行してみた結果、処理の早い順は大体以下のようになった。(「改良選択法」と「改良交換法」は、入れ替わることもあった)

  1. 改良選択法(ヒープ・ソート(下方移動))
  2. 改良選択法(ヒープ・ソート(上方移動))
  3. 改良交換法(クイック・ソート)
  4. 改良挿入法(シェル・ソート)
  5. 基本挿入法
  6. 基本選択法(直接選択法)
  7. 基本交換法(バブル・ソート)

多方面で使用することのあるアルゴリズムについてでした。
情報処理技術者試験等でよく出題されるアルゴリズムですが、実際に使用する局面も多々ありますし。。。

以上。

Comments