バブルソート

バブルソート

隣合う数字の大小を比較しながら整列させるソートのことです。
実装する中身が

n × n

となるためにO(n^2)となるので、整列のアルゴリズムとしては遅いようです。
なので、要素が短いという条件意外では使えそうもないです。



では、例を見ていきます。


初期データ5個の整数を持つとします。


80 20 17 41 4


これをバブルソートを利用して、昇順にソートしていく過程を見ていきます。
赤色がソート対象となる値で、青がソート完成した値です。

80 20 17 41 4

20 80 17 41 4

20 17 80 41 4

20 17 41 80 4

20 17 41 4 80


20 17 41 4 80

一回目のforループが終わって末端に最大値が来ました。

次はまた、最初の数値から見て、末端を除いて値を交換していきます。


20 17 41 4 80

17 20 41 4 80

17 20 41 4 80

17 20 4 41 80

17 20 4 41 80




5列目と4列目が固定されました。
後は同じように整列を続けます。


では、これをc言語のコードにしてみます。

/*
 x[] = sortしたい配列
 n = 配列要素の最大数
*/
void BubbleSort(int x[ ], int n)
{
 int temp;
 for (int i = 0; i < n; ++i) {
  for (int j = 1; j < n - i; j++) {
   if (x[j - 1] > x[j]) { 
    temp = x[j - 1];
    x[j - 1] = x[j];
    x[j]= temp;
   }
  }
 }
}

 

以上で終わります。