sorting_compare.go

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

package main

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

type SortFunc func([]int) []int

type SortAlgorithm struct {
    name string
    sortfunc SortFunc
    available bool
}

func main() {
    algorithms := []*SortAlgorithm{
        &SortAlgorithm{"bubble_sort", bubble_sort, true},
        &SortAlgorithm{"insert_sort", insert_sort, true},
        &SortAlgorithm{"comb_sort", comb_sort, true},
        &SortAlgorithm{"heap_sort", heap_sort, true},
        &SortAlgorithm{"quick_sort", quick_sort, true},
        &SortAlgorithm{"merge_sort", merge_sort, true},
        &SortAlgorithm{"radix_sort", radix_sort, true}}

    fmt.Print("# \t")
    for _, algo := range algorithms {
        fmt.Print(algo.name + "\t")
    }
    fmt.Println("")

    for n := 1024; n < 1024*1024*1024; n *= 2 {
        fmt.Printf("%d\t", n)

        for _, algo := range algorithms {
            if algo.available {
                rand.Seed(0)
                times := []float64{}
                for i := 0; i < 5; i++ {
                    var data = make([]int, n)
                    for i, _ := range data {
                        data[i] = int(rand.Int31())
                    }

                    t0 := time.Now()
                    data = algo.sortfunc(data)
                    dt := time.Since(t0)
                    times = append(times, dt.Seconds())
                }
                time_avg := 0.0
                for _, dt := range times {
                    time_avg += dt
                }
                time_avg /= float64(len(times))
                fmt.Printf("%f\t", time_avg)

                if time_avg > 5 {
                    algo.available = false
                }
            } else {
                fmt.Printf("n/a\t")
            }
        }
        fmt.Println("")
    }
}


// Quick sort

func quick_sort(data []int) []int {
    quick_sort_inner(data, 0, len(data))
    return data
}

func quick_sort_inner(data []int, low int, up int) {
    // sanity check
    if up - low < 0 {
        panic("quick_sort: Invalid argument")
    }

    if up - low <= 1 {
        return
    }

    if up - low == 2 {
        if data[low] > data[up - 1] {
            data[low], data[up - 1] = data[up - 1], data[low]
        }
        return
    }

    pivot := data[low + (up - low) / 2]

    i, j := low, up - 1
    for {
        // move i
        for data[i] < pivot && i < j {
            i++
        }

        // move j
        for data[j] > pivot && i < j {
            j--
        }

        if i < j {
            data[i], data[j] = data[j], data[i]
            i++
            continue
        } else {
            quick_sort_inner(data, low, i)
            quick_sort_inner(data, i, up)
            break
        }
    }

    return
}


// Merge sort

func merge_sort(data []int) []int {
    return merge_sort_inner(data, 0, len(data))
}

func merge_sort_inner(data []int, low int, up int) []int {
    // sanity check
    if up - low < 1 {
        panic("merge_sort_inner: Invalid argument")
    }

    if up - low == 1 {
        return data[low:up]
    }

    run1 := merge_sort_inner(data, low, low + (up - low) / 2)
    run2 := merge_sort_inner(data, low + (up - low) / 2, up)
    merged_run := make([]int, up - low)

    i, i1, i2 := 0, 0, 0
    for {
        if i2 == len(run2) || (i1 < len(run1) && run1[i1] < run2[i2]) {
            merged_run[i] = run1[i1]
            i++
            i1++
        } else {
            merged_run[i] = run2[i2]
            i++
            i2++
        }

        if i1 == len(run1) && i2 == len(run2) {
            break
        }
    }

    return merged_run
}


func bubble_sort(data []int) []int {
    // sort by Bubble Sort
    for i := 0; i < len(data) - 1; i++ {
        for j := 0; j < len(data) - 1; j++ {
            if data[j] > data[j + 1] {
                data[j], data[j + 1] = data[j + 1], data[j]
            }
        }
    }

    return data
}


func comb_sort(data []int) []int {
    for h := int(float32(len(data)) / 1.3); true;  {
        swapped := false

        for i := 0; i + h < len(data); i++ {
            if data[i] > data[i + h] {
                data[i], data[i + h] = data[i + h], data[i]
                swapped = true
            }
        }

        if ! swapped {
            if h == 1 {
                break
            } else {
                h = int(float32(h) / 1.3)
            }
        }
    }

    return data
}


// Heap sort

type BinaryHeap struct {
    nr_elem int
    data []int
}

func make_heap() *BinaryHeap {
    heap := new(BinaryHeap)
    heap.data = make([]int, 1024)
    heap.nr_elem = 0

    return heap
}

func Extend(slice []int, nr_extend int) []int {
    l := len(slice)
    if l + nr_extend > cap(slice) {  // reallocate
        // Allocate double what's needed, for future growth.
        newSlice := make([]int, (l+nr_extend)*2)
        // The copy function is predeclared and works for any slice type.
        copy(newSlice, slice)
        slice = newSlice
    }
    return slice
}

func (heap *BinaryHeap) push(x int) {
    if heap.nr_elem == len(heap.data) {
        heap.data = Extend(heap.data, len(heap.data))
    }

    heap.data[heap.nr_elem] = x
    heap.nr_elem ++
    heap.upheap(heap.nr_elem) // 1-origin idx
}

func (heap *BinaryHeap) pop() int {
    if heap.nr_elem == 0 {
        panic("no more element")
    }
    ret := heap.data[0]
    heap.data[0] = heap.data[heap.nr_elem - 1]
    heap.nr_elem --
    heap.downheap(1) // 1-origin idx

    return ret
}

// NOTICE: idx is 1-origin numbering
func (heap *BinaryHeap) upheap(idx int) {
    for idx > 1 {
        p_idx := idx / 2
        if heap.data[p_idx - 1] > heap.data[idx - 1] {
            heap.data[p_idx - 1], heap.data[idx - 1] = heap.data[idx - 1], heap.data[p_idx - 1]
            idx /= 2
        } else {
            break
        }
    }
    return
}

// NOTICE: idx is 1-origin numbering
func (heap *BinaryHeap) downheap(idx int) {
    for idx * 2 <= heap.nr_elem {
        lc_idx := idx * 2
        rc_idx := idx * 2 + 1
        c_idx := lc_idx

        if rc_idx <= heap.nr_elem && heap.data[rc_idx - 1] < heap.data[lc_idx - 1] {
            c_idx = rc_idx
        }

        if heap.data[c_idx - 1] < heap.data[idx - 1] {
            heap.data[c_idx - 1], heap.data[idx - 1] = heap.data[idx - 1], heap.data[c_idx - 1]
        }

        idx = c_idx
    }
    return
}

func heap_sort(data []int) []int {
    heap := make_heap()
    ret_data := make([]int, len(data))

    for _, x := range data {
        heap.push(x)
    }

    for i, _ := range ret_data {
        ret_data[i] = heap.pop()
    }

    return ret_data
}

func insert_sort(data []int) []int {
    // sort by Insert Sort
    for i := 0; i < len(data) - 1; i++ {
        for j := 0; j < len(data) - 1; j++ {
            if data[j] > data[j + 1] {
                data[j], data[j + 1] = data[j + 1], data[j]
            }
        }
    }

    return data
}

// 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
}