Source file src/sort/sort_test.go

     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  func TestBreakPatterns(t *testing.T) {
   126  	// Special slice used to trigger breakPatterns.
   127  	data := make([]int, 30)
   128  	for i := range data {
   129  		data[i] = 10
   130  	}
   131  	data[(len(data)/4)*1] = 0
   132  	data[(len(data)/4)*2] = 1
   133  	data[(len(data)/4)*3] = 2
   134  	Sort(IntSlice(data))
   135  }
   136  
   137  func TestReverseRange(t *testing.T) {
   138  	data := []int{1, 2, 3, 4, 5, 6, 7}
   139  	ReverseRange(IntSlice(data), 0, len(data))
   140  	for i := len(data) - 1; i > 0; i-- {
   141  		if data[i] > data[i-1] {
   142  			t.Fatalf("reverseRange didn't work")
   143  		}
   144  	}
   145  
   146  	data1 := []int{1, 2, 3, 4, 5, 6, 7}
   147  	data2 := []int{1, 2, 5, 4, 3, 6, 7}
   148  	ReverseRange(IntSlice(data1), 2, 5)
   149  	for i, v := range data1 {
   150  		if v != data2[i] {
   151  			t.Fatalf("reverseRange didn't work")
   152  		}
   153  	}
   154  }
   155  
   156  type nonDeterministicTestingData struct {
   157  	r *rand.Rand
   158  }
   159  
   160  func (t *nonDeterministicTestingData) Len() int {
   161  	return 500
   162  }
   163  func (t *nonDeterministicTestingData) Less(i, j int) bool {
   164  	if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() {
   165  		panic("nondeterministic comparison out of bounds")
   166  	}
   167  	return t.r.Float32() < 0.5
   168  }
   169  func (t *nonDeterministicTestingData) Swap(i, j int) {
   170  	if i < 0 || j < 0 || i >= t.Len() || j >= t.Len() {
   171  		panic("nondeterministic comparison out of bounds")
   172  	}
   173  }
   174  
   175  func TestNonDeterministicComparison(t *testing.T) {
   176  	// Ensure that sort.Sort does not panic when Less returns inconsistent results.
   177  	// See https://golang.org/issue/14377.
   178  	defer func() {
   179  		if r := recover(); r != nil {
   180  			t.Error(r)
   181  		}
   182  	}()
   183  
   184  	td := &nonDeterministicTestingData{
   185  		r: rand.New(rand.NewSource(0)),
   186  	}
   187  
   188  	for i := 0; i < 10; i++ {
   189  		Sort(td)
   190  	}
   191  }
   192  
   193  func BenchmarkSortString1K(b *testing.B) {
   194  	b.StopTimer()
   195  	unsorted := make([]string, 1<<10)
   196  	for i := range unsorted {
   197  		unsorted[i] = strconv.Itoa(i ^ 0x2cc)
   198  	}
   199  	data := make([]string, len(unsorted))
   200  
   201  	for i := 0; i < b.N; i++ {
   202  		copy(data, unsorted)
   203  		b.StartTimer()
   204  		Strings(data)
   205  		b.StopTimer()
   206  	}
   207  }
   208  
   209  func BenchmarkSortString1K_Slice(b *testing.B) {
   210  	b.StopTimer()
   211  	unsorted := make([]string, 1<<10)
   212  	for i := range unsorted {
   213  		unsorted[i] = strconv.Itoa(i ^ 0x2cc)
   214  	}
   215  	data := make([]string, len(unsorted))
   216  
   217  	for i := 0; i < b.N; i++ {
   218  		copy(data, unsorted)
   219  		b.StartTimer()
   220  		Slice(data, func(i, j int) bool { return data[i] < data[j] })
   221  		b.StopTimer()
   222  	}
   223  }
   224  
   225  func BenchmarkStableString1K(b *testing.B) {
   226  	b.StopTimer()
   227  	unsorted := make([]string, 1<<10)
   228  	for i := range unsorted {
   229  		unsorted[i] = strconv.Itoa(i ^ 0x2cc)
   230  	}
   231  	data := make([]string, len(unsorted))
   232  
   233  	for i := 0; i < b.N; i++ {
   234  		copy(data, unsorted)
   235  		b.StartTimer()
   236  		Stable(StringSlice(data))
   237  		b.StopTimer()
   238  	}
   239  }
   240  
   241  func BenchmarkSortInt1K(b *testing.B) {
   242  	b.StopTimer()
   243  	for i := 0; i < b.N; i++ {
   244  		data := make([]int, 1<<10)
   245  		for i := 0; i < len(data); i++ {
   246  			data[i] = i ^ 0x2cc
   247  		}
   248  		b.StartTimer()
   249  		Ints(data)
   250  		b.StopTimer()
   251  	}
   252  }
   253  
   254  func BenchmarkSortInt1K_Sorted(b *testing.B) {
   255  	b.StopTimer()
   256  	for i := 0; i < b.N; i++ {
   257  		data := make([]int, 1<<10)
   258  		for i := 0; i < len(data); i++ {
   259  			data[i] = i
   260  		}
   261  		b.StartTimer()
   262  		Ints(data)
   263  		b.StopTimer()
   264  	}
   265  }
   266  
   267  func BenchmarkSortInt1K_Reversed(b *testing.B) {
   268  	b.StopTimer()
   269  	for i := 0; i < b.N; i++ {
   270  		data := make([]int, 1<<10)
   271  		for i := 0; i < len(data); i++ {
   272  			data[i] = len(data) - i
   273  		}
   274  		b.StartTimer()
   275  		Ints(data)
   276  		b.StopTimer()
   277  	}
   278  }
   279  
   280  func BenchmarkSortInt1K_Mod8(b *testing.B) {
   281  	b.StopTimer()
   282  	for i := 0; i < b.N; i++ {
   283  		data := make([]int, 1<<10)
   284  		for i := 0; i < len(data); i++ {
   285  			data[i] = i % 8
   286  		}
   287  		b.StartTimer()
   288  		Ints(data)
   289  		b.StopTimer()
   290  	}
   291  }
   292  
   293  func BenchmarkStableInt1K(b *testing.B) {
   294  	b.StopTimer()
   295  	unsorted := make([]int, 1<<10)
   296  	for i := range unsorted {
   297  		unsorted[i] = i ^ 0x2cc
   298  	}
   299  	data := make([]int, len(unsorted))
   300  	for i := 0; i < b.N; i++ {
   301  		copy(data, unsorted)
   302  		b.StartTimer()
   303  		Stable(IntSlice(data))
   304  		b.StopTimer()
   305  	}
   306  }
   307  
   308  func BenchmarkStableInt1K_Slice(b *testing.B) {
   309  	b.StopTimer()
   310  	unsorted := make([]int, 1<<10)
   311  	for i := range unsorted {
   312  		unsorted[i] = i ^ 0x2cc
   313  	}
   314  	data := make([]int, len(unsorted))
   315  	for i := 0; i < b.N; i++ {
   316  		copy(data, unsorted)
   317  		b.StartTimer()
   318  		SliceStable(data, func(i, j int) bool { return data[i] < data[j] })
   319  		b.StopTimer()
   320  	}
   321  }
   322  
   323  func BenchmarkSortInt64K(b *testing.B) {
   324  	b.StopTimer()
   325  	for i := 0; i < b.N; i++ {
   326  		data := make([]int, 1<<16)
   327  		for i := 0; i < len(data); i++ {
   328  			data[i] = i ^ 0xcccc
   329  		}
   330  		b.StartTimer()
   331  		Ints(data)
   332  		b.StopTimer()
   333  	}
   334  }
   335  
   336  func BenchmarkSortInt64K_Slice(b *testing.B) {
   337  	b.StopTimer()
   338  	for i := 0; i < b.N; i++ {
   339  		data := make([]int, 1<<16)
   340  		for i := 0; i < len(data); i++ {
   341  			data[i] = i ^ 0xcccc
   342  		}
   343  		b.StartTimer()
   344  		Slice(data, func(i, j int) bool { return data[i] < data[j] })
   345  		b.StopTimer()
   346  	}
   347  }
   348  
   349  func BenchmarkStableInt64K(b *testing.B) {
   350  	b.StopTimer()
   351  	for i := 0; i < b.N; i++ {
   352  		data := make([]int, 1<<16)
   353  		for i := 0; i < len(data); i++ {
   354  			data[i] = i ^ 0xcccc
   355  		}
   356  		b.StartTimer()
   357  		Stable(IntSlice(data))
   358  		b.StopTimer()
   359  	}
   360  }
   361  
   362  const (
   363  	_Sawtooth = iota
   364  	_Rand
   365  	_Stagger
   366  	_Plateau
   367  	_Shuffle
   368  	_NDist
   369  )
   370  
   371  const (
   372  	_Copy = iota
   373  	_Reverse
   374  	_ReverseFirstHalf
   375  	_ReverseSecondHalf
   376  	_Sorted
   377  	_Dither
   378  	_NMode
   379  )
   380  
   381  type testingData struct {
   382  	desc        string
   383  	t           *testing.T
   384  	data        []int
   385  	maxswap     int // number of swaps allowed
   386  	ncmp, nswap int
   387  }
   388  
   389  func (d *testingData) Len() int { return len(d.data) }
   390  func (d *testingData) Less(i, j int) bool {
   391  	d.ncmp++
   392  	return d.data[i] < d.data[j]
   393  }
   394  func (d *testingData) Swap(i, j int) {
   395  	if d.nswap >= d.maxswap {
   396  		d.t.Fatalf("%s: used %d swaps sorting slice of %d", d.desc, d.nswap, len(d.data))
   397  	}
   398  	d.nswap++
   399  	d.data[i], d.data[j] = d.data[j], d.data[i]
   400  }
   401  
   402  func min(a, b int) int {
   403  	if a < b {
   404  		return a
   405  	}
   406  	return b
   407  }
   408  
   409  func lg(n int) int {
   410  	i := 0
   411  	for 1<<uint(i) < n {
   412  		i++
   413  	}
   414  	return i
   415  }
   416  
   417  func testBentleyMcIlroy(t *testing.T, sort func(Interface), maxswap func(int) int) {
   418  	sizes := []int{100, 1023, 1024, 1025}
   419  	if testing.Short() {
   420  		sizes = []int{100, 127, 128, 129}
   421  	}
   422  	dists := []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"}
   423  	modes := []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"}
   424  	var tmp1, tmp2 [1025]int
   425  	for _, n := range sizes {
   426  		for m := 1; m < 2*n; m *= 2 {
   427  			for dist := 0; dist < _NDist; dist++ {
   428  				j := 0
   429  				k := 1
   430  				data := tmp1[0:n]
   431  				for i := 0; i < n; i++ {
   432  					switch dist {
   433  					case _Sawtooth:
   434  						data[i] = i % m
   435  					case _Rand:
   436  						data[i] = rand.Intn(m)
   437  					case _Stagger:
   438  						data[i] = (i*m + i) % n
   439  					case _Plateau:
   440  						data[i] = min(i, m)
   441  					case _Shuffle:
   442  						if rand.Intn(m) != 0 {
   443  							j += 2
   444  							data[i] = j
   445  						} else {
   446  							k += 2
   447  							data[i] = k
   448  						}
   449  					}
   450  				}
   451  
   452  				mdata := tmp2[0:n]
   453  				for mode := 0; mode < _NMode; mode++ {
   454  					switch mode {
   455  					case _Copy:
   456  						for i := 0; i < n; i++ {
   457  							mdata[i] = data[i]
   458  						}
   459  					case _Reverse:
   460  						for i := 0; i < n; i++ {
   461  							mdata[i] = data[n-i-1]
   462  						}
   463  					case _ReverseFirstHalf:
   464  						for i := 0; i < n/2; i++ {
   465  							mdata[i] = data[n/2-i-1]
   466  						}
   467  						for i := n / 2; i < n; i++ {
   468  							mdata[i] = data[i]
   469  						}
   470  					case _ReverseSecondHalf:
   471  						for i := 0; i < n/2; i++ {
   472  							mdata[i] = data[i]
   473  						}
   474  						for i := n / 2; i < n; i++ {
   475  							mdata[i] = data[n-(i-n/2)-1]
   476  						}
   477  					case _Sorted:
   478  						for i := 0; i < n; i++ {
   479  							mdata[i] = data[i]
   480  						}
   481  						// Ints is known to be correct
   482  						// because mode Sort runs after mode _Copy.
   483  						Ints(mdata)
   484  					case _Dither:
   485  						for i := 0; i < n; i++ {
   486  							mdata[i] = data[i] + i%5
   487  						}
   488  					}
   489  
   490  					desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode])
   491  					d := &testingData{desc: desc, t: t, data: mdata[0:n], maxswap: maxswap(n)}
   492  					sort(d)
   493  					// Uncomment if you are trying to improve the number of compares/swaps.
   494  					//t.Logf("%s: ncmp=%d, nswp=%d", desc, d.ncmp, d.nswap)
   495  
   496  					// If we were testing C qsort, we'd have to make a copy
   497  					// of the slice and sort it ourselves and then compare
   498  					// x against it, to ensure that qsort was only permuting
   499  					// the data, not (for example) overwriting it with zeros.
   500  					//
   501  					// In go, we don't have to be so paranoid: since the only
   502  					// mutating method Sort can call is TestingData.swap,
   503  					// it suffices here just to check that the final slice is sorted.
   504  					if !IntsAreSorted(mdata) {
   505  						t.Fatalf("%s: ints not sorted\n\t%v", desc, mdata)
   506  					}
   507  				}
   508  			}
   509  		}
   510  	}
   511  }
   512  
   513  func TestSortBM(t *testing.T) {
   514  	testBentleyMcIlroy(t, Sort, func(n int) int { return n * lg(n) * 12 / 10 })
   515  }
   516  
   517  func TestHeapsortBM(t *testing.T) {
   518  	testBentleyMcIlroy(t, Heapsort, func(n int) int { return n * lg(n) * 12 / 10 })
   519  }
   520  
   521  func TestStableBM(t *testing.T) {
   522  	testBentleyMcIlroy(t, Stable, func(n int) int { return n * lg(n) * lg(n) / 3 })
   523  }
   524  
   525  // This is based on the "antiquicksort" implementation by M. Douglas McIlroy.
   526  // See https://www.cs.dartmouth.edu/~doug/mdmspe.pdf for more info.
   527  type adversaryTestingData struct {
   528  	t         *testing.T
   529  	data      []int // item values, initialized to special gas value and changed by Less
   530  	maxcmp    int   // number of comparisons allowed
   531  	ncmp      int   // number of comparisons (calls to Less)
   532  	nsolid    int   // number of elements that have been set to non-gas values
   533  	candidate int   // guess at current pivot
   534  	gas       int   // special value for unset elements, higher than everything else
   535  }
   536  
   537  func (d *adversaryTestingData) Len() int { return len(d.data) }
   538  
   539  func (d *adversaryTestingData) Less(i, j int) bool {
   540  	if d.ncmp >= d.maxcmp {
   541  		d.t.Fatalf("used %d comparisons sorting adversary data with size %d", d.ncmp, len(d.data))
   542  	}
   543  	d.ncmp++
   544  
   545  	if d.data[i] == d.gas && d.data[j] == d.gas {
   546  		if i == d.candidate {
   547  			// freeze i
   548  			d.data[i] = d.nsolid
   549  			d.nsolid++
   550  		} else {
   551  			// freeze j
   552  			d.data[j] = d.nsolid
   553  			d.nsolid++
   554  		}
   555  	}
   556  
   557  	if d.data[i] == d.gas {
   558  		d.candidate = i
   559  	} else if d.data[j] == d.gas {
   560  		d.candidate = j
   561  	}
   562  
   563  	return d.data[i] < d.data[j]
   564  }
   565  
   566  func (d *adversaryTestingData) Swap(i, j int) {
   567  	d.data[i], d.data[j] = d.data[j], d.data[i]
   568  }
   569  
   570  func newAdversaryTestingData(t *testing.T, size int, maxcmp int) *adversaryTestingData {
   571  	gas := size - 1
   572  	data := make([]int, size)
   573  	for i := 0; i < size; i++ {
   574  		data[i] = gas
   575  	}
   576  	return &adversaryTestingData{t: t, data: data, maxcmp: maxcmp, gas: gas}
   577  }
   578  
   579  func TestAdversary(t *testing.T) {
   580  	const size = 10000            // large enough to distinguish between O(n^2) and O(n*log(n))
   581  	maxcmp := size * lg(size) * 4 // the factor 4 was found by trial and error
   582  	d := newAdversaryTestingData(t, size, maxcmp)
   583  	Sort(d) // This should degenerate to heapsort.
   584  	// Check data is fully populated and sorted.
   585  	for i, v := range d.data {
   586  		if v != i {
   587  			t.Fatalf("adversary data not fully sorted")
   588  		}
   589  	}
   590  }
   591  
   592  func TestStableInts(t *testing.T) {
   593  	data := ints
   594  	Stable(IntSlice(data[0:]))
   595  	if !IntsAreSorted(data[0:]) {
   596  		t.Errorf("nsorted %v\n   got %v", ints, data)
   597  	}
   598  }
   599  
   600  type intPairs []struct {
   601  	a, b int
   602  }
   603  
   604  // IntPairs compare on a only.
   605  func (d intPairs) Len() int           { return len(d) }
   606  func (d intPairs) Less(i, j int) bool { return d[i].a < d[j].a }
   607  func (d intPairs) Swap(i, j int)      { d[i], d[j] = d[j], d[i] }
   608  
   609  // Record initial order in B.
   610  func (d intPairs) initB() {
   611  	for i := range d {
   612  		d[i].b = i
   613  	}
   614  }
   615  
   616  // InOrder checks if a-equal elements were not reordered.
   617  func (d intPairs) inOrder() bool {
   618  	lastA, lastB := -1, 0
   619  	for i := 0; i < len(d); i++ {
   620  		if lastA != d[i].a {
   621  			lastA = d[i].a
   622  			lastB = d[i].b
   623  			continue
   624  		}
   625  		if d[i].b <= lastB {
   626  			return false
   627  		}
   628  		lastB = d[i].b
   629  	}
   630  	return true
   631  }
   632  
   633  func TestStability(t *testing.T) {
   634  	n, m := 100000, 1000
   635  	if testing.Short() {
   636  		n, m = 1000, 100
   637  	}
   638  	data := make(intPairs, n)
   639  
   640  	// random distribution
   641  	for i := 0; i < len(data); i++ {
   642  		data[i].a = rand.Intn(m)
   643  	}
   644  	if IsSorted(data) {
   645  		t.Fatalf("terrible rand.rand")
   646  	}
   647  	data.initB()
   648  	Stable(data)
   649  	if !IsSorted(data) {
   650  		t.Errorf("Stable didn't sort %d ints", n)
   651  	}
   652  	if !data.inOrder() {
   653  		t.Errorf("Stable wasn't stable on %d ints", n)
   654  	}
   655  
   656  	// already sorted
   657  	data.initB()
   658  	Stable(data)
   659  	if !IsSorted(data) {
   660  		t.Errorf("Stable shuffled sorted %d ints (order)", n)
   661  	}
   662  	if !data.inOrder() {
   663  		t.Errorf("Stable shuffled sorted %d ints (stability)", n)
   664  	}
   665  
   666  	// sorted reversed
   667  	for i := 0; i < len(data); i++ {
   668  		data[i].a = len(data) - i
   669  	}
   670  	data.initB()
   671  	Stable(data)
   672  	if !IsSorted(data) {
   673  		t.Errorf("Stable didn't sort %d ints", n)
   674  	}
   675  	if !data.inOrder() {
   676  		t.Errorf("Stable wasn't stable on %d ints", n)
   677  	}
   678  }
   679  
   680  var countOpsSizes = []int{1e2, 3e2, 1e3, 3e3, 1e4, 3e4, 1e5, 3e5, 1e6}
   681  
   682  func countOps(t *testing.T, algo func(Interface), name string) {
   683  	sizes := countOpsSizes
   684  	if testing.Short() {
   685  		sizes = sizes[:5]
   686  	}
   687  	if !testing.Verbose() {
   688  		t.Skip("Counting skipped as non-verbose mode.")
   689  	}
   690  	for _, n := range sizes {
   691  		td := testingData{
   692  			desc:    name,
   693  			t:       t,
   694  			data:    make([]int, n),
   695  			maxswap: 1<<31 - 1,
   696  		}
   697  		for i := 0; i < n; i++ {
   698  			td.data[i] = rand.Intn(n / 5)
   699  		}
   700  		algo(&td)
   701  		t.Logf("%s %8d elements: %11d Swap, %10d Less", name, n, td.nswap, td.ncmp)
   702  	}
   703  }
   704  
   705  func TestCountStableOps(t *testing.T) { countOps(t, Stable, "Stable") }
   706  func TestCountSortOps(t *testing.T)   { countOps(t, Sort, "Sort  ") }
   707  
   708  func bench(b *testing.B, size int, algo func(Interface), name string) {
   709  	if stringspkg.HasSuffix(testenv.Builder(), "-race") && size > 1e4 {
   710  		b.Skip("skipping slow benchmark on race builder")
   711  	}
   712  	b.StopTimer()
   713  	data := make(intPairs, size)
   714  	x := ^uint32(0)
   715  	for i := 0; i < b.N; i++ {
   716  		for n := size - 3; n <= size+3; n++ {
   717  			for i := 0; i < len(data); i++ {
   718  				x += x
   719  				x ^= 1
   720  				if int32(x) < 0 {
   721  					x ^= 0x88888eef
   722  				}
   723  				data[i].a = int(x % uint32(n/5))
   724  			}
   725  			data.initB()
   726  			b.StartTimer()
   727  			algo(data)
   728  			b.StopTimer()
   729  			if !IsSorted(data) {
   730  				b.Errorf("%s did not sort %d ints", name, n)
   731  			}
   732  			if name == "Stable" && !data.inOrder() {
   733  				b.Errorf("%s unstable on %d ints", name, n)
   734  			}
   735  		}
   736  	}
   737  }
   738  
   739  func BenchmarkSort1e2(b *testing.B)   { bench(b, 1e2, Sort, "Sort") }
   740  func BenchmarkStable1e2(b *testing.B) { bench(b, 1e2, Stable, "Stable") }
   741  func BenchmarkSort1e4(b *testing.B)   { bench(b, 1e4, Sort, "Sort") }
   742  func BenchmarkStable1e4(b *testing.B) { bench(b, 1e4, Stable, "Stable") }
   743  func BenchmarkSort1e6(b *testing.B)   { bench(b, 1e6, Sort, "Sort") }
   744  func BenchmarkStable1e6(b *testing.B) { bench(b, 1e6, Stable, "Stable") }
   745  

View as plain text