なんとなくわかる「バブルソート」

スポンサーリンク

バブルソートとは

バブルソート(Bubble sort)とは、数字の配列に対して配列内の1つの数字とその次にある数字を比較して大きい方を上にあげる行為を繰り返してソートをするアルゴリズムです。バブルと言われているように大きいもの(小さいもの)が上に浮いていくような動作をします。

バブルソートはソートのアルゴリズムの中でも動きとしてはわかりやすいものになります。

例えば、配列[4,2,6,8,5]が存在し、昇順にしたいときは

  1. 8と5を比較して8が大きいので入れ替え→[4,2,6,5,8]
  2. 6と5を比較して5が大きいので入れ替え→[4,2,5,6,8]
  3. 2と5を比較して5が大きいのでそのまま→[4,2,5,6,8]
  4. 4と2を比較して4が大きいので入れ替え→[2,4,5,6,8]
  5. 終了!

という流れで入れ替えを繰り返してソートをします。

バブルソートの実装

C言語

#include<stdio.h>

int main(void){
 /*ソートする配列*/
int array[5]=[4,2,6,8,5];
int array_size = 5;
/*iとjはソートに使うfor文の変数,tempは入れ替え時の数字の保持に利用*/
int temp, i, j;

for(i = 0; i < (array_size - 1); i++){
for(j = (array_size - 1); i < j ; j--){
    /*2つの数字の比較、j-1が大きい時には入れ替える*/
if(array[j]<array[j-1]){
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}
}
}

printf("配列:[%d,%d,%d,%d,%d]",array[0],array[1],array[2],array[3],array[4]);
return 0;
}

for文を2個用いて配列の1つ目の数字から確定させていきます。

手順は変数jを用いて配列の一番後ろとその手前を比較して小さい方を後ろから2番目の位置にし、次は後ろから2番目と3番目を比較、その次に後ろか3番目と4番目という風に先頭に一番小さい数字がいくようになります。

その結果一番先頭の数字が確定し、変数iをインクリメントして先頭から2番目の数字を決めていきます。

コメント

タイトルとURLをコピーしました