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 {
462 data
[]int // item values, initialized to special gas value and changed by Less
463 maxcmp
int // number of comparisons allowed
464 ncmp
int // number of comparisons (calls to Less)
465 nsolid
int // number of elements that have been set to non-gas values
466 candidate
int // guess at current pivot
467 gas
int // special value for unset elements, higher than everything else
470 func (d
*adversaryTestingData
) Len() int { return len(d
.data
) }
472 func (d
*adversaryTestingData
) Less(i
, j
int) bool {
473 if d
.ncmp
>= d
.maxcmp
{
474 d
.t
.Fatalf("used %d comparisons sorting adversary data with size %d", d
.ncmp
, len(d
.data
))
478 if d
.data
[i
] == d
.gas
&& d
.data
[j
] == d
.gas
{
479 if i
== d
.candidate
{
490 if d
.data
[i
] == d
.gas
{
492 } else if d
.data
[j
] == d
.gas
{
496 return d
.data
[i
] < d
.data
[j
]
499 func (d
*adversaryTestingData
) Swap(i
, j
int) {
500 d
.data
[i
], d
.data
[j
] = d
.data
[j
], d
.data
[i
]
503 func newAdversaryTestingData(t
*testing
.T
, size
int, maxcmp
int) *adversaryTestingData
{
505 data
:= make([]int, size
)
506 for i
:= 0; i
< size
; i
++ {
509 return &adversaryTestingData
{t
: t
, data
: data
, maxcmp
: maxcmp
, gas
: gas
}
512 func TestAdversary(t
*testing
.T
) {
513 const size
= 10000 // large enough to distinguish between O(n^2) and O(n*log(n))
514 maxcmp
:= size
* lg(size
) * 4 // the factor 4 was found by trial and error
515 d
:= newAdversaryTestingData(t
, size
, maxcmp
)
516 Sort(d
) // This should degenerate to heapsort.
517 // Check data is fully populated and sorted.
518 for i
, v
:= range d
.data
{
520 t
.Errorf("adversary data not fully sorted")
526 func TestStableInts(t
*testing
.T
) {
528 Stable(IntSlice(data
[0:]))
529 if !IntsAreSorted(data
[0:]) {
530 t
.Errorf("nsorted %v\n got %v", ints
, data
)
534 type intPairs
[]struct {
538 // IntPairs compare on a only.
539 func (d intPairs
) Len() int { return len(d
) }
540 func (d intPairs
) Less(i
, j
int) bool { return d
[i
].a
< d
[j
].a
}
541 func (d intPairs
) Swap(i
, j
int) { d
[i
], d
[j
] = d
[j
], d
[i
] }
543 // Record initial order in B.
544 func (d intPairs
) initB() {
550 // InOrder checks if a-equal elements were not reordered.
551 func (d intPairs
) inOrder() bool {
552 lastA
, lastB
:= -1, 0
553 for i
:= 0; i
< len(d
); i
++ {
567 func TestStability(t
*testing
.T
) {
572 data
:= make(intPairs
, n
)
574 // random distribution
575 for i
:= 0; i
< len(data
); i
++ {
576 data
[i
].a
= rand
.Intn(m
)
579 t
.Fatalf("terrible rand.rand")
584 t
.Errorf("Stable didn't sort %d ints", n
)
587 t
.Errorf("Stable wasn't stable on %d ints", n
)
594 t
.Errorf("Stable shuffled sorted %d ints (order)", n
)
597 t
.Errorf("Stable shuffled sorted %d ints (stability)", n
)
601 for i
:= 0; i
< len(data
); i
++ {
602 data
[i
].a
= len(data
) - i
607 t
.Errorf("Stable didn't sort %d ints", n
)
610 t
.Errorf("Stable wasn't stable on %d ints", n
)
614 var countOpsSizes
= []int{1e2
, 3e2
, 1e3
, 3e3
, 1e4
, 3e4
, 1e5
, 3e5
, 1e6
}
616 func countOps(t
*testing
.T
, algo
func(Interface
), name
string) {
617 sizes
:= countOpsSizes
621 if !testing
.Verbose() {
622 t
.Skip("Counting skipped as non-verbose mode.")
624 for _
, n
:= range sizes
{
628 data
: make([]int, n
),
631 for i
:= 0; i
< n
; i
++ {
632 td
.data
[i
] = rand
.Intn(n
/ 5)
635 t
.Logf("%s %8d elements: %11d Swap, %10d Less", name
, n
, td
.nswap
, td
.ncmp
)
639 func TestCountStableOps(t
*testing
.T
) { countOps(t
, Stable
, "Stable") }
640 func TestCountSortOps(t
*testing
.T
) { countOps(t
, Sort
, "Sort ") }
642 func bench(b
*testing
.B
, size
int, algo
func(Interface
), name
string) {
643 if stringspkg
.HasSuffix(testenv
.Builder(), "-race") && size
> 1e4
{
644 b
.Skip("skipping slow benchmark on race builder")
647 data
:= make(intPairs
, size
)
649 for i
:= 0; i
< b
.N
; i
++ {
650 for n
:= size
- 3; n
<= size
+3; n
++ {
651 for i
:= 0; i
< len(data
); i
++ {
657 data
[i
].a
= int(x
% uint32(n
/5))
664 b
.Errorf("%s did not sort %d ints", name
, n
)
666 if name
== "Stable" && !data
.inOrder() {
667 b
.Errorf("%s unstable on %d ints", name
, n
)
673 func BenchmarkSort1e2(b
*testing
.B
) { bench(b
, 1e2
, Sort
, "Sort") }
674 func BenchmarkStable1e2(b
*testing
.B
) { bench(b
, 1e2
, Stable
, "Stable") }
675 func BenchmarkSort1e4(b
*testing
.B
) { bench(b
, 1e4
, Sort
, "Sort") }
676 func BenchmarkStable1e4(b
*testing
.B
) { bench(b
, 1e4
, Stable
, "Stable") }
677 func BenchmarkSort1e6(b
*testing
.B
) { bench(b
, 1e6
, Sort
, "Sort") }
678 func BenchmarkStable1e6(b
*testing
.B
) { bench(b
, 1e6
, Stable
, "Stable") }