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になったら最後に挿入ソートを適用して終了する。