LoginSignup
0

More than 3 years have passed since last update.

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

Posted at

カウントソート

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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
0