0
Help us understand the problem. What are the problem?

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
}
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
0
Help us understand the problem. What are the problem?