quicksort.go
919 Bytes
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
43
44
45
46
47
48
49
package webutility
type QSortDirection int
const (
QSortAscending = 0
QSortDescending = 1
)
// QuickSortable is an interface for quicksorting slices.
type QuickSortable interface {
Swap(i, j int)
Compare(i, j int) int
Len() int
}
// Quicksort quicksorts que.
func Quicksort(que QuickSortable, low, high int, dir QSortDirection) {
if low >= high {
return
}
if dir != QSortAscending && dir != QSortDescending {
return
}
index := partition(que, low, high, dir)
Quicksort(que, low, index-1, dir)
Quicksort(que, index+1, high, dir)
}
func partition(que QuickSortable, low, high int, dir QSortDirection) int {
i := low - 1
for j := low; j <= high-1; j++ {
if dir == QSortAscending {
if que.Compare(j, high) == -1 {
i++
que.Swap(i, j)
}
} else if dir == QSortDescending {
if que.Compare(j, high) == 1 {
i++
que.Swap(i, j)
}
}
}
que.Swap(i+1, high)
return i + 1
}