C++ source code to test sorting algorithms.

sort.cpp

#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);
}

sort.h

#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_test.cpp

/***********************************************************
 * ソート処理各種のテスト
 **********************************************************/
#include <iostream>
#include "sort.h"

using namespace std;

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

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

    // ==== 正常終了
    return 0;
}