shearSortシェアソート関数

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

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

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

プログラム

UWSC
//////////////////////////////////////////////////
// 【引数】
//   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を繰り返す回数 
// 【戻り値】
//   
//////////////////////////////////////////////////
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

使い方

UWSC
DIM array[] = 8, 20, 2, 22, 17, 30, 14, 4, 25, 5

shearSort(array)

FOR item IN array
	PRINT item
NEXT

シェアソート

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

アルゴリズム

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

関連記事

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