/
quick.go
42 lines (34 loc) · 939 Bytes
/
quick.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
package quicksort
func quicksort(target []int) {
sortIt(target, 0, len(target)-1)
}
//recursively sort the sub-slices
func sortIt(target []int, left int, right int) {
// returns when there is nothing left to traverse
if left >= right {
return
}
//swap the elements and returns the dividing point between right and left side
partIndex := partition(target, left, right)
sortIt(target, left, partIndex-1)
sortIt(target, partIndex, right)
}
func partition(target []int, left int, right int) int {
//select the pivot point, could be randomly selected, in this case I take the middle element
pivot := target[(left+right)/2]
// loop over the slice untill it finds the elements to be swapped
for left <= right {
for target[left] < pivot {
left++
}
for target[right] > pivot {
right--
}
if left <= right {
target[left], target[right] = target[right], target[left]
left++
right--
}
}
return left
}