情報基礎A 「Cプログラミング」（ステップ７・ソーティング）

このページでは、配列に保存されている数の並べ替え（整列、sorting）について考える。

１．配列を使ったデータのソーティング

いきなりではあるが、身長がまちまちの人々が一列に並んでいる状態から、あなたの指示で、背の低いほうから大きい方に、順番に整列させ直したいとしよう。 このとき、（場所が大変手狭なので）、あなたが指示できることは、身長を見比べながら、列の中の二人を入れ替える操作のみ、という状況設定にしてみよう。 人数が１０名くらいならば、「テキトー」にやっても、すぐに作業は完了するだろうが、１００名くらいになると、きちんとした方針を立てないと、 うまくコトは運ばないだろう。

そんなとき、割合と自然に思える手順（のひとつ）は、

1. まず列全体を見渡し、一番身長の低い人を見つけ、列の先頭の人と、その人の場所を入れ替える。
2. 次に、先頭から2番目より後ろの中から、（つまり、列全体で一番小柄な現在の先頭の人は除いて）一番身長の低い人を見つけ、２番目の人とその人の場所を入れ替える。
3. このように、着目する位置を後方にずらしながら、その位置よりも後方の中で一番小柄な人を見つけ、入れ替えを行う。
4. 着目する位置が列の最後尾から一人前に到達したら、作業終了

ではないだろうか。これをプログラムとして実装するには

• 配列の注目する要素の場所（ここではiとしよう）を順にずらす。
• i以降で一番値の小さい要素の場所(jとしよう）を見つける
• i番目とj番目の要素（の値）を入れ替える

がCで記述できれば良さそうだ。 ４人の場合に、この方式で並べ替える過程を図示してみた：

注目個所の移動

注目個所を順に後ろにずらす処理は、for文を使えば、簡単にできそうだ。敢えて書くまでも無いが(Nを人数とすると）、

   int i ;
   ・・・
   for (i = 0 ; i<N-1 ; i=i+1) { 
        配列の中の最小値の場所を見つける処理
        入れ替える処理
   }

配列の中の最小値の場所を見つける

最小値を見つけ出す処理は、前のステップの説明なども参考にすると

#include <float.h>
float data[N] ;
int i,j,k ;
float min ;
・・・
min = FLT_MAX ;
for (k=i ; k<N ; k=k+1) {
    if (data[k]<min) {
         min = data[k] ;
         j = k ;
    }
}

といった形にまとめられるはずだ。ここで、Nはデータの総数のつもり。 また、FLT_MAXは、float型で表現できる最大値を表す記号である。 最小値の可能性のある場所毎に、その場所（kの値）を別の変数（j）に 記録しておくところがミソである。 そうすると、ループが終了した時点で、jには、最小値が見つかった場所がセットされている。

配列の中の２つの要素を入れ替える

これは、ここまで学んだ諸君には造作無い処理のはずだ。作業用の変数（ここではw）を用意して、

float w ;
・・・
w = data[i] ;
data[i] = data[j] ;
data[j] = w ;

とすればよい。

３つの処理を組み合わせる

以上の３つの工程をひとつのプログラムに組み立ててみたのが、以下に示す例である：

#include <stdio.h>
#include <float.h>
#define N 10          /* データの総数（10）を記号Nで表す */
main( )
{
    float data[N] = { 152.1, 175.3, 177.3, 144.7, 139.2, 
                      161.2, 153.1, 185.3, 168.3, 154.8 } ;
    int i,j,k ;
    float w,min ;

    for (i=0 ; i<N-1 ; i=i+1) {   /* 注目点を１つずつ変える */
        min = FLT_MAX ;             /* 最小値の出発値をセット */
        for (k=i ; k<N ; k=k+1) {   /* iから後ろを探す */
            if (data[k]<min) {        /* より小さな値を見つけたら */
                min = data[k] ;           /* その値と、          */
                j = k ;                   /*    場所を記憶しておく */
            }
        }
        w = data[i] ;               /* iとjの内容を入れ替える */
        data[i] = data[j] ;
        data[j] = w ;
    }

    for (i=0; i<N ; i=i+1) {      /* 確認のため、データを表示 */
         printf("%f\n",data[i]) ;
    }
}

２．バブルソート

上では、「場所iより後ろで一番小さな値を探す」方針で並べ替えを行ったが、（似てはいるが）別のアプローチも考えられる。 例えば

1. 注目点iを、列の先頭から順に後ろにずらす
2. iより後ろの人(j)とを一人ずつ比べ、jのほうが身長が低かったら、iと交換
3. iが最後尾より一人手前まで到達したら、おしまい。

この方法は、整列（ソーティング)の最も基本的なアルゴリズムとして知られ、バブルソート（bubble sort)と呼ばれている。 最小値を探す手間が省ける分、プログラムは簡単になる。 その一方で、「全てのペアについて調べる」ため、作業効率は悪い（上記の、最小値を探しながらの方法のほうが、処理は数倍速い）。

#include <stdio.h>
#include <float.h>
#define N 10          /* データの総数（10）を記号Nで表す */
main( )
{
    float data[N] = { 152.1, 175.3, 177.3, 144.7, 139.2, 
                      161.2, 153.1, 185.3, 168.3, 154.8 } ;
    int i,j ;
    float w ;

    for (i=0 ; i<N-1 ; i=i+1) {     /* 注目点を１つずつ変える */
        for (j=i+1 ; j<N ; j=j+1) {   /* i+1より後ろを探す */
            if (data[i]<data[j]) {        /* 順序が違っていたら */
                w = data[i] ;                    /* iとjの内容を入れ替える */
                data[i] = data[j] ;
                data[j] = w ;
            }
        }
    }

    for (i=0; i<N ; i=i+1) {      /* 確認のため、データを表示 */
         printf("%f\n",data[i]) ;
    }
}

計算の過程をイメージしやすくために、データが４件の場合に、整列が進んでいく様子を図示してみた：

ソーティングは、データ処理のあらゆる場面に必要な基本的な作業なので、効率的なアルゴリズムが色々と研究されている。 表題に「アルゴリズム」とある教科書には必ず登場する定番のトピックなので、これから先を勉強したい者は、 図書館などで探してみるとよい。