UWSCのソートに＋αする

こんぴーた UWSC

UWSC公式掲示板で、キーと値の組み合わせをキーでソートしたいがどうしたら良いか、という質問があった。
これにstuncloudさんが良い回答をしていたのだけど、、、ちょっとだけ気になることがあるので記事にしてみた。


気になるのは、安定ソートでない点。



UWSCのソートについて

UWSCの配列ソートには、QSORTとHASHTBLを使ったHASH_SORTがある。
QSORTは、（おそらく内部実装がクイックソートで）安定ソートでない。
（キーが重複した場合、値の順番がオリジナルの順番ではなくなる）
HASHTBLを使うと、そもそもキーの重複ができない。


キーの重複を許容して、

  • 安定ソート
  • キーが重複したら、値でソート

を考えてみた。

スクリプト

ま、とりあえず以下のスクリプトを書いてみた。

OPTION EXPLICIT

DIM key[] =   40,   50,   50,   20,   20,   30,  20,   10
DIM val[] = "aa", "dd", "bb", "cc", "bb", "cc", "dd", "bb"

DIM key2 = SPLIT(JOIN(key)), val2 = SPLIT(JOIN(val))

PrintArray("original", key2, val2)
QSort(key2, 0, val2)
PrintArray("QSort", key2, val2)

key2 = SPLIT(JOIN(key))
val2 = SPLIT(JOIN(val))
QSortVal(key2, val2)
PrintArray("QSortVal", key2, val2)

key2 = SPLIT(JOIN(key))
val2 = SPLIT(JOIN(val))
StableSort(key2, val2)
PrintArray("StableSort", key2, val2)


PROCEDURE PrintArray(msg, keyArr[], valArr[])
	PRINT msg
	PRINT " key: " + JOIN(keyArr)
	PRINT " val: " + JOIN(valArr)
FEND

PROCEDURE StableSort(var keyArr[], var valArr[], order=0)
	DIM i, idx = -1, sub, j, m = LENGTH(keyArr) - 1, oarr = SAFEARRAY(0, m), suo, b
	FOR i = 0 TO m
		oarr[i] = i
	NEXT
	QSORT(keyArr, order, valArr, oarr)
	FOR i = 1 TO m
		b = (keyArr[i] = keyArr[i-1])
		IF b AND idx < 0 THEN idx = i - 1
		IFB idx >= 0 AND (!b OR i = m) THEN
			IF b THEN i = i + 1
			sub = SLICE(valArr, idx, i - 1)
			suo = SLICE(oarr, idx, i - 1)
			QSORT(suo, 0, sub)
			FOR j = idx TO i - 1
				valArr[j] = sub[j - idx]
			NEXT
			idx = -1
		ENDIF
	NEXT
FEND

PROCEDURE QSortVal(var keyArr[], var valArr[], order=0)
	DIM i, idx = -1, sub, j, m = LENGTH(keyArr) - 1, b
	QSORT(keyArr, order, valArr)
	FOR i = 1 TO m
		b = (keyArr[i] = keyArr[i-1])
		IF b AND idx < 0 THEN idx = i - 1
		IFB idx >= 0 AND (!b OR i = m) THEN
			IF b THEN i = i + 1
			sub = SLICE(valArr, idx, i - 1)
			QSORT(sub, order)
			FOR j = idx TO i - 1
				valArr[j] = sub[j - idx]
			NEXT
			idx = -1
		ENDIF
	NEXT
FEND


結果は

original
 key: 40 50 50 20 20 30 20 10
 val: aa dd bb cc bb cc dd bb
QSort
 key: 10 20 20 20 30 40 50 50
 val: bb bb dd cc cc aa dd bb
QSortVal
 key: 10 20 20 20 30 40 50 50
 val: bb bb cc dd cc aa bb dd
StableSort
 key: 10 20 20 20 30 40 50 50
 val: bb cc bb dd cc aa dd bb


UWSC標準のQSORTでは、20のものが、bb,dd,ccとなっている。
これはオリジナル順のcc,bb,ddでも、値ソート順のbb,cc,ddでもない。
QSortVal関数では、値でソートしている。
StableSort関数では、オリジナルと同じで安定ソートとなっている。

解説

StableSort関数では、元の順番を持つ配列を内部で生成している。
メモリーを潤沢に使うことになるけど、UWSCで扱う程度なので問題ないと判断。
キーが同じ範囲の、値の配列と元の順番の配列から部分配列を取り出して、再度ソートし格納し直している。


QSortVal関数では、値の部分配列を再度ソートしているだけ。


どちらも一旦ソート後、全体を見て、SLICEで部分配列を取り出し再度ソートすることで実現している。
どちらの関数も第三引数は、QSORTの順列です。
QSortValで、キーは昇順・値は降順とかしたい場合は、改造してくださいね。


もっと大変になるような気がしていたけど、意外とシンプルに書けて満足です。


なお、.net4.0以前のArray.Sortはクイックソート。4.5以降はイントロソートだそうです。
みんな、安定ソートには興味がないのね。
ワーストケースが怖いなら、イントロソートが良いかもね。