本ページには広告が含まれています。
引数に指定された配列をシェルソートで並び替えます。
- 構文
- shellSort( 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
//////////////////////////////////////////////////
// 【引数】
// inputs : 繰り返す文字列
// multiplier : inputsを繰り返す回数
// 【戻り値】
//
//////////////////////////////////////////////////
FUNCTION strRepeat(inputs, multiplier)
DIM res = ""
FOR n = 1 TO multiplier
res = res + inputs
NEXT
RESULT = res
FEND
//////////////////////////////////////////////////
// 【引数】
// arrayname : 上限値を求める配列の名前
// dimension : 返す次元を示す整数
// 【戻り値】
//
//////////////////////////////////////////////////
FUNCTION UBound(arrayname[], dimension = 1)
RESULT = EVAL("RESIZE(arrayname" + strRepeat("[0]", dimension - 1) + ")")
FEND使い方
DIM array[] = 8, 20, 2, 22, 17, 30, 14, 4, 25, 5
shellSort(array)
FOR item IN array
PRINT item
NEXT- 結果
2 4 5 8 14 17 20 22 25 30
シェルソート
シェルソート（Shell Sort）は、挿入ソートを高速化したソートアルゴリズムの一つで、挿入ソートのアルゴリズムを改良したものです。挿入ソートが隣接する要素を比較するのに対して、シェルソートは間隔を設定して、間隔だけ離れた要素を比較します。
| 最悪計算時間 | 間隔に依存 |
|---|---|
| 最良計算時間 | \(O(n \log n)\) |
| 平均計算時間 | 間隔に依存 |
アルゴリズム
- ソート対象の配列を、間隔を設定して分割します。最初は間隔を半分にし、以降、間隔を縮小しながら分割を繰り返します。
- 分割された部分配列に対して、挿入ソートを実行します。つまり、隣接する要素を比較して、正しい順序に並び替えます。
- 1〜2を、最後に間隔が1になるまで繰り返します。
関連記事
- QSORT関数 (スクリプト関数)
- QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
- small関数 (自作関数)
- 配列の中で小さい方から数えた順位の値を求めます。
- bubbleSort関数 (自作関数)
- 引数に指定された配列を バブルソート で並び替えます。
- shakerSort関数 (自作関数)
- シェーカーソートは、ソートのアルゴリズムの一つです。バブルソートを改良したもの。双方向バブルソート、改良交換法とも言われます。バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行います。
- gnomeSort関数 (自作関数)
- ノームソートはソートアルゴリズムの一つです。挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行います。
- insertionSort関数 (自作関数)
- 挿入ソートは、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入します。
- heapSort関数 (自作関数)
- 引数に指定された配列をヒープソートで並び替えます。
- quickSort関数 (自作関数)
- 問題を小さな部分問題に分割していく分割統治法を利用した手法で、データから適当に基準値を決めこれより大きいグループと小さいグループに分けるという手順を、分けた小さなグループに対しても再帰的に繰り返していきます。
- shearSort関数 (自作関数)
- シェアソートはソートアルゴリズムの一つで、データを長方形に並べた上で各行・各列ごとにソートを行ないます。
- Sort.Header プロパティ (Excel)