~telemachus/algorithms

ref: 597d3c5170b0fd3982a2aa1d12e39179f2293bbf algorithms/yourbasicpartition.go -rw-r--r-- 1.5 KiB
597d3c51Peter Aronoff Improve the README 1 year, 2 months ago
`                                                                                `
```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```
```package algorithms

import (
"math/rand"
)

func yourBasicPivot(xs []int) int {
n := len(xs)
return yourBasicMedian(xs[rand.Intn(n)],
xs[rand.Intn(n)],
xs[rand.Intn(n)])
}

func yourBasicMedian(a, b, c int) int {
if a < b {
switch {
case b < c:
return b
case a < c:
return c
default:
return a
}
}
switch {
case a < c:
return a
case b < c:
return c
default:
return b
}
}

// Partition reorders the elements of xs so that:
// - all elements in xs[:low] are less than pivotValue,
// - all elements in xs[low:high] are equal to pivotValue,
// - all elements in xs[high:] are greater than pivotValue.
func yourBasicPartition(xs []int, pivotValue int) (low, high int) {
low, high = 0, len(xs)
for mid := 0; mid < high; {
// Invariant:
//  - xs[:low] < pivotValue
//  - xs[low:mid] = pivotValue
//  - xs[mid:high] are unknown
//  - xs[high:] > pivotValue
//
//     < pivotValue  = pivotValue  unknown       > pivotValue
//     ----------------------------------------------------
// xs: |            |            |a            |           |
//     ----------------------------------------------------
//                  ^            ^             ^
//                  low          mid           high
switch x := xs[mid]; {
case x < pivotValue:
xs[mid] = xs[low]
xs[low] = x
low++
mid++
case x == pivotValue:
mid++
default: // x > pivotValue
xs[mid] = xs[high-1]
xs[high-1] = x
high--
}
}
return low, high
}
```