バブルソート

ホームアルゴリズム入門講座 > バブルソート

バブルソート

バブルソートの基本データ

バブルソートのアルゴリズム

バブルソートは、「隣り合う要素を比較し、入れ替える」という考えを元にしたソートアルゴリズムです。典型的なアルゴリズムの中ではもっとも基本的で実装が簡単でです。計算量が多くなりますが、しばしば用いられます。

たとえば、3 2 1 というデータがあります。これをバブルソートによって並び替えてみます。

元のデータ: 3 2 1

(1回目の外側ループ)
2 3 1 (3と2を比較して交換した)
2 1 3 (3と1を比較して交換した)
(2回目の外側ループ)
1 2 3 (2と1を比較して交換した)
1 2 3 (1と2を比較したけど、交換しない)

ソートされたデータ: 1 2 3

隣り同士を交換していくループを「内ループ」とし、その「内ループ」を繰り返す外側のループを「外ループ」とすると、バブルソートはデータ数 n の2乗の計算が必要になります。(f(n) = n2) よって、バブルソートの計算量はO(n2)です。

バブルソートの実装

バブルソートを実装してみます。ソートの機能だけでなく、外ループごとに現在の並びを表示する機能や、繰り返しの回数をカウントする機能も入れています。

using System;

namespace NewWorld
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int[] data = {6,3,8,5,4,7,9,2,1};
			int m;
			int count = 0;
			for(int i = 0; i < (data.Length - 1); i++)
			{
				for(int y = 0; y < (data.Length - 1); y++)
				{
					if(data[y] > data[y+1])
					{
						m = data[y];
						data[y] = data[y+1];
						data[y+1] = m;
					}
					count++;
				}
				Console.Write("{0} roop: ",i+1);
				foreach(int num in data)
					Console.Write(num + " ");
				Console.WriteLine();
			}
			
			Console.WriteLine("{0} times",count);
		}
	}
}

繰り返す回数は、厳密には (n - 1)2 です。ループの中で data[y+1] を使っていますが、この部分は最後の要素に対しては「配列の要素外」の例外が投げられていまうからです。

データを入れ替える際には、配列とは違う一時保存データ m を用意し、それを介して交換します。

出力された外ループごとの結果を見ると、最低の数 1 が右から左へと移動していくのが分かります。これがバブルソートという名前の由来です。

なお、繰り返しの回数は (n - 1)2 ですが、実際に「交換する回数」はもっと減ります。それを知りたければ count++; をifの中に入れれば分かります。

改良の余地

バブルソートの外ループごとの結果を見れば、改良の余地があることに気づきます。それは「後半」はすべてそろっているということです。

バブルソートは後ろから順にそろえていきます。そのため、「後半」はもう「隣り同士の要素を比較」する必要がないのです。重要なのは「後半」をどのように定義するか、です。逆に言えば、比較するべき「前半」の定義です。

using System;

namespace NewWorld
{
	class MainClass
	{
		public static void Main(string[] args)
		{
			int[] data = {6,3,8,5,4,7,9,2,1};
			int m;
			int count = 0;
			for(int i = 0; i < (data.Length - 1); i++)
			{
				for(int y = 0; y < (data.Length - 1 - i); y++)
				{
					if(data[y] > data[y+1])
					{
						m = data[y];
						data[y] = data[y+1];
						data[y+1] = m;
					}
					count++;
				}
				Console.Write("{0} roop: ",i+1);
				foreach(int num in data)
					Console.Write(num + " ");
				Console.WriteLine();
			}
			
			Console.WriteLine("{0} times",count);
		}
	}
}

内ループを見てください。繰り返す回数が「data.Length - 1 - i」になっています。これが「前半」の定義です。これにより、「前半」だけ比較し、「後半」は無視することが可能になります。実際、繰り返す回数はおおよそ半減します。

この改良版バブルソートをさらに双方向で比較していくようにしたのが「シェーカーソート」です。また、バブルソートの発展版に「コムソート」というものもありますが、コムソートは極めて早い分、安定ソートではなくなってしまいます。