ActionScript入門Wiki - バブルソート(改良版)

トップページ > アルゴリズム > バブルソート(改良版)

概要

バブルソートでバブルソートのアルゴリズムと書き方を学びました。
今回は前回のコードを少し改良して、より効率よくソート処理を行うプログラムを書いてみましょう。

問題点

バブルソートでは、このように既に並び終わっている値を指定しても比較処理が続いてしまいます。
この部分を何とかすれば効率よくソートが出来るはずです。

解説

1番目の要素と2番目の要素を比較。

2番目の要素と3番目の要素を比較。

3番目の要素と4番目の要素を比較。

1周ループした時点でこのようになっています。
もしこの比較の中で一回も交換が行われていなかったら整列されていると見なします。
少なくとも一周は回ってしまいますが、前のコードよりは確実に効率が良くなるはずです。

これをコードで書いてみましょう。

private function bubbleSort(data:Array):void
{
	for (var i:int = data.length - 1; i >= 1; i--)
	{
		var check:Boolean = false;
 
		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;
 
				check = true;
			}
		}
 
		if (!check) return;
	}
}

前回のバブルソートのコードにcheckというBoolean変数を付け加えました。デフォルト値はfalseにしておきます。

もし、内ループの中で一回でも交換が行われているなら、まだ整列が完了していない可能性があります。
なので、交換処理のところでcheck = trueを入れておきましょう。これは少なくとも一回は交換したというフラグです。

ループを抜けるとif (!check) return;と記述しています。
!checkはcheck == falseと同じ意味です。
checkがfalse、つまり内ループで交換が一回も行われていなかったらソート完了という事なので、returnでバブルソートのメソッドを抜けます。

検証

実際どれぐらい速くなるのかを簡単に検証してみましょう。
[1, 2, 3, 4, 5, 6]の既に並び終わっている配列を前回のバブルソートに入れてみます。

1周目の比較回数は5回です。

2週目の比較回数は4回です。(累計: 9回)

3週目の比較回数は3回です。(累計: 12回)

4週目の比較回数は2回です。(累計: 14回)

5週目の比較回数は1回です。(累計: 15回)

という事で前回のバブルソートの比較回数は15回になりました。
次は、改良版バブルソートです。

最初の1周を回ると比較回数が5回になります。(1と2, 2と3, 3と4, 4と5, 5と6)
一回も交換されていないのでcheckがfalseのままです。なのでこのままreturnでループを抜けます。

改良版バブルソートの比較回数 : 5回
ということで15回が5回になったので大分速くなりましたね。

ただ、実際は既にソートされている配列を渡すケースは滅多に無いと思います。
この改良版バブルソートは既に整列されている、もしくはほぼ整列されているような配列を渡した場合に大きく効果が出ます。
改良前と比べて特にデメリットのようなものは見当たらないので基本的にはこっちを使ったほうが良いと思います。

Rubyスクリプト

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

検証用コード

package
{
	import flash.display.Sprite;
 
	public class Main extends Sprite
	{
		public function Main()
		{
			var data:Array = [4, 3, 6, 2, 1, 5];
			bubbleSort(data);
 
			trace(data);
		}
 
		private function bubbleSort(data:Array):void
		{			
			for (var i:int = data.length - 1; i >= 1; i--)
			{
				var check:Boolean = false;
 
				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;
 
						check = true;
					}
				}
 
				if (!check) return;
			}
		}
	}
}

リンク元(0)