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番目以降の要素についても比較・挿入を繰り返します。