9．配列を使ったプログラム（ソートを例に）

　値の大きい順，あるいは小さい順に並べることをソートという．例えば，9, 5, 10, 3, 1の5つの数字を小さい順（昇順:ascending order）に並べ替えることを考える．どうしたら実現できるでしょう？

バブルソート(bubble sort)
　ちょっと人が考えるやり方とは違うけれどもプログラムしやすい方法です。

　隣接する要素を順に比較しながら入れ替える方法です。いま、配列dataに９，５，１０，３，１（データ数N=5）が順に入っていたとしましょう。0番目の要素(9)と1番目の要素(5)を比べて，左側の要素の方が大きいので入れ替えます。続いて、新たに1番目の要素になった9と2番目の要素10を比較すると，左側の要素が小さいのでそのまま。この整列の様子を下図に示します。下線部分が比較する位置です。

　上の図でj番目とj+1番目を比較することを繰り返すとなるとjは0番目から3番目まで変化させればいいという事を覚えておいてください。

　隣同士を比較して、順番が違っていれば交換します。これを左端(0番目)から右端の一つ手前(3番目)まで繰り返すと、最初の並びがどうなっていても一番右端が最大値になります。なので次は、左端（0番目）から2番目まで比較・交換をします。

　これを繰り返していくと4回目ですべて整列が完了します。これをプログラムしましょう。【値の交換】まず、配列の要素を交換する部分を考えます。data[j]とdata[j+1]の値を交換するにはどうしたらいいでしょう？
data[j]=data[j+1];
data[j+1]=data[j]; 

　とするとどうなるか。最初の代入文でdata[j]にはdata[j+1]に入っていた値が入ります。次の代入文で、今data[j]に入っている値がdata[j+1]に入りますので、どちらの値も元々のdata[j+1]の値になってしまいます。値を交換するには、一旦別の変数に入れる必要があります。
tmp=data[j];
data[j]=data[j+1];
data[j+1]=tmp;
　これで、値の交換ができます。

【端から順に比較し違っていれば交換】　続いて、端から端まで隣同士を比較して左の方が大きければ値を交換するプログラムを考えます。
for(j=0; j<N-1;j++){
   if(data[j]>data[j+1]){
        tmp=data[j]; data[j]=data[j+1]; data[j+1]=tmp;   // 値を交換する。
   }
}

【端から順に比較をN-1回繰り返す】　これを上のfor文を1回やると一番右側に最大値が移動し、データ数N-1回繰り返すと全体がソートされるわけですので、上のfor文をN-1回繰り返すことを考えると次のプログラムになります。少し最初の値を変えていますが、動作を理解しやすくするためです。(プロジェクト名no13で、ソース名はbubble1.cとしました）

【プログラムの効率化】　このプログラムでちゃんとソートできます。配列dataの要素を増やして、Nの値を変えれば大きな要素数でもソート可能です。但し、ちょっとこのプログラムでは無駄があります。最初に説明したように一度jのfor文を実行すると一番右側に最大値が来るので2回目は比較する要素を一つ減らせます。3回目は２つ減らせます。それを考慮したのが次のプログラムです。17行目が変わっていて、少しプログラムが早くなります。

演習1　値を降順にバブルソートするプログラムを作成せよ。

演習2　バブルソートのプログラムを右端から比較していくプログラムに変更せよ。