insertionSortインサーションソート

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

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

構文
insertionSort( array )
引数
array 必須
ソートする数値を格納した配列。参照引数。
戻り値

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   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を繰り返す回数 
// 【戻り値】
//   
//////////////////////////////////////////////////
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

使い方

UWSC
DIM array[] = 8, 20, 2, 22, 17, 30, 14, 4, 25, 5

insertionSort(array)

FOR item IN array
	PRINT item
NEXT
結果
プレーンテキスト
2
4
5
8
14
17
20
22
25
30

挿入ソート

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

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

アルゴリズム

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

関連記事

QSORT関数 (スクリプト関数)
配列の中身をソートします。
small (自作関数)
配列の中で小さい方から数えた順位の値を求めます。
bubbleSort (自作関数)
引数に指定された配列を バブルソート で並び替えます。
shakerSort (自作関数)
引数に指定された配列を シェーカーソート で並び替えます。
gnomeSort (自作関数)
引数に指定された配列を ノームソート で並び替えます。
shellSort (自作関数)
引数に指定された配列を シェルソート で並び替えます。
heapSort (自作関数)
引数に指定された配列を ヒープソート で並び替えます。
quickSort (自作関数)
引数に指定された配列を クイックソート で並び替えます。
shearSort (自作関数)
引数に指定された配列を シェアソート で並び替えます。
Sort.Header プロパティ (Excel)
最初の行にヘッダー情報が含まれるかどうかを指定します。