「逆写像ソート」の編集履歴（バックアップ）一覧はこちら

「逆写像ソート」(2010/01/25 (月) 19:16:11) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

整列アルゴリズムのひとつ。
分布数えソートと同じく実行時間は O(n) であり安定であるが、分布数えソートよりも若干遅いようである。整列に使用するキー値は一定の範囲の整数でなければならない。アルゴリズムは以下のとおり。 
x = a[i] ⇔ i = index[x] となる index[x] を作成する
もし x = a[i] となる i がなければ index[x] = -1とする
キー値が重複する場合、別配列 next[i] を用いてその並びを記述する（ex：a[i] = a[j] = a[k] ⇒ next[i] = j, next[j] = k, next[k] = -1）
index[x] <> -1のとき、a[index[x]] を書き出す

プログラミング掲示板「ソートロジック大会」なども参照のこと 
#asciiart(blockquote){
Const MAX = 100
Const MIN = 0
Sub mapsort(n As Integer, a As *Integer, b As *Integer, next As *Integer)
	Dim i As Integer, j As Integer, x As Integer
	Dim index[MAX - MIN + 1] As Integer
	' index[]の初期化
	For x = 0 To MAX - MIN
		index[x] = -1
	Next x
	' index[]の作成
	For i = n To 0 Step -1
		x = a[i] - MIN
		next[i] = index[x]
		index[x] = i
	Next i
	' データの書き出し
	j = 0
	For x = 0 To MAX - MIN
		i = index[x]
		While i >= 0
			b[j] = a[i]
			j = j + 1
			i = next[i]
		Wend
	Next x
End Sub
}