C言語プログラミング バブルソート
C言語のソート紹介シリーズ、挿入ソート、シェルソート、選択ソートと来て今回はバブルソート(基本交換法)を紹介いたします。
計算時間が遅いため実用的ではないです。
ただ、非常に簡潔な仕組みのため、ソートという操作の概念を理解しやすいかと思います。
たとえば、最後尾に最も大きい値、先頭に最も小さい値を持ってきたい場合……先頭とその次を比べて順番が逆だったら入れ替え、先頭の次とそのさらに次を比べて順番が逆だったら入れ替え……これを最後まで繰り返すと最後尾に最も大きな値が来ます。再び同じことを今度は先頭から最後尾の一つ前まで繰り返せば、最後尾に一番大きい数、最後尾の一つ前に二番目に大きい数が来ます。これを全体が順番通りになるまで繰り返すのがバブルソートです。
データが「８５４２６３７１」のときの数値の変化例は以下の通りです。
・左から順番に隣り合った文字同士を比べる。大きい方が右に行くように交換していく。結果、一番大きい数値が一番右に来る。「５４２６３７１(８)」
・残った中で一番大きい数値が残った中の一番右に来る。「４２５３６１(７)８」
・残った中で一番大きい数値が残った中の一番右に来る。「２４３５１(６)７８」
・残った中で一番大きい数値が残った中の一番右に来る。「２３４１(５)６７８」
・残った中で一番大きい数値が残った中の一番右に来る。「２３１(４)５６７８」
・残った中で一番大きい数値が残った中の一番右に来る。「２１(３)４５６７８」
・残った中で一番大きい数値が残った中の一番右に来る。「１(２)３４５６７８」
以下、C言語で書いたバブルソートのプログラムです。
ソートを行う関数部分のみです。
/* バブルソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i,j,temp;
for(i=num-1;i>0;i--){
for(j=0;j<i;j++){
if(data[j]>data[j+1]){
/*データの入れ替え*/
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
}
}
}
/* バブルソート関数ここまで */
Wikipedia ソート
Wikipedia バブルソート
Wikipedia C言語