~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
}