ActionScript入門Wiki - バブルソート

トップページ > アルゴリズム > バブルソート

概要

ソートアルゴリズムの一種にバブルソートというソート方法があります。
このソートは、隣同士の要素の大小を比較しながら整列していくというアルゴリズムです。

flash on 2010-4-15 - wonderfl build flash online

解説

を昇順(値の小さい順)に並べたいと思います。

比較前:

比較後:

1番目の要素と2番目の要素の大小を比べます。
後ろにある1の方が小さいので交換します。

比較前:

比較後:

2番目の要素と3番目の要素の大小を比べます。
前にある3の方が小さいので交換はしません。

比較前:

比較後:

3番目の要素と4番目の要素の大小を比べます。
後ろにある2の方が小さいので交換します。

さてこれで一周しました。
ここで注目して欲しいのは、配列の中で一番大きい値が最後尾に来ているということです。
上の配列の場合、4が一番後ろに来ていますね。4の初期位置がどこにあろうと交換処理を一周すると確実に最後尾に配置されるようになっています。

これから2週目の比較に入るのですが、配列の最後尾にある値は比較の対象にはなりません。
上で説明したとおり、最後尾には必ず一番大きい値が入っているので比較するだけ無駄になるからです。

このように位置が確定している部分は黄色を付けることにします。

2週目の比較処理です。

比較前:

比較後:

1番目の要素と2番目の要素の大小を比べます。
前にある1の方が小さいので交換はしません。

比較前:

比較後:

2番目の要素と3番目の要素の大小を比べます。
後ろにある2の方が小さいので交換します。

2週目が終わった時点で昇順に整列されているのが分かりますね。
ただ、それは人間の目で見ると分かるだけであって、コンピュータには処理が終わったかどうかは分かりません。
なので、まだ処理が続きます。

3週目です。
比較前:

比較後:

1番目の要素と2番目の要素の大小を比べます。
前にある1の方が小さいので交換はしません。

さて、3週目が終わった時点で上のようになります。
1番目の値は、もう他の値と比較が出来ないので自動で確定されます。

このようになりますね。これで整列完了です。

アルゴリズムは大体理解できたしょうか。
上で解説した内容をコードで記述してみたいと思います。

private function bubbleSort(data:Array):void
{
	for (var i:int = data.length - 1; i >= 1; i--)
	{
		for (var j:int = 0; j < i; j++)
		{
			if (data[j] > data[j + 1])
			{
				var temp:int = data[j];
				data[j] = data[j + 1];
				data[j + 1] = temp;
			}
		}
	}
}

メソッド名はbubbleSortにしてソート対象の配列を引数として受け取ります。

for文が入れ子になっていて非常にややこしいですね。
まずは内ループの部分を見てみましょう。

for (var j:int = 0; j < i; j++)
{
	if (data[j] > data[j + 1])
	{
		var temp:int = data[j];
		data[j] = data[j + 1];
		data[j + 1] = temp;
	}
}

if (data[j] > data[j + 1])で比較していますね。
jの最初の値は0なのでdata[0] > data[1]、つまり0番目の要素と1番目の要素を比較しているわけです。
もし1番目の要素の方が小さいとtrueになり、if文の中で交換されるわけですね。
(交換コードの意味が分からない方は、値の交換処理を参照してください)

j++と記述されているのでjの値はどんどんと増えていくわけです。
つまり次のループでは1番目の要素と2番目の要素を比較、その次のループでは2番目の要素と3番目の要素を…という風にループされていくわけです。

しかし、いつまでも比較していると配列外の要素にアクセスしてしまうことになるのでループの終了条件を書かなければなりません。

for (var j:int = 0; j < data.length - 1; j++)

普通に考えるとこのようになります。jの値が配列の最後尾までくるとループを終了するというコードです。
これでも正しく動くのですが、少し無駄がありますね。

というのも、上の解説で説明したとおり1週目は配列の最後まで比較しますが、2週目以降は位置が確定した値が出てくるので比較回数が少なくなっているはずです。

1週目で3回比較して4の値が確定しました。
では、2週目になると4が確定しているので比較回数が2回になりますね。
更に3週目になると比較回数が1回になるように、周回を重ねるごとに比較回数が1回ずつ少なくなっています。

j < data.length - 1だと確定している値も比較条件になるので、無駄があるということです。

for (var i:int = data.length - 1; i >= 1; i--)
{
	for (var j:int = 0; j < i; j++)
	{
		if (data[j] > data[j + 1])
		{
			var temp:int = data[j];
			data[j] = data[j + 1];
			data[j + 1] = temp;
		}
	}
}

ではもう外側ループやj < iの意味が何となく分かってきたと思いませんか？
この外側ループの変数iはその周目で何回比較するかを表したものです。

j			i
3	1	4	2

1周目はこのようになります。
jの値が増えていってiと同じ所にくるとループを停止します。

j		i
1	3	2	4

2週目はこのようになります。
iの値を一つだけ減少させているのは、最後尾が確定しているので比較する必要が無いからです。
jの値が増えていってiと同じに所にくるとループを停止します。

j	i
1	2	3	4

3週目はこのようになります。
特に説明は要りませんね。

外側のループ条件をi >= 1としているので、ここでループが終了します。

上でも説明しましたが、1番目の値はもう他の値と比べることが出来ないので自動で確定されます。
なので、i >= 0ではなくi >= 1とした方が的確ですね。

これでバブルソートのコードが出来上がりました。

Rubyスクリプト

# coding: UTF-8
def bubbleSort(data)
  (data.length - 1).downto(1) do |i|
    (0...i).each do |j|
      if data[j] > data[j + 1]
        data[j], data[j + 1] = data[j + 1], data[j]
      end
    end
  end
 
  return data
end
 
p bubbleSort [3, 4, 1, 2]

検証用コード

package
{
	import flash.display.Sprite;
 
	public class Main extends Sprite
	{
		public function Main()
		{
			var data:Array = [3, 2, 1];
			bubbleSort(data);
			trace(data); // 1,2,3
		}
 
		private function bubbleSort(data:Array):void
		{
			for (var i:int = data.length - 1; i >= 1; i--)
			{
				for (var j:int = 0; j < i; j++)
				{
					if (data[j] > data[j + 1])
					{
						var temp:int = data[j];
						data[j] = data[j + 1];
						data[j + 1] = temp;
					}
				}
			}
		}
	}	
}

リンク元(0)