Skip to content

Instantly share code, notes, and snippets.

@swuecho
Created April 11, 2012 04:08
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save swuecho/2356792 to your computer and use it in GitHub Desktop.
Save swuecho/2356792 to your computer and use it in GitHub Desktop.
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)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment