バブルソートを覚えた。

最近アルゴリズムの勉強はじめたので、少しずつアウトプットしていこうかと思います。

今回はバブルソートについて。

バブルソートはリストにおいて最後尾の要素を基点として、隣同士の要素の値を比較して条件に応じた交換を行う整列アルゴリズムです。

条件とは値の大小関係です。「値の大きい順(降順)」か「値の小さい順(昇順)」にリストを並び替えます。

このソートを実行すると値の大きいまたは小さい要素が浮かびあがってくるように見えることから、バブル(bubble: 泡)ソートと呼ばれているそうです。

例として、ある数値の集合を降順にソートします。

int x[7] = {5, 4, 3, 0, 10, 15, 6};
int i, j, tmp;

for (i = 0; i < 7-1; i++){
  for (j = 7-1; j > i; j--){
    /* 前の要素の方が小さかったらswapする */
    if (x[j] > x[j-1]){ 
      tmp = x[j];　
      x[j] = x[j-1];
      x[j-1] = tmp;
    }
  }
}

(結果)
x[7] = {15, 10, 6, 5, 4, 3, 0}

となる。