-
Notifications
You must be signed in to change notification settings - Fork 1
/
quicksort.go
116 lines (94 loc) · 2.08 KB
/
quicksort.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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
type pivotID int
const (
firstPivot pivotID = iota
lastPivot
medianOfThreePivot
)
func countComparisons(arr []int, id pivotID) int64 {
return quickSort(arr, 0, len(arr)-1, id)
}
func quickSort(arr []int, left int, right int, id pivotID) int64 {
if left >= right {
return 0
}
choosePivot(arr, left, right, id)
p := partition(arr, left, right)
count := int64(right - left)
count += quickSort(arr, left, p-1, id)
count += quickSort(arr, p+1, right, id)
return count
}
func choosePivot(arr []int, left int, right int, id pivotID) {
switch id {
case firstPivot:
case lastPivot:
arr[left], arr[right] = arr[right], arr[left]
case medianOfThreePivot:
pivotIndex := max(arr, min(arr, left, right), min(arr, max(arr, left, right), (left+right)/2))
arr[left], arr[pivotIndex] = arr[pivotIndex], arr[left]
}
}
func partition(arr []int, left int, right int) int {
pivot := arr[left]
i := left
for j := left + 1; j <= right; j++ {
if arr[j] < pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i], arr[left] = arr[left], arr[i]
return i
}
func max(arr []int, left int, right int) int {
if arr[left] > arr[right] {
return left
}
return right
}
func min(arr []int, left int, right int) int {
if arr[left] < arr[right] {
return left
}
return right
}
func main() {
stdin, err := os.Open(os.Getenv("INPUT_PATH"))
if err != nil {
stdin = os.Stdin
}
defer stdin.Close()
stdout, err := os.Create(os.Getenv("OUTPUT_PATH"))
if err != nil {
stdout = os.Stdout
}
defer stdout.Close()
reader := bufio.NewScanner(stdin)
writer := bufio.NewWriterSize(stdout, 1024*1024)
arr := make([]int, 0, 64)
for reader.Scan() {
value, err := strconv.Atoi(reader.Text())
checkError(err)
arr = append(arr, value)
}
pivots := []pivotID{firstPivot, lastPivot, medianOfThreePivot}
for _, pivot := range pivots {
array := make([]int, len(arr))
copy(array, arr)
result := countComparisons(array, pivot)
fmt.Fprintln(writer, result)
}
writer.Flush()
}
func checkError(err error) {
if err != nil {
panic(err)
}
}