~telemachus/algorithms

ref: 597d3c5170b0fd3982a2aa1d12e39179f2293bbf algorithms/hoarepartition.go -rw-r--r-- 590 bytes
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
package algorithms

func hoarePartition(xs []int, low, high int) int {
	pivotValue := xs[(high+low)/2]
	i := low - 1
	j := high + 1

	for {
		for i = i + 1; xs[i] < pivotValue; i++ {
		}
		for j = j - 1; xs[j] > pivotValue; j-- {
		}

		// The loops below are a more literal version of Hoare’s partition,
		// but they are far less idiomatic Go.
		//
		// for {
		// 	i++
		// 	if xs[i] >= pivotValue {
		// 		break
		// 	}
		// }
		// for {
		// 	j--
		// 	if xs[j] <= pivotValue {
		// 		break
		// 	}
		// }

		if i < j {
			xs[i], xs[j] = xs[j], xs[i]
		} else {
			return j
		}
	}
}