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. 4 5 package sort_test 6 7 import ( 8 "fmt" 9 "internal/testenv" 10 "math" 11 "math/rand" 12 . "sort" 13 "strconv" 14 stringspkg "strings" 15 "testing" 16 ) 17 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", "%*&^*&^&", "***"} 21 22 func TestSortIntSlice(t *testing.T) { 23 data := ints 24 a := IntSlice(data[0:]) 25 Sort(a) 26 if !IsSorted(a) { 27 t.Errorf("sorted %v", ints) 28 t.Errorf(" got %v", data) 29 } 30 } 31 32 func TestSortFloat64Slice(t *testing.T) { 33 data := float64s 34 a := Float64Slice(data[0:]) 35 Sort(a) 36 if !IsSorted(a) { 37 t.Errorf("sorted %v", float64s) 38 t.Errorf(" got %v", data) 39 } 40 } 41 42 func TestSortStringSlice(t *testing.T) { 43 data := strings 44 a := StringSlice(data[0:]) 45 Sort(a) 46 if !IsSorted(a) { 47 t.Errorf("sorted %v", strings) 48 t.Errorf(" got %v", data) 49 } 50 } 51 52 func TestInts(t *testing.T) { 53 data := ints 54 Ints(data[0:]) 55 if !IntsAreSorted(data[0:]) { 56 t.Errorf("sorted %v", ints) 57 t.Errorf(" got %v", data) 58 } 59 } 60 61 func TestFloat64s(t *testing.T) { 62 data := float64s 63 Float64s(data[0:]) 64 if !Float64sAreSorted(data[0:]) { 65 t.Errorf("sorted %v", float64s) 66 t.Errorf(" got %v", data) 67 } 68 } 69 70 func TestStrings(t *testing.T) { 71 data := strings 72 Strings(data[0:]) 73 if !StringsAreSorted(data[0:]) { 74 t.Errorf("sorted %v", strings) 75 t.Errorf(" got %v", data) 76 } 77 } 78 79 func TestSlice(t *testing.T) { 80 data := strings 81 Slice(data[:], func(i, j int) bool { 82 return data[i] < data[j] 83 }) 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) 87 } 88 } 89 90 func TestSortLarge_Random(t *testing.T) { 91 n := 1000000 92 if testing.Short() { 93 n /= 100 94 } 95 data := make([]int, n) 96 for i := 0; i < len(data); i++ { 97 data[i] = rand.Intn(100) 98 } 99 if IntsAreSorted(data) { 100 t.Fatalf("terrible rand.rand") 101 } 102 Ints(data) 103 if !IntsAreSorted(data) { 104 t.Errorf("sort didn't sort - 1M ints") 105 } 106 } 107 108 func TestReverseSortIntSlice(t *testing.T) { 109 data := ints 110 data1 := ints 111 a := IntSlice(data[0:]) 112 Sort(a) 113 r := IntSlice(data1[0:]) 114 Sort(Reverse(r)) 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") 118 } 119 if i > len(data)/2 { 120 break 121 } 122 } 123 } 124 125 type nonDeterministicTestingData struct { 126 r *rand.Rand 127 } 128 129 func (t *nonDeterministicTestingData) Len() int { 130 return 500 131 } 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") 135 } 136 return t.r.Float32() < 0.5 137 } 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") 141 } 142 } 143 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. 147 defer func() { 148 if r := recover(); r != nil { 149 t.Error(r) 150 } 151 }() 152 153 td := &nonDeterministicTestingData{ 154 r: rand.New(rand.NewSource(0)), 155 } 156 157 for i := 0; i < 10; i++ { 158 Sort(td) 159 } 160 } 161 162 func BenchmarkSortString1K(b *testing.B) { 163 b.StopTimer() 164 unsorted := make([]string, 1<<10) 165 for i := range unsorted { 166 unsorted[i] = strconv.Itoa(i ^ 0x2cc) 167 } 168 data := make([]string, len(unsorted)) 169 170 for i := 0; i < b.N; i++ { 171 copy(data, unsorted) 172 b.StartTimer() 173 Strings(data) 174 b.StopTimer() 175 } 176 } 177 178 func BenchmarkSortString1K_Slice(b *testing.B) { 179 b.StopTimer() 180 unsorted := make([]string, 1<<10) 181 for i := range unsorted { 182 unsorted[i] = strconv.Itoa(i ^ 0x2cc) 183 } 184 data := make([]string, len(unsorted)) 185 186 for i := 0; i < b.N; i++ { 187 copy(data, unsorted) 188 b.StartTimer() 189 Slice(data, func(i, j int) bool { return data[i] < data[j] }) 190 b.StopTimer() 191 } 192 } 193 194 func BenchmarkStableString1K(b *testing.B) { 195 b.StopTimer() 196 unsorted := make([]string, 1<<10) 197 for i := 0; i < len(data); i++ { 198 unsorted[i] = strconv.Itoa(i ^ 0x2cc) 199 } 200 data := make([]string, len(unsorted)) 201 202 for i := 0; i < b.N; i++ { 203 copy(data, unsorted) 204 b.StartTimer() 205 Stable(StringSlice(data)) 206 b.StopTimer() 207 } 208 } 209 210 func BenchmarkSortInt1K(b *testing.B) { 211 b.StopTimer() 212 for i := 0; i < b.N; i++ { 213 data := make([]int, 1<<10) 214 for i := 0; i < len(data); i++ { 215 data[i] = i ^ 0x2cc 216 } 217 b.StartTimer() 218 Ints(data) 219 b.StopTimer() 220 } 221 } 222 223 func BenchmarkStableInt1K(b *testing.B) { 224 b.StopTimer() 225 unsorted := make([]int, 1<<10) 226 for i := range unsorted { 227 unsorted[i] = i ^ 0x2cc 228 } 229 data := make([]int, len(unsorted)) 230 for i := 0; i < b.N; i++ { 231 copy(data, unsorted) 232 b.StartTimer() 233 Stable(IntSlice(data)) 234 b.StopTimer() 235 } 236 } 237 238 func BenchmarkStableInt1K_Slice(b *testing.B) { 239 b.StopTimer() 240 unsorted := make([]int, 1<<10) 241 for i := range unsorted { 242 unsorted[i] = i ^ 0x2cc 243 } 244 data := make([]int, len(unsorted)) 245 for i := 0; i < b.N; i++ { 246 copy(data, unsorted) 247 b.StartTimer() 248 SliceStable(data, func(i, j int) bool { return data[i] < data[j] }) 249 b.StopTimer() 250 } 251 } 252 253 func BenchmarkSortInt64K(b *testing.B) { 254 b.StopTimer() 255 for i := 0; i < b.N; i++ { 256 data := make([]int, 1<<16) 257 for i := 0; i < len(data); i++ { 258 data[i] = i ^ 0xcccc 259 } 260 b.StartTimer() 261 Ints(data) 262 b.StopTimer() 263 } 264 } 265 266 func BenchmarkSortInt64K_Slice(b *testing.B) { 267 b.StopTimer() 268 for i := 0; i < b.N; i++ { 269 data := make([]int, 1<<16) 270 for i := 0; i < len(data); i++ { 271 data[i] = i ^ 0xcccc 272 } 273 b.StartTimer() 274 Slice(data, func(i, j int) bool { return data[i] < data[j] }) 275 b.StopTimer() 276 } 277 } 278 279 func BenchmarkStableInt64K(b *testing.B) { 280 b.StopTimer() 281 for i := 0; i < b.N; i++ { 282 data := make([]int, 1<<16) 283 for i := 0; i < len(data); i++ { 284 data[i] = i ^ 0xcccc 285 } 286 b.StartTimer() 287 Stable(IntSlice(data)) 288 b.StopTimer() 289 } 290 } 291 292 const ( 293 _Sawtooth = iota 294 _Rand 295 _Stagger 296 _Plateau 297 _Shuffle 298 _NDist 299 ) 300 301 const ( 302 _Copy = iota 303 _Reverse 304 _ReverseFirstHalf 305 _ReverseSecondHalf 306 _Sorted 307 _Dither 308 _NMode 309 ) 310 311 type testingData struct { 312 desc string 313 t *testing.T 314 data []int 315 maxswap int // number of swaps allowed 316 ncmp, nswap int 317 } 318 319 func (d *testingData) Len() int { return len(d.data) } 320 func (d *testingData) Less(i, j int) bool { 321 d.ncmp++ 322 return d.data[i] < d.data[j] 323 } 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)) 327 d.t.FailNow() 328 } 329 d.nswap++ 330 d.data[i], d.data[j] = d.data[j], d.data[i] 331 } 332 333 func min(a, b int) int { 334 if a < b { 335 return a 336 } 337 return b 338 } 339 340 func lg(n int) int { 341 i := 0 342 for 1<<uint(i) < n { 343 i++ 344 } 345 return i 346 } 347 348 func testBentleyMcIlroy(t *testing.T, sort func(Interface), maxswap func(int) int) { 349 sizes := []int{100, 1023, 1024, 1025} 350 if testing.Short() { 351 sizes = []int{100, 127, 128, 129} 352 } 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++ { 359 j := 0 360 k := 1 361 data := tmp1[0:n] 362 for i := 0; i < n; i++ { 363 switch dist { 364 case _Sawtooth: 365 data[i] = i % m 366 case _Rand: 367 data[i] = rand.Intn(m) 368 case _Stagger: 369 data[i] = (i*m + i) % n 370 case _Plateau: 371 data[i] = min(i, m) 372 case _Shuffle: 373 if rand.Intn(m) != 0 { 374 j += 2 375 data[i] = j 376 } else { 377 k += 2 378 data[i] = k 379 } 380 } 381 } 382 383 mdata := tmp2[0:n] 384 for mode := 0; mode < _NMode; mode++ { 385 switch mode { 386 case _Copy: 387 for i := 0; i < n; i++ { 388 mdata[i] = data[i] 389 } 390 case _Reverse: 391 for i := 0; i < n; i++ { 392 mdata[i] = data[n-i-1] 393 } 394 case _ReverseFirstHalf: 395 for i := 0; i < n/2; i++ { 396 mdata[i] = data[n/2-i-1] 397 } 398 for i := n / 2; i < n; i++ { 399 mdata[i] = data[i] 400 } 401 case _ReverseSecondHalf: 402 for i := 0; i < n/2; i++ { 403 mdata[i] = data[i] 404 } 405 for i := n / 2; i < n; i++ { 406 mdata[i] = data[n-(i-n/2)-1] 407 } 408 case _Sorted: 409 for i := 0; i < n; i++ { 410 mdata[i] = data[i] 411 } 412 // Ints is known to be correct 413 // because mode Sort runs after mode _Copy. 414 Ints(mdata) 415 case _Dither: 416 for i := 0; i < n; i++ { 417 mdata[i] = data[i] + i%5 418 } 419 } 420 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)} 423 sort(d) 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) 426 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. 431 // 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) 438 t.FailNow() 439 } 440 } 441 } 442 } 443 } 444 } 445 446 func TestSortBM(t *testing.T) { 447 testBentleyMcIlroy(t, Sort, func(n int) int { return n * lg(n) * 12 / 10 }) 448 } 449 450 func TestHeapsortBM(t *testing.T) { 451 testBentleyMcIlroy(t, Heapsort, func(n int) int { return n * lg(n) * 12 / 10 }) 452 } 453 454 func TestStableBM(t *testing.T) { 455 testBentleyMcIlroy(t, Stable, func(n int) int { return n * lg(n) * lg(n) / 3 }) 456 } 457 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 { 461 data []int 462 keys map[int]int 463 candidate int 464 } 465 466 func (d *adversaryTestingData) Len() int { return len(d.data) } 467 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) 473 } else { 474 d.keys[j] = len(d.keys) 475 } 476 } 477 } 478 479 if _, present := d.keys[i]; !present { 480 d.candidate = i 481 return false 482 } 483 if _, present := d.keys[j]; !present { 484 d.candidate = j 485 return true 486 } 487 488 return d.keys[i] >= d.keys[j] 489 } 490 491 func (d *adversaryTestingData) Swap(i, j int) { 492 d.data[i], d.data[j] = d.data[j], d.data[i] 493 } 494 495 func TestAdversary(t *testing.T) { 496 const size = 100 497 data := make([]int, size) 498 for i := 0; i < size; i++ { 499 data[i] = i 500 } 501 502 d := &adversaryTestingData{data, make(map[int]int), 0} 503 Sort(d) // This should degenerate to heapsort. 504 } 505 506 func TestStableInts(t *testing.T) { 507 data := ints 508 Stable(IntSlice(data[0:])) 509 if !IntsAreSorted(data[0:]) { 510 t.Errorf("nsorted %v\n got %v", ints, data) 511 } 512 } 513 514 type intPairs []struct { 515 a, b int 516 } 517 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] } 522 523 // Record initial order in B. 524 func (d intPairs) initB() { 525 for i := range d { 526 d[i].b = i 527 } 528 } 529 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++ { 534 if lastA != d[i].a { 535 lastA = d[i].a 536 lastB = d[i].b 537 continue 538 } 539 if d[i].b <= lastB { 540 return false 541 } 542 lastB = d[i].b 543 } 544 return true 545 } 546 547 func TestStability(t *testing.T) { 548 n, m := 100000, 1000 549 if testing.Short() { 550 n, m = 1000, 100 551 } 552 data := make(intPairs, n) 553 554 // random distribution 555 for i := 0; i < len(data); i++ { 556 data[i].a = rand.Intn(m) 557 } 558 if IsSorted(data) { 559 t.Fatalf("terrible rand.rand") 560 } 561 data.initB() 562 Stable(data) 563 if !IsSorted(data) { 564 t.Errorf("Stable didn't sort %d ints", n) 565 } 566 if !data.inOrder() { 567 t.Errorf("Stable wasn't stable on %d ints", n) 568 } 569 570 // already sorted 571 data.initB() 572 Stable(data) 573 if !IsSorted(data) { 574 t.Errorf("Stable shuffled sorted %d ints (order)", n) 575 } 576 if !data.inOrder() { 577 t.Errorf("Stable shuffled sorted %d ints (stability)", n) 578 } 579 580 // sorted reversed 581 for i := 0; i < len(data); i++ { 582 data[i].a = len(data) - i 583 } 584 data.initB() 585 Stable(data) 586 if !IsSorted(data) { 587 t.Errorf("Stable didn't sort %d ints", n) 588 } 589 if !data.inOrder() { 590 t.Errorf("Stable wasn't stable on %d ints", n) 591 } 592 } 593 594 var countOpsSizes = []int{1e2, 3e2, 1e3, 3e3, 1e4, 3e4, 1e5, 3e5, 1e6} 595 596 func countOps(t *testing.T, algo func(Interface), name string) { 597 sizes := countOpsSizes 598 if testing.Short() { 599 sizes = sizes[:5] 600 } 601 if !testing.Verbose() { 602 t.Skip("Counting skipped as non-verbose mode.") 603 } 604 for _, n := range sizes { 605 td := testingData{ 606 desc: name, 607 t: t, 608 data: make([]int, n), 609 maxswap: 1<<31 - 1, 610 } 611 for i := 0; i < n; i++ { 612 td.data[i] = rand.Intn(n / 5) 613 } 614 algo(&td) 615 t.Logf("%s %8d elements: %11d Swap, %10d Less", name, n, td.nswap, td.ncmp) 616 } 617 } 618 619 func TestCountStableOps(t *testing.T) { countOps(t, Stable, "Stable") } 620 func TestCountSortOps(t *testing.T) { countOps(t, Sort, "Sort ") } 621 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") 625 } 626 b.StopTimer() 627 data := make(intPairs, size) 628 x := ^uint32(0) 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++ { 632 x += x 633 x ^= 1 634 if int32(x) < 0 { 635 x ^= 0x88888eef 636 } 637 data[i].a = int(x % uint32(n/5)) 638 } 639 data.initB() 640 b.StartTimer() 641 algo(data) 642 b.StopTimer() 643 if !IsSorted(data) { 644 b.Errorf("%s did not sort %d ints", name, n) 645 } 646 if name == "Stable" && !data.inOrder() { 647 b.Errorf("%s unstable on %d ints", name, n) 648 } 649 } 650 } 651 } 652 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") } 659