blob: 32c1a4d3bd9340c70dc951d5049e3d545c30bd0f (
plain)
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
package sort
import (
"math/rand"
"codeberg.org/snonux/algorithms/ds"
)
func Quick[V ds.Number](a ds.ArrayList[V]) ds.ArrayList[V] {
quick(a)
return a
}
func quick[V ds.Number](a ds.ArrayList[V]) {
if len(a) <= 10 {
Insertion(a)
return
}
j := quickPartition(a)
quick(a[0:j])
quick(a[j+1:])
}
func quickPartition[V ds.Number](a ds.ArrayList[V]) int {
l := len(a)
i := 0 // Left scan index
j := l // Right scan index
hi := j - 1
a.Swap(0, median(a, l))
v := a[0]
for {
for i++; a[i] < v && i < hi; i++ {
}
for j--; v < a[j] && j > 0; j-- {
}
// Check scan complete
if i >= j {
break
}
a.Swap(i, j)
}
// Put partitioning item v into a[j]
a.Swap(0, j)
// whith a[lo..j-1 <= a[j] <= a[j+1..hi]
return j
}
func median[V ds.Number](a ds.ArrayList[V], l int) int {
u := rand.Intn(l)
v := rand.Intn(l)
w := rand.Intn(l)
x := a[u]
y := a[v]
z := a[w]
if x < y {
switch {
case y < z:
return v
case x < z:
return w
default:
return u
}
}
switch {
case x < z:
return u
case y < z:
return w
default:
return v
}
}
|
