Source file src/sort/zfuncversion.go
1
2
3
4
5
6
7 package sort
8
9
10 func insertionSort_func(data lessSwap, a, b int) {
11 for i := a + 1; i < b; i++ {
12 for j := i; j > a && data.Less(j, j-1); j-- {
13 data.Swap(j, j-1)
14 }
15 }
16 }
17
18
19 func siftDown_func(data lessSwap, lo, hi, first int) {
20 root := lo
21 for {
22 child := 2*root + 1
23 if child >= hi {
24 break
25 }
26 if child+1 < hi && data.Less(first+child, first+child+1) {
27 child++
28 }
29 if !data.Less(first+root, first+child) {
30 return
31 }
32 data.Swap(first+root, first+child)
33 root = child
34 }
35 }
36
37
38 func heapSort_func(data lessSwap, a, b int) {
39 first := a
40 lo := 0
41 hi := b - a
42 for i := (hi - 1) / 2; i >= 0; i-- {
43 siftDown_func(data, i, hi, first)
44 }
45 for i := hi - 1; i >= 0; i-- {
46 data.Swap(first, first+i)
47 siftDown_func(data, lo, i, first)
48 }
49 }
50
51
52 func medianOfThree_func(data lessSwap, m1, m0, m2 int) {
53 if data.Less(m1, m0) {
54 data.Swap(m1, m0)
55 }
56 if data.Less(m2, m1) {
57 data.Swap(m2, m1)
58 if data.Less(m1, m0) {
59 data.Swap(m1, m0)
60 }
61 }
62 }
63
64
65 func swapRange_func(data lessSwap, a, b, n int) {
66 for i := 0; i < n; i++ {
67 data.Swap(a+i, b+i)
68 }
69 }
70
71
72 func doPivot_func(data lessSwap, lo, hi int) (midlo, midhi int) {
73 m := int(uint(lo+hi) >> 1)
74 if hi-lo > 40 {
75 s := (hi - lo) / 8
76 medianOfThree_func(data, lo, lo+s, lo+2*s)
77 medianOfThree_func(data, m, m-s, m+s)
78 medianOfThree_func(data, hi-1, hi-1-s, hi-1-2*s)
79 }
80 medianOfThree_func(data, lo, m, hi-1)
81 pivot := lo
82 a, c := lo+1, hi-1
83 for ; a < c && data.Less(a, pivot); a++ {
84 }
85 b := a
86 for {
87 for ; b < c && !data.Less(pivot, b); b++ {
88 }
89 for ; b < c && data.Less(pivot, c-1); c-- {
90 }
91 if b >= c {
92 break
93 }
94 data.Swap(b, c-1)
95 b++
96 c--
97 }
98 protect := hi-c < 5
99 if !protect && hi-c < (hi-lo)/4 {
100 dups := 0
101 if !data.Less(pivot, hi-1) {
102 data.Swap(c, hi-1)
103 c++
104 dups++
105 }
106 if !data.Less(b-1, pivot) {
107 b--
108 dups++
109 }
110 if !data.Less(m, pivot) {
111 data.Swap(m, b-1)
112 b--
113 dups++
114 }
115 protect = dups > 1
116 }
117 if protect {
118 for {
119 for ; a < b && !data.Less(b-1, pivot); b-- {
120 }
121 for ; a < b && data.Less(a, pivot); a++ {
122 }
123 if a >= b {
124 break
125 }
126 data.Swap(a, b-1)
127 a++
128 b--
129 }
130 }
131 data.Swap(pivot, b-1)
132 return b - 1, c
133 }
134
135
136 func quickSort_func(data lessSwap, a, b, maxDepth int) {
137 for b-a > 12 {
138 if maxDepth == 0 {
139 heapSort_func(data, a, b)
140 return
141 }
142 maxDepth--
143 mlo, mhi := doPivot_func(data, a, b)
144 if mlo-a < b-mhi {
145 quickSort_func(data, a, mlo, maxDepth)
146 a = mhi
147 } else {
148 quickSort_func(data, mhi, b, maxDepth)
149 b = mlo
150 }
151 }
152 if b-a > 1 {
153 for i := a + 6; i < b; i++ {
154 if data.Less(i, i-6) {
155 data.Swap(i, i-6)
156 }
157 }
158 insertionSort_func(data, a, b)
159 }
160 }
161
162
163 func stable_func(data lessSwap, n int) {
164 blockSize := 20
165 a, b := 0, blockSize
166 for b <= n {
167 insertionSort_func(data, a, b)
168 a = b
169 b += blockSize
170 }
171 insertionSort_func(data, a, n)
172 for blockSize < n {
173 a, b = 0, 2*blockSize
174 for b <= n {
175 symMerge_func(data, a, a+blockSize, b)
176 a = b
177 b += 2 * blockSize
178 }
179 if m := a + blockSize; m < n {
180 symMerge_func(data, a, m, n)
181 }
182 blockSize *= 2
183 }
184 }
185
186
187 func symMerge_func(data lessSwap, a, m, b int) {
188 if m-a == 1 {
189 i := m
190 j := b
191 for i < j {
192 h := int(uint(i+j) >> 1)
193 if data.Less(h, a) {
194 i = h + 1
195 } else {
196 j = h
197 }
198 }
199 for k := a; k < i-1; k++ {
200 data.Swap(k, k+1)
201 }
202 return
203 }
204 if b-m == 1 {
205 i := a
206 j := m
207 for i < j {
208 h := int(uint(i+j) >> 1)
209 if !data.Less(m, h) {
210 i = h + 1
211 } else {
212 j = h
213 }
214 }
215 for k := m; k > i; k-- {
216 data.Swap(k, k-1)
217 }
218 return
219 }
220 mid := int(uint(a+b) >> 1)
221 n := mid + m
222 var start, r int
223 if m > mid {
224 start = n - b
225 r = mid
226 } else {
227 start = a
228 r = m
229 }
230 p := n - 1
231 for start < r {
232 c := int(uint(start+r) >> 1)
233 if !data.Less(p-c, c) {
234 start = c + 1
235 } else {
236 r = c
237 }
238 }
239 end := n - start
240 if start < m && m < end {
241 rotate_func(data, start, m, end)
242 }
243 if a < start && start < mid {
244 symMerge_func(data, a, start, mid)
245 }
246 if mid < end && end < b {
247 symMerge_func(data, mid, end, b)
248 }
249 }
250
251
252 func rotate_func(data lessSwap, a, m, b int) {
253 i := m - a
254 j := b - m
255 for i != j {
256 if i > j {
257 swapRange_func(data, m-i, m, j)
258 i -= j
259 } else {
260 swapRange_func(data, m-i, m+j-i, i)
261 j -= i
262 }
263 }
264 swapRange_func(data, m-i, m, i)
265 }
266
View as plain text