quick_sort.go

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

package main

import (
    "fmt"
    "math/rand"
)

func quick_sort(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(data, low, i)
            quick_sort(data, i, up)
            break
        }
    }

    return
}

func main() {
    rand.Seed(0)

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

        fmt.Println(data)

        // sort by Quick Sort
        quick_sort(data, 0, len(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)
            }
        }
    }
}