shearSort関数

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

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

構文: shearSort( array )

引数

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

戻り値

プログラム

//////////////////////////////////////////////////
// 【引数】
//   array : ソートする数値を格納した配列。参照引数。
// 【戻り値】
//////////////////////////////////////////////////
PROCEDURE shearSort(Var array[])
	DIM num = UBound(array)
	DIM rows = INT(SQRT(num))
	DIM cols = (num + 1) / rows
	FOR loop = 1 TO rows
		// 行をグループ
		FOR row = 1 TO rows
			IFB row MOD 2 <> 0 THEN
				// 奇数行目
				REPEAT
					DIM flg = FALSE
					FOR col = 1 TO cols - 1
						ofsRow = row - 1
						ofsCol = col - 1
						n = ofsRow * cols + ofsCol
						IFB array[n] > array[n+1] THEN
							swap(array[n], array[n+1])
							flg = TRUE
						ENDIF
					NEXT
				UNTIL !flg
			ELSE
				// 偶数行目
				REPEAT
					flg = FALSE
					FOR col = 1 TO cols - 1
						ofsRow = row - 1
						ofsCol = col - 1
						n = ofsRow * cols + ofsCol
						IFB array[n] < array[n+1] THEN
							swap(array[n], array[n+1])
							flg = TRUE
						ENDIF
					NEXT
				UNTIL !flg
			ENDIF
		NEXT
		PRINT
		// 列をグループ
		FOR col = 1 TO cols
			REPEAT
				flg = FALSE
				FOR row = 1 TO rows - 1
					ofsRow = row - 1
					ofsCol = col - 1
					n = ofsRow * cols + ofsCol
					IFB array[n] > array[n+cols] THEN	
						swap(array[n], array[n+cols])
						flg = TRUE
					ENDIF
				NEXT
			UNTIL !flg
		NEXT
	NEXT
	FOR row = 1 TO rows
		REPEAT
			flg = FALSE
			FOR col = 1 TO cols - 1
				ofsRow = row - 1
				ofsCol = col - 1
				n = ofsRow * cols + ofsCol
				IFB array[n] > array[n+1] THEN
					swap(array[n], array[n+1])
					flg = TRUE
				ENDIF
			NEXT
		UNTIL !flg
	NEXT
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

使い方

シェアソート

シェアソート（Shell Sort）は、挿入ソートを改良したアルゴリズムであり、配列を複数の部分配列に分割して、それぞれを挿入ソートで整列することで、全体として高速にソートすることができます。

アルゴリズム

ソート対象の配列を、一定の間隔で分割します。間隔は、一般的に、配列の要素数の半分程度から始め、繰り返し処理ごとに半分に縮小します。
分割された部分配列を、挿入ソートで整列します。
間隔を縮小して、再度分割します。1~2の処理を、間隔が1になるまで繰り返します。

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