libgo/go/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
   6
   7 import (
   8         "fmt"
   9         "rand"
  10         "strconv"
  11         "testing"
  12 )
  13
  14
  15 var ints = [...]int{74, 59, 238, -784, 9845, 959, 905, 0, 0, 42, 7586, -5467984, 7586}
  16 var float64s = [...]float64{74.3, 59.0, 238.2, -784.0, 2.3, 9845.768, -959.7485, 905, 7.8, 7.8}
  17 var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}
  18
  19 func TestSortIntArray(t *testing.T) {
  20         data := ints
  21         a := IntArray(data[0:])
  22         Sort(a)
  23         if !IsSorted(a) {
  24                 t.Errorf("sorted %v", ints)
  25                 t.Errorf("   got %v", data)
  26         }
  27 }
  28
  29 func TestSortFloat64Array(t *testing.T) {
  30         data := float64s
  31         a := Float64Array(data[0:])
  32         Sort(a)
  33         if !IsSorted(a) {
  34                 t.Errorf("sorted %v", float64s)
  35                 t.Errorf("   got %v", data)
  36         }
  37 }
  38
  39 func TestSortStringArray(t *testing.T) {
  40         data := strings
  41         a := StringArray(data[0:])
  42         Sort(a)
  43         if !IsSorted(a) {
  44                 t.Errorf("sorted %v", strings)
  45                 t.Errorf("   got %v", data)
  46         }
  47 }
  48
  49 func TestSortInts(t *testing.T) {
  50         data := ints
  51         SortInts(data[0:])
  52         if !IntsAreSorted(data[0:]) {
  53                 t.Errorf("sorted %v", ints)
  54                 t.Errorf("   got %v", data)
  55         }
  56 }
  57
  58 func TestSortFloat64s(t *testing.T) {
  59         data := float64s
  60         SortFloat64s(data[0:])
  61         if !Float64sAreSorted(data[0:]) {
  62                 t.Errorf("sorted %v", float64s)
  63                 t.Errorf("   got %v", data)
  64         }
  65 }
  66
  67 func TestSortStrings(t *testing.T) {
  68         data := strings
  69         SortStrings(data[0:])
  70         if !StringsAreSorted(data[0:]) {
  71                 t.Errorf("sorted %v", strings)
  72                 t.Errorf("   got %v", data)
  73         }
  74 }
  75
  76 func TestSortLarge_Random(t *testing.T) {
  77         data := make([]int, 1000000)
  78         for i := 0; i < len(data); i++ {
  79                 data[i] = rand.Intn(100)
  80         }
  81         if IntsAreSorted(data) {
  82                 t.Fatalf("terrible rand.rand")
  83         }
  84         SortInts(data)
  85         if !IntsAreSorted(data) {
  86                 t.Errorf("sort didn't sort - 1M ints")
  87         }
  88 }
  89
  90 func BenchmarkSortString1K(b *testing.B) {
  91         b.StopTimer()
  92         for i := 0; i < b.N; i++ {
  93                 data := make([]string, 1<<10)
  94                 for i := 0; i < len(data); i++ {
  95                         data[i] = strconv.Itoa(i ^ 0x2cc)
  96                 }
  97                 b.StartTimer()
  98                 SortStrings(data)
  99                 b.StopTimer()
 100         }
 101 }
 102
 103 func BenchmarkSortInt1K(b *testing.B) {
 104         b.StopTimer()
 105         for i := 0; i < b.N; i++ {
 106                 data := make([]int, 1<<10)
 107                 for i := 0; i < len(data); i++ {
 108                         data[i] = i ^ 0x2cc
 109                 }
 110                 b.StartTimer()
 111                 SortInts(data)
 112                 b.StopTimer()
 113         }
 114 }
 115
 116 func BenchmarkSortInt64K(b *testing.B) {
 117         b.StopTimer()
 118         for i := 0; i < b.N; i++ {
 119                 data := make([]int, 1<<16)
 120                 for i := 0; i < len(data); i++ {
 121                         data[i] = i ^ 0xcccc
 122                 }
 123                 b.StartTimer()
 124                 SortInts(data)
 125                 b.StopTimer()
 126         }
 127 }
 128
 129 const (
 130         _Sawtooth = iota
 131         _Rand
 132         _Stagger
 133         _Plateau
 134         _Shuffle
 135         _NDist
 136 )
 137
 138 const (
 139         _Copy = iota
 140         _Reverse
 141         _ReverseFirstHalf
 142         _ReverseSecondHalf
 143         _Sorted
 144         _Dither
 145         _NMode
 146 )
 147
 148 type testingData struct {
 149         desc    string
 150         t       *testing.T
 151         data    []int
 152         maxswap int // number of swaps allowed
 153         nswap   int
 154 }
 155
 156 func (d *testingData) Len() int           { return len(d.data) }
 157 func (d *testingData) Less(i, j int) bool { return d.data[i] < d.data[j] }
 158 func (d *testingData) Swap(i, j int) {
 159         if d.nswap >= d.maxswap {
 160                 d.t.Errorf("%s: used %d swaps sorting array of %d", d.desc, d.nswap, len(d.data))
 161                 d.t.FailNow()
 162         }
 163         d.nswap++
 164         d.data[i], d.data[j] = d.data[j], d.data[i]
 165 }
 166
 167 func lg(n int) int {
 168         i := 0
 169         for 1<<uint(i) < n {
 170                 i++
 171         }
 172         return i
 173 }
 174
 175 func TestBentleyMcIlroy(t *testing.T) {
 176         sizes := []int{100, 1023, 1024, 1025}
 177         dists := []string{"sawtooth", "rand", "stagger", "plateau", "shuffle"}
 178         modes := []string{"copy", "reverse", "reverse1", "reverse2", "sort", "dither"}
 179         var tmp1, tmp2 [1025]int
 180         for ni := 0; ni < len(sizes); ni++ {
 181                 n := sizes[ni]
 182                 for m := 1; m < 2*n; m *= 2 {
 183                         for dist := 0; dist < _NDist; dist++ {
 184                                 j := 0
 185                                 k := 1
 186                                 data := tmp1[0:n]
 187                                 for i := 0; i < n; i++ {
 188                                         switch dist {
 189                                         case _Sawtooth:
 190                                                 data[i] = i % m
 191                                         case _Rand:
 192                                                 data[i] = rand.Intn(m)
 193                                         case _Stagger:
 194                                                 data[i] = (i*m + i) % n
 195                                         case _Plateau:
 196                                                 data[i] = min(i, m)
 197                                         case _Shuffle:
 198                                                 if rand.Intn(m) != 0 {
 199                                                         j += 2
 200                                                         data[i] = j
 201                                                 } else {
 202                                                         k += 2
 203                                                         data[i] = k
 204                                                 }
 205                                         }
 206                                 }
 207
 208                                 mdata := tmp2[0:n]
 209                                 for mode := 0; mode < _NMode; mode++ {
 210                                         switch mode {
 211                                         case _Copy:
 212                                                 for i := 0; i < n; i++ {
 213                                                         mdata[i] = data[i]
 214                                                 }
 215                                         case _Reverse:
 216                                                 for i := 0; i < n; i++ {
 217                                                         mdata[i] = data[n-i-1]
 218                                                 }
 219                                         case _ReverseFirstHalf:
 220                                                 for i := 0; i < n/2; i++ {
 221                                                         mdata[i] = data[n/2-i-1]
 222                                                 }
 223                                                 for i := n / 2; i < n; i++ {
 224                                                         mdata[i] = data[i]
 225                                                 }
 226                                         case _ReverseSecondHalf:
 227                                                 for i := 0; i < n/2; i++ {
 228                                                         mdata[i] = data[i]
 229                                                 }
 230                                                 for i := n / 2; i < n; i++ {
 231                                                         mdata[i] = data[n-(i-n/2)-1]
 232                                                 }
 233                                         case _Sorted:
 234                                                 for i := 0; i < n; i++ {
 235                                                         mdata[i] = data[i]
 236                                                 }
 237                                                 // SortInts is known to be correct
 238                                                 // because mode Sort runs after mode _Copy.
 239                                                 SortInts(mdata)
 240                                         case _Dither:
 241                                                 for i := 0; i < n; i++ {
 242                                                         mdata[i] = data[i] + i%5
 243                                                 }
 244                                         }
 245
 246                                         desc := fmt.Sprintf("n=%d m=%d dist=%s mode=%s", n, m, dists[dist], modes[mode])
 247                                         d := &testingData{desc, t, mdata[0:n], n * lg(n) * 12 / 10, 0}
 248                                         Sort(d)
 249
 250                                         // If we were testing C qsort, we'd have to make a copy
 251                                         // of the array and sort it ourselves and then compare
 252                                         // x against it, to ensure that qsort was only permuting
 253                                         // the data, not (for example) overwriting it with zeros.
 254                                         //
 255                                         // In go, we don't have to be so paranoid: since the only
 256                                         // mutating method Sort can call is TestingData.swap,
 257                                         // it suffices here just to check that the final array is sorted.
 258                                         if !IntsAreSorted(mdata) {
 259                                                 t.Errorf("%s: ints not sorted", desc)
 260                                                 t.Errorf("\t%v", mdata)
 261                                                 t.FailNow()
 262                                         }
 263                                 }
 264                         }
 265                 }
 266         }
 267 }