ActionScript入門Wiki - 挿入ソート

トップページ > アルゴリズム > 挿入ソート

概要

挿入ソートを書いてみましょう。

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

挿入ソート

この挿入ソートはトランプの並び替え方法に似ています。

このような順番でトランプが並んでいるとしましょう。
これを値の小さい順に並び替えます。

右側の5だけがずれていますよね。

なので、5をどかし、

8と9を右にずらして、

間に5を入れて完成です。
こんな感じでトランプを整理するでしょう。
この方法をソートアルゴリズムにしたのが挿入ソートです。

アルゴリズム

1週目

挿入ソートでは配列[1]、つまり左から見て2番目の値から走査を開始します。

分かりやすいように、対象の値に赤色を付けておきます。

この対象の値4の左側を見てみましょう。
左側を順番に見ていき、「4より小さい値を見つけた」もしくは「配列の左端まで来てしまった」場合にストップします。
左側には8しか無いので、ストップする場所は[0]になりますね。

ストップした所から対象の位置までの値を全て右にずらします。
この場合8だけ右ずれますね。

そのストップした場所に対象の値4を入れて1周目は終了です。まだこの4は位置が確定していません。

2週目

次は配列[2]、左から見て3番目の値から走査を開始します。

対象の値は3ですね。
この3の位置から左側を順番に見ていって、自分より小さい値を探し出しましょう。
8も4も自分より大きい値なので、配列の左端まで来てしまいました。なのでストップする位置は[0]ですね。

[0]～対象位置までの値を全て右にずらします。この場合4と8を右にずらします。

ストップした位置に対象の値3を入れて2週目終了です。

3周目

次は配列[3]、左から見て4番目の値から走査を開始します。

対象の値は7ですね。
この7の位置から左側を順番に見ていって、自分より小さい値を探し出しましょう。
配列[1]の4が7より小さいですね。

ただ、この4が入っている位置で止まるわけにはいきません。
この一個右側にある8が入っている位置で止まるようにします。こうしないと4も右側にずれてしまうからです。

ストップした位置～対象位置までの値を全て右にずらします。この場合ずれるのは8のみです。

ストップした位置に対象の値7を入れて3週目終了です。

4周目

もう説明は要らないと思いますが、一応手順に従ってずらしてみましょう。

対象の値は6ですね。
この6の位置から左側を順番に見ていって、自分より小さい値を探し出しましょう。
配列[1]の4が6より小さいですね。

[1]にある4が自分より小さい値なので、その右側にある[2]がストップ位置になります。

ストップした位置～対象位置までの値を全て右にずらします。この場合ずれるのは7と8です。

ストップした位置に対象の値6を入れて4週目終了です。

これでループが回り終わったのでソート完了です。
では、このアルゴリズムをコードで書いてみましょう。

プログラム

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

挿入ソートのコードはこのようになります。

一つ一つ説明していきましょう。

private function insertionSort(data:Array):void
{
}

挿入ソートは英語でInsertion Sortというので、そのままメソッド名に採用します。
引数はソート対象の配列を受け取ります。

for (var i:int = 1; i < data.length; i++)
{
}

配列の1番目から走査するので外側ループの変数iには1を入れておきます。

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

data[i]には対象の値が入っています。
このあと右にずらすときに、対象の値が上書きされてしまうので、temp変数に値を退避させておきます。

for文の部分をみてみましょう。
これはストップ位置を決めるのと、値をずらす処理を同時に行っています。

for (var j:int = i - 1; j >= 0 && temp < data[j]; j--)

ループ変数jがストップ位置を探すための添え字です。
i - 1を入れて対象位置の一つ左から探索し始めます。

j >= 0
配列外まで走査しないようにj >= 0を入れています

temp < data[j]
tempには対象の値が入っていますね。
つまり、対象の値より現在走査中の値の方が大きければループが回り続けます。

data[j + 1] = data[j];

これが内ループの処理です。
jの中身をj + 1に入れているので、右側にずらしていることになりますね。

data[j + 1] = temp;

ループを抜けた時点で、ループ変数jは対象位置より小さい値、もしくは配列の-1番目を指しているはずです。
なので、対象の値を入れる位置はj + 1になるので、data[j + 1] = tempと記述します。

これで挿入ソートの完成です。

var data:Array = [5, 2, 3, 4, 1];
insertionSort(data);
trace(data); // 1,2,3,4,5

使い方はこのような感じですね。

検証用コード

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

リンク元(0)