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

package sort

import (
	"algorithms/ds"
)

// Quick2 uses a 3-way partitioning so it is more efficient
// dealing with duplicates
func Quick2(a ds.ArrayList) ds.ArrayList {
	a = Shuffle(a)
	quick2(a, 0, len(a)-1)
	return a
}

func quick2(a ds.ArrayList, lo, hi int) {
	if hi <= lo {
		return
	}

	lt := lo    // Lower than
	i := lo + 1 // lt..i contain duplicates
	gt := hi    // Greater than
	v := a[lo]  // Partitioning item

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

	quick2(a, lo, lt-1)
	quick2(a, gt+1, hi)
}