radix_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 32-bit int
// using 8-bit bucket
func radix_sort(data []int) []int {
    buckets := make([]*list.List, 256)
    tmp_data := make([]int, len(data))

    for _, nr_shift := range ([]uint{0, 1, 2, 3}) {
        mask := 0xFF << (nr_shift * 8)

        for i, _ := range buckets {
            buckets[i] = list.New()
        }

        for _, x := range data {
            key := (x & mask) >> (nr_shift * 8)
            buckets[key].PushBack(x)
        }


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

        data = tmp_data
    }

    return data
}

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] = int(rand.Int31())
        }

        fmt.Println(data)

        // sort by Quick Sort
        data = radix_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)
            }
        }
    }
}