~telemachus/algorithms

ref: 597d3c5170b0fd3982a2aa1d12e39179f2293bbf algorithms/quicksort.go -rw-r--r-- 938 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
37
38
39
package algorithms

// QuicksortL implements quicksort using Lomuto’s partition.
func QuicksortL(xs []int, low, high int) {
	if high-low <= 0 {
		return
	}

	pivotIndex := lomutoPartition(xs, low, high)
	QuicksortL(xs, low, pivotIndex-1)
	QuicksortL(xs, pivotIndex+1, high)
}

// QuicksortH implements quicksort using Hoare’s partition.
func QuicksortH(xs []int, low, high int) {
	if high-low <= 0 {
		return
	}

	pivotIndex := hoarePartition(xs, low, high)
	QuicksortH(xs, low, pivotIndex)
	QuicksortH(xs, pivotIndex+1, high)
}

// QuicksortYB implements quicksort using Stefan Nilsson’s partition.
// See the following links:
// - https://yourbasic.org/golang/quicksort-optimizations
// - https://yourbasic.org/about
func QuicksortYB(xs []int) {
	if len(xs) < 20 {
		InsertionSort(xs)
		return
	}

	pivotIndex := yourBasicPivot(xs)
	low, high := yourBasicPartition(xs, pivotIndex)
	QuicksortYB(xs[:low])
	QuicksortYB(xs[high:])
}