sort/quick3way.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

package sort

import (
	"github.com/snonux/algorithms/ds"
)

// Quick3Way uses a 3-way partitioning so it is more efficient dealing with duplicates
func Quick3Way(a ds.ArrayList) ds.ArrayList {
	Shuffle(a)
	quick3Way(a)
	return a
}

func quick3Way(a ds.ArrayList) {
	l := len(a)
	if l <= 10 {
		Insertion(a)
		return
	}

	lt := 0     // Lower than
	i := 1      // lt..i contain duplicates
	gt := l - 1 // Greater than

	a.Swap(0, median(a, l))
	v := a[0]

	for i <= gt {
		switch {
		case a[i] < v:
			a.Swap(lt, i)
			lt++
			i++
		case a[i] > v:
			a.Swap(i, gt)
			gt--
		default:
			// Duplicate
			i++
		}
	}
	// Now a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]

	quick3Way(a[0:lt])
	quick3Way(a[gt+1:])
}