shellSort

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

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE shellSort(Var array[])
	DIM i, j, inc, temp
	
	inc = 4
	WHILE INT(inc) > 0
		FOR i = 0 TO UBound(array)
			j = i
			temp = array[i]
			WHILE j >= inc AND array[zcut(j-inc)] > temp
				array[j] = array[j-inc]
				j = j - inc
			WEND
			array[j] = temp
		NEXT
		IFB inc / 2 <> 0 THEN
			inc = inc / 2
		ELSEIF inc = 1 THEN
			inc = 0
		ELSE
			inc = 1
		ENDIF
	WEND
FEND

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

シェルソート

間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返します。

隣同士の要素を入れ替えるよりも高速に並び替えることができます。

アルゴリズム

  1. 適当な間隔hを決める。
  2. 間隔hをあけて取り出したデータ列に挿入ソートを適用する。
  3. 間隔hを狭めて手順2を繰り返す。
  4. h=1になったら最後に挿入ソートを適用して終了する。