shakerSort関数

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

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

構文: shakerSort( array )

引数

array 必須: ソートする数値を格納した配列。参照引数。

戻り値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。
// 【戻り値】
//////////////////////////////////////////////////
PROCEDURE shakerSort(Var array[])
	DIM topIndex = 0
	DIM bottomIndex = UBound(array) - 1
	WHILE TRUE
		DIM lastSwapIndex = topIndex
		FOR n = topIndex TO bottomIndex
			IFB array[n] > array[n+1] THEN
				swap(array[n], array[n+1])
				lastSwapIndex = n
			ENDIF
		NEXT
		bottomIndex = lastSwapIndex
		IF topIndex = bottomIndex THEN BREAK
		FOR n = bottomIndex TO topIndex + 1 STEP -1
			IFB array[n] < array[n-1] THEN
				swap(array[n], array[n-1])
				lastSwapIndex = n
			ENDIF
		NEXT
		topIndex = lastSwapIndex
		IF topIndex = bottomIndex THEN BREAK
	WEND
FEND

//////////////////////////////////////////////////
// 【引数】
//   inputs : 繰り返す文字列
//   multiplier : inputsを繰り返す回数
// 【戻り値】
//   inputsをmultiplier回を繰り返した文字列を返します
//////////////////////////////////////////////////
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

解説

2-3行目

4,22行目

無限ループ。

5行目

lastSwapIndexにtopIndexを代入。

6,11行目

topIndexがbottomIndexになるまで繰り返す。

7-10行目

配列のn番目がn+1番目より大きかったら、その2つを入れ替える。lastIndexにnを代入する。

12行目

bottomIndexにlastSwapIndexを代入。

13行目

topIndexとbottomIndexが等しかったらループを抜ける。

14,19行目

bottomIndexからtopIndex+1まで繰り返す。

15-18行目

配列のn番目がn-1番目より小さかったら、その2つを入れ替える。lastIndexにnを代入する。

20行目

bottomIndexにlastSwapIndexを代入。

21行目

topIndexとbottomIndexが等しかったらループを抜ける。

使い方

結果

シェーカーソート

シェーカーソートは、ソートのアルゴリズムの一つです。バブルソートを改良したもの。双方向バブルソート、改良交換法とも言われます。

バブルソートでは、配列の要素を1つずつ比較していくため、逆に整列された配列の場合には非常に遅いという問題があります。シェーカーソートは、配列を前から順番に比較するだけでなく、後ろからも比較することで、配列の整列をより効率的に行います。

アルゴリズム

バブルソートで1回スキャンを行うと最後の要素1個がスキャン範囲中最大であることがわかり、次回のスキャン範囲を1狭めることができます。さらに、このスキャンの最後で連続してm個の要素の交換が行われていなければそのm個についてはソート済みであることが分かるので、次回のスキャン範囲をm狭めることができます。この工夫で、後半が殆ど整列済みのデータに対してバブルソートが高速に行えるようになります。

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

最初に、カレントポインタを配列の先頭、終端ポインタを配列の末尾に設定します。
カレントポインタが終端ポインタに到達するまで、以下の処理を繰り返します。
1. カレントポインタとその次の要素を比較し、大小関係が逆ならば、交換します。
2. カレントポインタを1つ進めます。
3. 終端ポインタとその前の要素を比較し、大小関係が逆ならば、交換します。
4. 終端ポインタを1つ戻します。
カレントポインタが終端ポインタに到達したら、ソートが完了です。

QSORT関数 (スクリプト関数): 配列の中身をソートします。
bubbleSort関数 (自作関数): 引数に指定された配列をバブルソートで並び替えます。
gnomeSort関数 (自作関数): 引数に指定された配列をノームソートで並び替えます。
insertionSort関数 (自作関数): 引数に指定された配列を挿入ソートで並び替えます。
small関数 (自作関数): 配列の中で小さい方から数えた順位の値を求めます。
shellSort関数 (自作関数): 引数に指定された配列をシェルソートで並び替えます。
heapSort関数 (自作関数): 引数に指定された配列をヒープソートで並び替えます。
quickSort関数 (自作関数): 引数に指定された配列をクイックソートで並び替えます。
shearSort関数 (自作関数): 引数に指定された配列をシェアソートで並び替えます。
RESIZE関数 (スクリプト関数): 配列の上限値を取得または変更します。配列の上限値を変更する場合は第二引数に値を指定します。