カウントソート・ビンソート

カウントソート

• 出現頻度を数えることでソート
• 整列対象の列に登場する値が$0$から$m-1$の整数に限定されている状況を想定すると，その列にそれぞれの値がどの程度登場するかを数えることでソートできる
• 登場頻度の累積を計算しておくことで，整列対象の配列中の値$x$に対して，その値$x$を累積度数配列におけるインデックスとして引くことで，その値$x$がソートされた配列においてどこにいるべきなのかがわかる

func CountSort(target []int, max int) []int {
	counter := make([]int, max)
	ret := make([]int, len(target))
	for _, ele := range target {
		counter[ele] += 1
	}
	for i := 0; i < max-1; i++ {
		counter[i+1] += counter[i]
	}
	for i := len(target)-1; 0 <= i; i-- {
		counter[target[i]]--
		ret[counter[target[i]]] = target[i]
	}
	return ret
}

ビンソート

• 「リスト」を使って列を表現した上で，出現頻度を数えることでソートする
• 「安定（＝同じキーを持つデータが二つ以上あるとき，整列前の順序の通りに整列される）」なソートになる

func BinSort(target []int, max int) []int {
	listhead := make([]int, max)
	for i := range listhead {
		listhead[i] = -1
	}
	next := make([]int, len(target))
	for i := range next {
		next[i] = -1
	}
	ret := make([]int, len(target))
	for i := len(target)-1; 0 <= i; i-- {
		j := target[i]
		next[i] = listhead[j]
		listhead[j] = i
	}
	i := 0
	for j := 0; j < max; j++ {
		p := listhead[j]
		for p != -1 {
			ret[i] = target[p]
			i++
			p = next[p]
		}
	}
	return ret
}