Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

カウントソート

  • 出現頻度を数えることでソート
  • 整列対象の列に登場する値が$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
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  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
ユーザーは見つかりませんでした