swuecho
4/11/2012 - 4:08 AM

quicksort-fail when pivot !=0

quicksort-fail when pivot !=0

package main
import(
	"os"
        "io"
        "bufio"
        "fmt"
        "strconv"
)


var (
	data []int
	counter int=0
	filename string="testnum.txt"
)

func swap( arr []int,i int, j int){
	arr[i],arr[j]=arr[j],arr[i]
}
func quicksort(a []int) {
        if len(a)>1 {
		pivotIndex:=0
		pivotIndex=partition(a,pivotIndex)
		left:=a[:pivotIndex]
		counter=counter+len(left)-1
		right:=a[pivotIndex+1:]
		counter=counter+len(right)-1
		quicksort(left)
		quicksort(right)
	}
}

func partition(a []int, pivotIndex int) int {
	rightIndex:=len(a)-1
	pivotValue:=a[pivotIndex]
	i:=pivotIndex+1 // i is the lower index,j is the upper index
	for j:=pivotIndex+1;j<rightIndex;j++ {
		if a[j]<pivotValue {
			swap(a,i,j)
			i=i+1
		}
}
	swap(a,pivotIndex,i-1)
	return i-1
}
		

func inOrder(a []int) bool {
        if len(a) > 0 {
                prev := a[0]
                for i := 1; i < len(a); i++ {
                        if a[i] < prev {
                                return false
                        }
                        prev = a[i]
                }
        }

        return true
}



func main() {
	file,_:=os.Open(filename)
	defer file.Close()
	r:=bufio.NewReader(file)
	for{
		byte,_,err:=r.ReadLine()
		if err != nil {
			if err == io.EOF {
				break
            }
			return 
        }
		d,_:=strconv.ParseUint(string(byte),10,32)
		data=append(data,int(d))
	}
	quicksort(data)
	fmt.Println(data[:10],counter)
}