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

カウントソート

• 出現頻度を数えることでソート
• 整列対象の列に登場する値が$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
}