ActionScript入門Wiki - 選択ソート

トップページ > アルゴリズム > 選択ソート

概要

選択ソートを書いてみましょう。
この記事は、バブルソートを読んでいるという前提条件で話を進めていきます。

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

選択ソート

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

選択ソートは配列の中にある最小値を探しだして、未確定の先頭要素と交換します。
最小値を探すには未確定の値が入ってるところを全て探索しなければなりません。

1周目

最小値には何も入っていないので4を入れておきます。
現在の最小値 : 4

現在の最小値(4)と1を比べると1の方が小さいので、最小値が1になります。
現在の最小値 : 1

現在の最小値(1)と3を比べると1の方が小さいので、最小値はそのままです。
現在の最小値 : 1

現在の最小値(1)と2を比べると1の方が小さいので、最小値はそのままです。
現在の最小値 : 1

1周回った時点で最小値が1になったので先頭要素と交換します。
この時点で1の位置が確定しました。確定した値には黄色を付けておきます。

2週目

最小値には何も入っていないので4を入れておきます。
現在の最小値 : 4

現在の最小値(4)と3を比べると3の方が小さいので、最小値が3になります。
現在の最小値 : 3

現在の最小値(3)と2を比べると2の方が小さいので、最小値が2になります。
現在の最小値 : 2

1周回った時点で最小値が2になったので未確定の先頭要素と交換します。
1, 2, 3, 4とこの時点で整列が完了していますが、前回でも説明したとおりコンピュータには整列したかどうかは分からないのでまだ処理が続きます。

3周目

最小値には何も入っていないので3を入れておきます。
現在の最小値 : 3

現在の最小値(3)と4を比べると3の方が小さいので、最小値はそのままです。
現在の最小値 : 3

1周回った時点で最小値が3になったので未確定の先頭要素と交換します。
未確定の先頭要素は最小値と同じ値なので交換しても位置は変わりません。

この時点で未確定の値が4だけになったので、4も自動で確定されます。

このように選択ソートでは未確定の要素群から最小値を探し出し、先頭の要素と交換する処理を繰り返します。

では、このアルゴリズムをコードで書いてみましょう。

プログラム

private function selectionSort(data:Array):void
{
	for (var i:int = 0; i < data.length - 1; i++)
	{
		var min:int = i; // 最小値が入っている添え字
		for (var j:int = i + 1; j < data.length; j++)
		{
			if (data[min] > data[j]) min = j;
		}
 
		var temp:int = data[i];
		data[i] = data[min];
		data[min] = temp;
	}
}

全体のコードはこのようになります。

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

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

選択ソートは英語でSelection Sortなので、そのままメソッド名に採用します。
引数はソート対象の配列を受け取ります。

private function selectionSort(data:Array):void
{
	for (var i:int = 0; i < data.length - 1; i++)
	{
	}
}

選択ソートでは最小値と未確定の先頭要素を交換するのですが、その先頭要素の添え字位置を保持しているのがこのループ変数iです。
1周目は0で、2周目は1で...という風に常に未確定の先頭要素の位置を指しています。

i < data.lengthではなく、i < data.length - 1という書き方に注目してみましょう。
上でも書きましたが、未確定の要素が一つだけになると最小値は自分自身になるので自動で位置が確定してしまいます。
なのでi < data.lengthのように最後までループする必要が無いということです。

private function selectionSort(data:Array):void
{
	for (var i:int = 0; i < data.length - 1; i++)
	{
		var min:int = i; // 最小値が入っている添え字
		for (var j:int = i + 1; j < data.length; j++)
		{
			if (data[min] > data[j]) min = j;
		}
 
		var temp:int = data[i];
		data[i] = data[min];
		data[min] = temp;
	}
}

var min:intが最小値の場所を指す変数になります。
注意して欲しいのは、最小値をそのまま入れるのではなく、最小値が入っている配列の添え字を入れます。
配列の2番目とか4番目のような、「番目」を入れるわけですね。

内ループでは最小値と未確定の要素を比べているわけですが、ループを回る前に最小値を初期化しておかなければなりません。
最小値に何も入っていないと比べることが出来ないので、ループ前に先頭要素の添え字をminに入れておきます。
つまり先頭要素の値を仮定の最小値にしておくわけです。

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

最小値minには未確定の先頭要素iの添え字が入っているので、内ループの添え字はi + 1になります。
j = iだと同じ値を比べることになるので1回比較する時間が無駄になります。

minとjの添え字先の値を比べてjの方が小さかったら、最小値にjを入れます。このjが仮定の最小値になるわけですね。

var temp:int = data[i];
data[i] = data[min];
data[min] = temp;

ループを抜け終わった時点でminの添え字先の値が最小になっている事が確定します。
後は先頭要素と交換するだけなので、交換処理のコードを書きましょう。
交換処理については、値の交換処理を参照してください。

これで選択ソートのコードが完成しました。

var data:Array = [4, 3, 2, 1, 7, 3, 11, 77, 4];
selectionSort(data);
trace(data); // 1,2,3,3,4,4,7,11,77

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

検証用コード

package
{
	import flash.display.Sprite;
 
	public class Main extends Sprite
	{
		public function Main()
		{
			var data:Array = [4, 3, 2, 1, 7, 3, 11, 77, 4];
			selectionSort(data);
			trace(data);
		}
 
		private function selectionSort(data:Array):void
		{
			for (var i:int = 0; i < data.length - 1; i++)
			{
				var min:int = i; // 最小値が入っている添え字
				for (var j:int = i + 1; j < data.length; j++)
				{
					if (data[min] > data[j]) min = j;
				}
 
				var temp:int = data[i];
				data[i] = data[min];
				data[min] = temp;
			}
		}
	}
}

リンク元(0)