UWSC辞典

シェアソート

構文

shearSort( Var 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

//////////////////////////////////////////////////
// 【引数】
//   a : 変数bと交換する値。参照引数。 
//   b : 変数aと交換する値。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
	DIM tmp = a
	a = b
	b = tmp
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND//////////////////////////////////////////////////
// 【引数】
//   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

//////////////////////////////////////////////////
// 【引数】
//   a : 変数bと交換する値。参照引数。 
//   b : 変数aと交換する値。参照引数。 
// 【戻値】
// 
//////////////////////////////////////////////////
PROCEDURE swap(Var a, Var b)
	DIM tmp = a
	a = b
	b = tmp
FEND

//////////////////////////////////////////////////
// 【引数】
//   配列 : 上限値を求める配列 
// 【戻値】
//   配列の上限値 
//////////////////////////////////////////////////
FUNCTION UBound(array[])
	RESULT = RESIZE(array)
FEND