go で counting sort やってみる #Go

counting sort

ソートアルゴリズムの１つ
メモリに心配なければ早そう O(n+k)

x(n) の配列

制約

すべてのx[i]に対して

0 <= x[i] < k

が成り立つ前提

なので配列内でとりうる値の範囲がわかっていないと利用できない

kが大きくなればなるほど分布を保持する配列のメモリ割り当てが必要

例

n = 10
k = 5

において下記配列を並び替えてみる

x(10) = [3, 4, 2, 1, 0, 0, 4, 3, 4, 2] # len = 10

① すべてのx(n) の要素に対して出現回数を求める。結果をカウント配列countMapに格納する

package counting_sort

import "fmt"

func counting_sort(x []int, k int) {
    countMap := make([]int, k)
    // create map
    for _, val := range x {
        countMap[val]++
    }
    fmt.Printf("countMap: %#v\n", countMap)
}

test でデバッグ

package counting_sort

import (
    "reflect"
    "testing"
)

func Test_counting_sort(t *testing.T) {
    type args struct {
        x []int
        k int
    }
    tests := []struct {
        name string
        args args
        want []int
    }{
        {
            name: "ok_0",
            args: args{
                x: []int{3, 4, 2, 1, 0, 0, 4, 3, 4, 2},
                k: 5,
            },
            want: []int{0, 0, 1, 2, 2, 3, 3, 4, 4, 4},
        },
    }
    for _, tt := range tests {
        t.Run(tt.name, func(t *testing.T) {
            counting_sort(tt.args.x, tt.args.k)
            if !reflect.DeepEqual(tt.args.x, tt.want) {
                t.Errorf(`
                name: %v,
                act. %v
                exp. %v
            `, tt.name, tt.args.x, tt.want)
            }
        })
    }
}

=== RUN   Test_counting_sort
=== RUN   Test_counting_sort/ok_0
# countMap: []int{2, 1, 2, 2, 3}
--- FAIL: Test_counting_sort (0.00s)
    --- FAIL: Test_counting_sort/ok_0 (0.00s)
        /Users/kouhei/go/src/github.com/smith-30/algo/counting_sort/main_test.go:31: 
                            name: ok_0,
                            act. [3 4 2 1 0 0 4 3 4 2]
                            exp. [0 0 1 2 2 3 3 4 4 4]

FAIL
FAIL    github.com/smith-30/algo/counting_sort  0.018s
Error: Tests failed.

② countMapのvalueを、keyがxのインデックスの最大値を示すように更新する

言葉で説明しにくいのでコードを参照ください、、

package counting_sort

import "fmt"

func counting_sort(x []int, k int) {
    countMap := make([]int, k)
    // create map
    for _, val := range x {
        countMap[val]++
    }

    // change countMap's value.
    var prev int
    for k, val := range countMap {
        prev += val
        countMap[k] = prev
    }
    fmt.Printf("countMap: %#v\n", countMap)
}

このようになります

countMap: []int{2, 3, 5, 7, 10}

ステップ1でのkeyに対する出現個数から、keyに対するvalueがxにおけるインデックスの最大番号となるようにしている
例えば、最後の10はkeyが4なので、4の値がxの10番目にはあるというと。

③ countMapを使ってxの値を配列 resultに詰める(resultがsort後の配列)

package counting_sort

func counting_sort(x []int, k int) []int {
    result := make([]int, len(x))
    countMap := make([]int, k)

    // ① create map
    for _, val := range x {
        countMap[val]++
    }

    // ② change countMap's value.
    var prev int
    for k, val := range countMap {
        prev += val
        countMap[k] = prev
    }

    // ③ while decreasing a, put the value of x in result.
    for _, val := range x {
        countMap[val]--
        result[countMap[val]] = val
    }

    return result
}

countMapの値を減らすことで次にきたvalueをどのインデックスに詰めればよいかを実現しています。

処理の計算量的には
①でO(n)
②でO(k)
③でO(n)

なのでO(2n+k) ?
O(n+k) って書いてあったけどどうしてなんだろ、、?

go で counting sort やってみる

counting sort

例

参考