insertionSort関数

本ページには広告が含まれています。

引数に指定された配列を挿入ソートで並び替えます。

構文: insertionSort( 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

//////////////////////////////////////////////////
// 【引数】
//   inputs : 繰り返す文字列
//   multiplier : inputsを繰り返す回数
// 【戻り値】
//   inputsをmultiplier回を繰り返した文字列を返します
//////////////////////////////////////////////////
FUNCTION strRepeat(inputs, multiplier)
	DIM res = ""
	FOR n = 1 TO multiplier
		res = res + inputs
	NEXT
	RESULT = res
FEND

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

//////////////////////////////////////////////////
// 【引数】
//   arrayname : 上限値を求める配列の名前
//   dimension : 返す次元を示す整数
// 【戻り値】
//   配列の上限値
//////////////////////////////////////////////////
FUNCTION UBound(arrayname[], dimension = 1)
	RESULT = EVAL("RESIZE(arrayname" + strRepeat("[0]", dimension - 1) + ")")
FEND

使い方

結果

挿入ソート

挿入ソートは、配列を走査して、整列済みの部分列に適切な位置に要素を挿入していくことで配列をソートします。

最悪計算時間	\(O(n^{2})\)
最良計算時間	\(O(n)\)
平均計算時間	\(O(n^{2})\)

アルゴリズム

配列の2番目の要素から走査を開始します。
現在の要素を、それより前の整列済みの部分列の適切な位置に挿入します。
2の処理を、配列の最後の要素まで繰り返します。

QSORT関数 (スクリプト関数): 配列の中身をソートします。
bubbleSort関数 (自作関数): 引数に指定された配列をバブルソートで並び替えます。
shakerSort関数 (自作関数): 引数に指定された配列をシェーカーソートで並び替えます。
small関数 (自作関数): 配列の中で小さい方から数えた順位の値を求めます。
gnomeSort関数 (自作関数): 引数に指定された配列をノームソートで並び替えます。
shellSort関数 (自作関数): 引数に指定された配列をシェルソートで並び替えます。
heapSort関数 (自作関数): 引数に指定された配列をヒープソートで並び替えます。
quickSort関数 (自作関数): 引数に指定された配列をクイックソートで並び替えます。
shearSort関数 (自作関数): 引数に指定された配列をシェアソートで並び替えます。
RESIZE関数 (スクリプト関数): 配列の上限値を取得または変更します。配列の上限値を変更する場合は第二引数に値を指定します。