shellSortシェルソート関数

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

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

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

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   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

使い方

UWSC
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. 分割された部分配列に対して、挿入ソートを実行します。つまり、隣接する要素を比較して、正しい順序に並び替えます。
  3. 1〜2を、最後に間隔が1になるまで繰り返します。

関連記事

QSORT関数 (スクリプト関数)
QSORT関数は、配列の中身をソートする関数です。戻値はありません。昇順・降順・UNICODE文字比較 昇順・UNICODE文字比較 降順・自然順ソート 昇順・自然順ソート 降順のいずれかを指定することができます。
small関数 (自作関数)
配列の中で小さい方から数えた順位の値を求めます。
bubbleSort関数 (自作関数)
引数に指定された配列を バブルソート で並び替えます。
shakerSort関数 (自作関数)
引数に指定された配列を シェーカーソート で並び替えます。
gnomeSort関数 (自作関数)
引数に指定された配列を ノームソート で並び替えます。
insertionSort関数 (自作関数)
引数に指定された配列を 挿入ソート で並び替えます。
heapSort関数 (自作関数)
引数に指定された配列を ヒープソート で並び替えます。
quickSort関数 (自作関数)
引数に指定された配列を クイックソート で並び替えます。
shearSort関数 (自作関数)
引数に指定された配列を シェアソート で並び替えます。
Sort.Header プロパティ (Excel)
最初の行にヘッダー情報が含まれるかどうかを指定します。