bucket_sort.go

//usr/bin/env go run $0 $@ ; exit

package main

import (
    "fmt"
    "math/rand"
    "container/list"
)

type BinaryHeap struct {
    nr_elem int
    data []int
}

// assume 8-bit int
func bucket_sort(data []int) []int {
    buckets := make([]*list.List, 256)
    for i, _ := range buckets {
        buckets[i] = list.New()
    }

    for _, x := range data {
        buckets[x].PushBack(x)
    }

    ret := make([]int, len(data))
    n := 0
    for i, _ := range buckets {
        bucket := buckets[i]
        for e := bucket.Front(); e != nil; e = e.Next() {
            ret[n] = e.Value.(int)
            n++
        }
    }

    return ret
}

func main() {
    rand.Seed(0)

    for n := 0; n < 100; n++ {
        // generate random number array
        var data = make([]int, 30)
        for i, _ := range data {
            data[i] = rand.Intn(256)
        }

        fmt.Println(data)

        // sort by Quick Sort
        data = bucket_sort(data)
        
        fmt.Println(data)
        
        // check whether the array is sorted.
        for i := 0; i < len(data) - 1; i++ {
            if data[i] > data[i + 1] {
                panic(i)
            }
        }
    }
}