-
Notifications
You must be signed in to change notification settings - Fork 255
/
quick_sort.go
41 lines (33 loc) · 720 Bytes
/
quick_sort.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
package main
import "fmt"
func QuickSort(slice []int) {
quick(slice, 0, len(slice)-1)
}
func quick(slice []int, start int, end int) {
if start < end {
pivotIndex := split(slice, start, end)
quick(slice, start, pivotIndex-1)
quick(slice, pivotIndex+1, end)
}
}
func split(slice []int, start int, end int) int {
pivot := slice[end]
j := start
for index := start; index < end; index++ {
if slice[index] < pivot {
slice[index], slice[j] = slice[j], slice[index]
j++
}
}
if pivot <= slice[j] {
slice[end] = slice[j]
slice[j] = pivot
}
return j
}
func main() {
slice := []int{2, 1, 8, 4, 3, 7, 6, 5, 9}
fmt.Println("Slice:", slice)
QuickSort(slice)
fmt.Println("QuickSort:", slice)
}