Source file src/sort/sort_test.go

Documentation: sort

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

View as plain text