insertionSort

タグ: ,
構文
insertionSort( Var array )
引数
array
ソートする数値を格納した配列。参照引数。
戻値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE insertionSort(Var array[])
	FOR i = 1 TO UBound(array)
		j = i
		WHILE j > 0 
			IF array[j-1] > array[j] THEN swap(array[j-1], array[j])
			j = j - 1
		WEND
	NEXT
FEND

//////////////////////////////////////////////////
// 【引数】
//   a : 変数bと交換する値。参照引数。 
//   b : 変数aと交換する値。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
	DIM tmp = a
	a = b
	b = tmp
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND

挿入ソート

挿入ソートは、ソートアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入します。

アルゴリズム

まず0番目と1番目の要素を比較し、順番が逆であれば入れ換える。次に2番目の要素が1番目までの要素より小さい場合、正しい順に並ぶように「挿入」します。これで2番目までの要素が整列済みとなります。整列済みなだけで間に要素が挿入される可能性はあります。このあと3番目以降の要素についても比較・挿入を繰り返します。