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("merge_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
    }

    p1, p2, p3 := data[low], data[low + (up - low) / 2], data[up - 1]
    if p1 > p2 {
        p2, p1 = p1, p2
    }
    if p2 > p3 {
        p3, p2 = p2, p3
    }
    if p1 > p2 {
        p2, p1 = p1, p2
    }
    pivot := p2

    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 {
            if data[i] > pivot {
                data[i], data[j] = data[j], data[i]
            }
            continue
        } else {
            if data[i] <= pivot {
                i ++
            }
            quick_sort(data, low, i)
            quick_sort(data, i, up)
            break
        }
    }

    return
}

func main() {
    rand.Seed(0)

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