comb_sort.go

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

package main

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

type BinaryHeap struct {
    nr_elem int
    data []int
}

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
}

func main() {
    rand.Seed(0)

    t0 := time.Now()

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

        fmt.Println(data)

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

    elapsed := time.Since(t0)
    fmt.Printf("exec_time: %.4f sec\n", elapsed.Seconds())
}