1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
18 var ints
= [...]int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
19 var float64s
= [...]float64{74.3, 59.0, math
.Inf(1), 238.2, -784.0, 2.3, math
.NaN(), math
.NaN(), math
.Inf(-1), 9845.768, -959.7485, 905, 7.8, 7.8}
20 var strings
= [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
22 func TestSortIntSlice(t
*testing
.T
) {
24 a
:= IntSlice(data
[0:])
27 t
.Errorf("sorted %v", ints
)
28 t
.Errorf(" got %v", data
)
32 func TestSortFloat64Slice(t
*testing
.T
) {
34 a
:= Float64Slice(data
[0:])
37 t
.Errorf("sorted %v", float64s
)
38 t
.Errorf(" got %v", data
)
42 func TestSortStringSlice(t
*testing
.T
) {
44 a
:= StringSlice(data
[0:])
47 t
.Errorf("sorted %v", strings
)
48 t
.Errorf(" got %v", data
)
52 func TestInts(t
*testing
.T
) {
55 if !IntsAreSorted(data
[0:]) {
56 t
.Errorf("sorted %v", ints
)
57 t
.Errorf(" got %v", data
)
61 func TestFloat64s(t
*testing
.T
) {
64 if !Float64sAreSorted(data
[0:]) {
65 t
.Errorf("sorted %v", float64s
)
66 t
.Errorf(" got %v", data
)
70 func TestStrings(t
*testing
.T
) {
73 if !StringsAreSorted(data
[0:]) {
74 t
.Errorf("sorted %v", strings
)
75 t
.Errorf(" got %v", data
)
79 func TestSlice(t
*testing
.T
) {
81 Slice(data
[:], func(i
, j
int) bool {
82 return data
[i
] < data
[j
]
84 if !SliceIsSorted(data
[:], func(i
, j
int) bool { return data
[i
] < data
[j
] }) {
85 t
.Errorf("sorted %v", strings
)
86 t
.Errorf(" got %v", data
)
90 func TestSortLarge_Random(t
*testing
.T
) {
95 data
:= make([]int, n
)
96 for i
:= 0; i
< len(data
); i
++ {
97 data
[i
] = rand
.Intn(100)
99 if IntsAreSorted(data
) {
100 t
.Fatalf("terrible rand.rand")
103 if !IntsAreSorted(data
) {
104 t
.Errorf("sort didn't sort - 1M ints")
108 func TestReverseSortIntSlice(t
*testing
.T
) {
111 a
:= IntSlice(data
[0:])
113 r
:= IntSlice(data1
[0:])
115 for i
:= 0; i
< len(data
); i
++ {
116 if a
[i
] != r
[len(data
)-1-i
] {
117 t
.Errorf("reverse sort didn't sort")
125 type nonDeterministicTestingData
struct {
129 func (t
*nonDeterministicTestingData
) Len() int {
132 func (t
*nonDeterministicTestingData
) Less(i
, j
int) bool {
133 if i
< 0 || j
< 0 || i
>= t
.Len() || j
>= t
.Len() {
134 panic("nondeterministic comparison out of bounds")
136 return t
.r
.Float32() < 0.5
138 func (t
*nonDeterministicTestingData
) Swap(i
, j
int) {
139 if i
< 0 || j
< 0 || i
>= t
.Len() || j
>= t
.Len() {
140 panic("nondeterministic comparison out of bounds")
144 func TestNonDeterministicComparison(t
*testing
.T
) {
145 // Ensure that sort.Sort does not panic when Less returns inconsistent results.
146 // See https://golang.org/issue/14377.
148 if r
:= recover(); r
!= nil {
153 td
:= &nonDeterministicTestingData
{
154 r
: rand
.New(rand
.NewSource(0)),
157 for i
:= 0; i
< 10; i
++ {
162 func BenchmarkSortString1K(b
*testing
.B
) {
164 unsorted
:= make([]string, 1<<10)
165 for i
:= range unsorted
{
166 unsorted
[i
] = strconv
.Itoa(i
^ 0x2cc)
168 data
:= make([]string, len(unsorted
))
170 for i
:= 0; i
< b
.N
; i
++ {
178 func BenchmarkSortString1K_Slice(b
*testing
.B
) {
180 unsorted
:= make([]string, 1<<10)
181 for i
:= range unsorted
{
182 unsorted
[i
] = strconv
.Itoa(i
^ 0x2cc)
184 data
:= make([]string, len(unsorted
))
186 for i
:= 0; i
< b
.N
; i
++ {
189 Slice(data
, func(i
, j
int) bool { return data
[i
] < data
[j
] })
194 func BenchmarkStableString1K(b
*testing
.B
) {
196 unsorted
:= make([]string, 1<<10)
197 for i
:= 0; i
< len(data
); i
++ {
198 unsorted
[i
] = strconv
.Itoa(i
^ 0x2cc)
200 data
:= make([]string, len(unsorted
))
202 for i
:= 0; i
< b
.N
; i
++ {
205 Stable(StringSlice(data
))
210 func BenchmarkSortInt1K(b
*testing
.B
) {
212 for i
:= 0; i
< b
.N
; i
++ {
213 data
:= make([]int, 1<<10)
214 for i
:= 0; i
< len(data
); i
++ {
223 func BenchmarkStableInt1K(b
*testing
.B
) {
225 unsorted
:= make([]int, 1<<10)
226 for i
:= range unsorted
{
227 unsorted
[i
] = i
^ 0x2cc
229 data
:= make([]int, len(unsorted
))
230 for i
:= 0; i
< b
.N
; i
++ {
233 Stable(IntSlice(data
))
238 func BenchmarkStableInt1K_Slice(b
*testing
.B
) {
240 unsorted
:= make([]int, 1<<10)
241 for i
:= range unsorted
{
242 unsorted
[i
] = i
^ 0x2cc
244 data
:= make([]int, len(unsorted
))
245 for i
:= 0; i
< b
.N
; i
++ {
248 SliceStable(data
, func(i
, j
int) bool { return data
[i
] < data
[j
] })
253 func BenchmarkSortInt64K(b
*testing
.B
) {
255 for i
:= 0; i
< b
.N
; i
++ {
256 data
:= make([]int, 1<<16)
257 for i
:= 0; i
< len(data
); i
++ {
266 func BenchmarkSortInt64K_Slice(b
*testing
.B
) {
268 for i
:= 0; i
< b
.N
; i
++ {
269 data
:= make([]int, 1<<16)
270 for i
:= 0; i
< len(data
); i
++ {
274 Slice(data
, func(i
, j
int) bool { return data
[i
] < data
[j
] })
279 func BenchmarkStableInt64K(b
*testing
.B
) {
281 for i
:= 0; i
< b
.N
; i
++ {
282 data
:= make([]int, 1<<16)
283 for i
:= 0; i
< len(data
); i
++ {
287 Stable(IntSlice(data
))
311 type testingData
struct {
315 maxswap
int // number of swaps allowed
319 func (d
*testingData
) Len() int { return len(d
.data
) }
320 func (d
*testingData
) Less(i
, j
int) bool {
322 return d
.data
[i
] < d
.data
[j
]
324 func (d
*testingData
) Swap(i
, j
int) {
325 if d
.nswap
>= d
.maxswap
{
326 d
.t
.Errorf("%s: used %d swaps sorting slice of %d", d
.desc
, d
.nswap
, len(d
.data
))
330 d
.data
[i
], d
.data
[j
] = d
.data
[j
], d
.data
[i
]
333 func min(a
, b
int) int {
348 func testBentleyMcIlroy(t
*testing
.T
, sort
func(Interface
), maxswap
func(int) int) {
349 sizes
:= []int{100, 1023, 1024, 1025}
351 sizes
= []int{100, 127, 128, 129}
353 dists
:= []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"}
354 modes
:= []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"}
355 var tmp1
, tmp2
[1025]int
356 for _
, n
:= range sizes
{
357 for m
:= 1; m
< 2*n
; m
*= 2 {
358 for dist
:= 0; dist
< _NDist
; dist
++ {
362 for i
:= 0; i
< n
; i
++ {
367 data
[i
] = rand
.Intn(m
)
369 data
[i
] = (i
*m
+ i
) % n
373 if rand
.Intn(m
) != 0 {
384 for mode
:= 0; mode
< _NMode
; mode
++ {
387 for i
:= 0; i
< n
; i
++ {
391 for i
:= 0; i
< n
; i
++ {
392 mdata
[i
] = data
[n
-i
-1]
394 case _ReverseFirstHalf
:
395 for i
:= 0; i
< n
/2; i
++ {
396 mdata
[i
] = data
[n
/2-i
-1]
398 for i
:= n
/ 2; i
< n
; i
++ {
401 case _ReverseSecondHalf
:
402 for i
:= 0; i
< n
/2; i
++ {
405 for i
:= n
/ 2; i
< n
; i
++ {
406 mdata
[i
] = data
[n
-(i
-n
/2)-1]
409 for i
:= 0; i
< n
; i
++ {
412 // Ints is known to be correct
413 // because mode Sort runs after mode _Copy.
416 for i
:= 0; i
< n
; i
++ {
417 mdata
[i
] = data
[i
] + i%5
421 desc
:= fmt
.Sprintf("n=%d m=%d dist=%s mode=%s", n
, m
, dists
[dist
], modes
[mode
])
422 d
:= &testingData
{desc
: desc
, t
: t
, data
: mdata
[0:n
], maxswap
: maxswap(n
)}
424 // Uncomment if you are trying to improve the number of compares/swaps.
425 //t.Logf("%s: ncmp=%d, nswp=%d", desc, d.ncmp, d.nswap)
427 // If we were testing C qsort, we'd have to make a copy
428 // of the slice and sort it ourselves and then compare
429 // x against it, to ensure that qsort was only permuting
430 // the data, not (for example) overwriting it with zeros.
432 // In go, we don't have to be so paranoid: since the only
433 // mutating method Sort can call is TestingData.swap,
434 // it suffices here just to check that the final slice is sorted.
435 if !IntsAreSorted(mdata
) {
436 t
.Errorf("%s: ints not sorted", desc
)
437 t
.Errorf("\t%v", mdata
)
446 func TestSortBM(t
*testing
.T
) {
447 testBentleyMcIlroy(t
, Sort
, func(n
int) int { return n
* lg(n
) * 12 / 10 })
450 func TestHeapsortBM(t
*testing
.T
) {
451 testBentleyMcIlroy(t
, Heapsort
, func(n
int) int { return n
* lg(n
) * 12 / 10 })
454 func TestStableBM(t
*testing
.T
) {
455 testBentleyMcIlroy(t
, Stable
, func(n
int) int { return n
* lg(n
) * lg(n
) / 3 })
458 // This is based on the "antiquicksort" implementation by M. Douglas McIlroy.
459 // See http://www.cs.dartmouth.edu/~doug/mdmspe.pdf for more info.
460 type adversaryTestingData
struct {
466 func (d
*adversaryTestingData
) Len() int { return len(d
.data
) }
468 func (d
*adversaryTestingData
) Less(i
, j
int) bool {
469 if _
, present
:= d
.keys
[i
]; !present
{
470 if _
, present
:= d
.keys
[j
]; !present
{
471 if i
== d
.candidate
{
472 d
.keys
[i
] = len(d
.keys
)
474 d
.keys
[j
] = len(d
.keys
)
479 if _
, present
:= d
.keys
[i
]; !present
{
483 if _
, present
:= d
.keys
[j
]; !present
{
488 return d
.keys
[i
] >= d
.keys
[j
]
491 func (d
*adversaryTestingData
) Swap(i
, j
int) {
492 d
.data
[i
], d
.data
[j
] = d
.data
[j
], d
.data
[i
]
495 func TestAdversary(t
*testing
.T
) {
497 data
:= make([]int, size
)
498 for i
:= 0; i
< size
; i
++ {
502 d
:= &adversaryTestingData
{data
, make(map[int]int), 0}
503 Sort(d
) // This should degenerate to heapsort.
506 func TestStableInts(t
*testing
.T
) {
508 Stable(IntSlice(data
[0:]))
509 if !IntsAreSorted(data
[0:]) {
510 t
.Errorf("nsorted %v\n got %v", ints
, data
)
514 type intPairs
[]struct {
518 // IntPairs compare on a only.
519 func (d intPairs
) Len() int { return len(d
) }
520 func (d intPairs
) Less(i
, j
int) bool { return d
[i
].a
< d
[j
].a
}
521 func (d intPairs
) Swap(i
, j
int) { d
[i
], d
[j
] = d
[j
], d
[i
] }
523 // Record initial order in B.
524 func (d intPairs
) initB() {
530 // InOrder checks if a-equal elements were not reordered.
531 func (d intPairs
) inOrder() bool {
532 lastA
, lastB
:= -1, 0
533 for i
:= 0; i
< len(d
); i
++ {
547 func TestStability(t
*testing
.T
) {
552 data
:= make(intPairs
, n
)
554 // random distribution
555 for i
:= 0; i
< len(data
); i
++ {
556 data
[i
].a
= rand
.Intn(m
)
559 t
.Fatalf("terrible rand.rand")
564 t
.Errorf("Stable didn't sort %d ints", n
)
567 t
.Errorf("Stable wasn't stable on %d ints", n
)
574 t
.Errorf("Stable shuffled sorted %d ints (order)", n
)
577 t
.Errorf("Stable shuffled sorted %d ints (stability)", n
)
581 for i
:= 0; i
< len(data
); i
++ {
582 data
[i
].a
= len(data
) - i
587 t
.Errorf("Stable didn't sort %d ints", n
)
590 t
.Errorf("Stable wasn't stable on %d ints", n
)
594 var countOpsSizes
= []int{1e2
, 3e2
, 1e3
, 3e3
, 1e4
, 3e4
, 1e5
, 3e5
, 1e6
}
596 func countOps(t
*testing
.T
, algo
func(Interface
), name
string) {
597 sizes
:= countOpsSizes
601 if !testing
.Verbose() {
602 t
.Skip("Counting skipped as non-verbose mode.")
604 for _
, n
:= range sizes
{
608 data
: make([]int, n
),
611 for i
:= 0; i
< n
; i
++ {
612 td
.data
[i
] = rand
.Intn(n
/ 5)
615 t
.Logf("%s %8d elements: %11d Swap, %10d Less", name
, n
, td
.nswap
, td
.ncmp
)
619 func TestCountStableOps(t
*testing
.T
) { countOps(t
, Stable
, "Stable") }
620 func TestCountSortOps(t
*testing
.T
) { countOps(t
, Sort
, "Sort ") }
622 func bench(b
*testing
.B
, size
int, algo
func(Interface
), name
string) {
623 if stringspkg
.HasSuffix(testenv
.Builder(), "-race") && size
> 1e4
{
624 b
.Skip("skipping slow benchmark on race builder")
627 data
:= make(intPairs
, size
)
629 for i
:= 0; i
< b
.N
; i
++ {
630 for n
:= size
- 3; n
<= size
+3; n
++ {
631 for i
:= 0; i
< len(data
); i
++ {
637 data
[i
].a
= int(x
% uint32(n
/5))
644 b
.Errorf("%s did not sort %d ints", name
, n
)
646 if name
== "Stable" && !data
.inOrder() {
647 b
.Errorf("%s unstable on %d ints", name
, n
)
653 func BenchmarkSort1e2(b
*testing
.B
) { bench(b
, 1e2
, Sort
, "Sort") }
654 func BenchmarkStable1e2(b
*testing
.B
) { bench(b
, 1e2
, Stable
, "Stable") }
655 func BenchmarkSort1e4(b
*testing
.B
) { bench(b
, 1e4
, Sort
, "Sort") }
656 func BenchmarkStable1e4(b
*testing
.B
) { bench(b
, 1e4
, Stable
, "Stable") }
657 func BenchmarkSort1e6(b
*testing
.B
) { bench(b
, 1e6
, Sort
, "Sort") }
658 func BenchmarkStable1e6(b
*testing
.B
) { bench(b
, 1e6
, Stable
, "Stable") }