バブルソート

バブルソートとは

ソート(並べ替え)のアルゴリズムにはいくつかの種類がありますが、ここでは最も単純なバブルソートを紹介します。

以下のような配列a[]を昇順に並べ替えたいと思います。

配列の終端までa[j]とa[j + 1]を比較し、添え字が小さいほうの値が大きければ値を入れ替えます。
まず最初にa[0]とa[1]を比較し、a[0] = 5、a[1] = 3よりa[0] > a[1]なので値を入れ替えます。

次にa[1]とa[2]を比較し、a[1] = 5、a[2] = 9よりa[1] < a[2]なので値を入れ替えません。

次にa[2]とa[3]を比較し、a[2] = 9、a[3] = 1よりa[2] > a[3]なので値を入れ替えます。

これを最後までやると最も大きい数が配列の一番最後に来ます。

この作業を要素数だけ繰り返すと、次は2番目に大きい数が最後から2番目に、3番目に大きい数が最後から3番目に…と続いて、並べ替えることができます。

ソースコード

これをプログラムで表現するとこのようになります。

	int a[5] = { 5, 3, 9, 1, 8 };
	int i, j, buf;

	for (i = 0; i < 5; i++)
	{
		for (j = 0; j < 4; j++)
		{
			if (a[j] > a[j + 1])
			{
				buf = a[j];
				a[j] = a[j + 1];
				a[j + 1] = buf;
			}
		}
	}