８．ソーティング（選択ソート・バブルソート）

８．１．ソーティングとは

ある集合に属する要素の有限列（同じ要素が２回以上現れてもよい）が与えられた時、与えられた順序に従って要素を並べ換えることを「ソーティング」と言います。例えば3の倍数からなる自然数集合に属する数10個を、小さい数から順に並べ替えることはソーティングです。数字に限らず、文字列でも人間でも比較の方法さえ決まってさえいれば、ソーティングをすることができます。

８．２．選択ソート（selection sort）

n個の数字を昇順（小さいもの順）に並べるアルゴリズムとして、最も単純なものは以下のようなものです。

n個の中から最も小さい数字を探し、それを1番目の数字と入れ替える。
残りのn-1個の中から最も小さい数字を探し、それを2番目の数字と入れ替える。
この処理をn-1回繰り返す。

このアルゴリズムを「選択ソート」（単純選択法）と呼びます。これを実装したサンプルプログラムを以下に示します。5～12行目は乱数を発生させて指定個の数字を持つ配列を生成する関数で、14～31行目は選択ソートを実行する関数、33～38行目は配列内部の数字を表示する関数です。このサンプルを実行すると、最初に10個の乱数列が表示され、最後にソート後の数列が表示されます。

1: #include<stdio.h>
2: #include<stdlib.h>
3: #include<time.h>
4:
5: void create_array(int num[],int length){
6:   int i;
7:
8:   srand(time(NULL));
9:   for(i=0;i<length;i++){
10:    num[i]=rand()%100;
11:  }
12:}
13:
14:void selection_sort(int num[],int length){
15:  int i,n,tmp;
16:  int min,min_pos;
17:
18:  for(i=0;i<length-1;i++){
19:    min=num[i]; //仮の最小値を最初の数にセット
20:    min_pos=i;  //仮の最小値の場所も覚える
21:    for(n=i+1;n<length;n++){
22:      if(num[n]<min){ //比較対象の数字が仮の最小値より小さければ、仮の最小値をそれにする
23:        min=num[n];
24:        min_pos=n;
25:      }
26:    }
27:    tmp=num[i]; //最小値と最初の数を入れ替え
28:    num[i]=min;
29:    num[min_pos]=tmp;
30:  }
31:}
32:
33:void print_array(int num[],int length){
34:  int i;
35:  for(i=0;i<length;i++){
36:    printf("num[%d]=%d\n",i,num[i]);
37:  }
38:}
39:
40:int main(int argc,char *argv[]){
41:  int length=10;
42:  int num[length];
43:
44:  create_array(num,length);
45:  print_array(num,length);
46:  puts("");
47:  selection_sort(num,length);
48:  print_array(num,length);
49:
50:  return(0);
51:}

(実習課題）

８．１のサンプルプログラムを改良しなさい。

2つのプログラムに分ける。1つは乱数を発生させて、ファイルに1行ずつ数字を書き込むプログラム（乱数発生プログラム）。もう1つは読み込んだファイルを選択ソートして、標準出力に出力するプログラム（選択ソートプログラム）。（乱数発生プログラムは後の章でも使用する）
乱数発生プログラムで実行時に指定されるオプションは、「発生させる数の個数」と「数字を書き込むファイル名」。発生させる数は1以上1000以下とする。
選択ソートプログラムで実行時に指定されるオプションは、「数字が書き込まれたファイル名」と「ソートする数の個数」（つまりファイルの行数）。
選択ソートプログラムでソーティングしている関数を、再帰呼び出しを使用するように改良する。
（ヒント）n個の選択ソートとは、n個の中から最小のものを見つけ出した後、残りのn-1個に対して選択ソートを実行することである。

　1　2

８．２．バブルソート

選択ソートは最小値を探すとき、「仮の最小値」と「仮の最小値の場所」の2つの情報を覚えていなければなりません。それらを覚えずにすむように改良したものが、「バブルソート」です。バブルソートのアルゴリズムは以下の通りです。今回もn個の数列を昇順に並べ替える場合を例にしています。

n個の数の中から最小のものを1番目にする。その際、以下のようにする。
- n番目とn-1番目を比較し、n番目の方が小さければ入れ替える。
- n-1番目とn-2番目を比較し、n-1番目の方が小さければ入れ替える。
- 同様の処理をn-1回繰り返すと、1番目にn個の中から最も小さい数字がくる。
1番目を除いたn-1個の数に対して、上記の作業を行う。すると2番目にn-1個の中から最小の数字（つまりn個の中で2番目の小さい数字）がくる。
同様の処理をn-1回繰り返す。