並べ替えのプログラム

エディタでソースプログラムを書いて，コンパイル・実行する．

並べ替えの問題

N個のデータ

data1,data2,...,dataN

が与えられているとする．データ間に何らかの順序（<）が定められていると仮定する（たとえば，数値の大小や文字列の辞書式順序など）．このとき，定められた順序に基づいてN個のデータを並べて

data_i1 < data_i2 < ... < data_iN

とすることを並べ替え（ソート: sort）という．

小さいものから大きなものへと並べることを昇順，その逆に，大きなものから小さなものへと並べることを降順という．

与えられたデータを順序を付けて並べ替える処理は，多くの処理で頻繁に使われる．こうした実際的な必要に迫られて，並べ替えのアルゴリズムは深く研究されている．

以下に，N個の数値データが1次元配列

a[0], a[1], ... ,a[N-2], a[N-1]

に格納されているとして，2つの方法で並べ替えプログラムを実行してみよう．

単純選択ソート

通称'馬鹿ソート'と呼ばれる並べ替えのアルゴリズムで，配列変数 a[i]の値が，それよりも大きな添字を持つ配列要素の値a[j] （i < j）を比較して，

a[j] >= a[i]，

つまり，a[i]がa[j]より小さいかまたは等しければそのままにしておき，もし

a[j] < a[i]，


つまり，a[i]の方がa[j]より大きければ，これらの値を入れ替える操作を，添字iの値を0からN-2まで繰り返すことによって並べ替える方法である．
添字iの値をN-1までにすると，それより大きな添字jを持つ配列成分，たとえばa[N]は存在しない．
したがって，iの値はN-1まででよい．

このアルゴリズムは，次のように表すことができる．

for i := 0 to N - 2 do
    for j := i + 1 to N - 1 do
        if (a[j] < a[i]) then
            begin
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            end;


このアルゴリズムをC言語の完全なプログラムとして書くと次のようになる．
C言語では，/*と*/で挟まれた文字列は無視されてコメントとして使われる．

　　　　　　　　　　（ファイル名：simple_sort.c）
#include <stdio.h>     /* for printf() */
#include <stdlib.h>    /* for rand(): 0からRAND_MAXまでの乱数 */
#include <time.h>      /* for clock(): プロセッサ時間の取得 */

#define SIZE 5000    /* 配列の大きさ */

void main()
{
    int a[SIZE];
    int i, j, tmp;
    time_t start_t, end_t;

    for (i = 0; i < SIZE; i++)   /* 配列成分の初期化 */ 
        a[i] = rand();

    printf("Simple sort\ncaluculating now ....");
    start_t = clock();             /* 並替えの開始 */

    /* 並替えの計算 */
    for (i = 0; i < SIZE - 1; i++)
        for (j = i + 1; j < SIZE; j++)
	    if (a[j] < a[i])       /*  <: 昇順,  >: 降順  */
            {
                tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            };

    end_t = clock();                /* 並替えの終了 */

/*    for (i = 0; i < SIZE; i++)
        printf("%d -> %d\n", i, a[i]); 並替えデータの表示*/

    printf("Num. of Data = %d\n", SIZE);
    printf("time = %2.3f (sec)\n",(double)(end_t - start_t)/CLOCKS_PER_SEC);

}


このプログラムは以下のような工夫をしている．

プログラムの先頭部分に#define文により，配列要素の数を定める定数をSIZEとして定義した（この例では5000となっている）．
この値を変えることによって，並べ替えのためのデータ数（配列要素の数）を調節できる．
並べ替えのためのデータを乱数によって発生させ，配列変数aに格納している．
C言語では，乱数の発生は，組込み関数rand()によって行なう．
並べ替えに要する時間を計測するために，並べ替えアルゴリズムを実行する直前と直後にプロセッサ時刻を取得し，その差によって実行時間を計算して表示している．
C言語では，プロセッサ時刻の取得は，組込み関数clock()によって行なう．



クイックソート
クイックソート（quicksort）は1962年にC.A.R. Hoareが開発したアルゴリズムで，一般的データに対して最も早いアルゴリズムとして有名である（
このアルゴリズムの詳細は省略する）．

C言語では，クリックソートのためのライブラリ関数としてqsort()が用意されている．
qsort()を使うためには，比較関数を別に定義しなければならない．
以下のプログラムでは，比較関数をcomp()として定義していることに注意する．

　　　　　　　　　　（ファイル名：quick_sort.c）
#include <stdio.h>    /* for printf()  */
#include <stdlib.h>   /* for qsort(), rand(): 0からRAND_MAXまでの乱数 */
#include <time.h>     /* for clock(): プロセッサ時間の取得 */

#define SIZE 5000     /* 配列の大きさ */


int comp(int *x, int *y)    /* 比較関数 */
{
    if (*x < *y)            /*  <: 昇順,  >: 降順  */
        return(-1);
    else if (*x > *y)
        return(1);
    else
        return(0);
}

void main()
{
    int a[SIZE];
    int i, j, tmp;
    int comp();
    time_t start_t, end_t;

    for (i = 0; i < SIZE; i++)         /* 配列成分の初期化 */ 
        a[i] = rand();

    printf("caluculating now ....");
    start_t = clock();                 /* 並替えの開始 */

    qsort(a, SIZE, sizeof(int), comp); /* quick sortの計算 */

    end_t = clock();                   /* 並替えの終了 */

    printf("Num. of Data = %d\n", SIZE);
    printf("time = %2.4f (sec)\n",(double)(end_t - start_t)/CLOCKS_PER_SEC);

}



2つのプログラムの比較
上の単純ソートプログラムをsimple_sort.c，クイックソートプログラムをquick_sort.cとして保存する．
これらのプログラムを

% gcc -o sinple_sort simple_sort.c
     および
% gcc -o quick_sort quick_sort.c


とコンパイルする．
このとき，でき上がる実行ファイル名はそれぞれsimple_sortとquick_sortで，次のようにしてプログラムを実行できる．

% simple_sort
     および
% quick_sort





演習

SIZEを20程度にして，上のプログラムsimple_sort.cでコメントにしているソート結果の表示部分のコメントをはずして，実際に昇順に並べ替えられていることを確かめよ．

SIZEを100から10,000程度までさまざまに変えて，次の計測時間表を完成せよ．



サイズ 単純(sec) クイック(sec)


100 


500 


1000 


2000 


3000 


4000 


5000 


6000 


7000 


8000 


9000 


10000 






情報処理概論目次