libgo/go/sort/sort.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 provides primitives for sorting slices and user-defined
   6 // collections.
   7 package sort
   8
   9 import "math"
  10
  11 // A type, typically a collection, that satisfies sort.Interface can be
  12 // sorted by the routines in this package.  The methods require that the
  13 // elements of the collection be enumerated by an integer index.
  14 type Interface interface {
  15         // Len is the number of elements in the collection.
  16         Len() int
  17         // Less returns whether the element with index i should sort
  18         // before the element with index j.
  19         Less(i, j int) bool
  20         // Swap swaps the elements with indexes i and j.
  21         Swap(i, j int)
  22 }
  23
  24 func min(a, b int) int {
  25         if a < b {
  26                 return a
  27         }
  28         return b
  29 }
  30
  31 // Insertion sort
  32 func insertionSort(data Interface, a, b int) {
  33         for i := a + 1; i < b; i++ {
  34                 for j := i; j > a && data.Less(j, j-1); j-- {
  35                         data.Swap(j, j-1)
  36                 }
  37         }
  38 }
  39
  40 // siftDown implements the heap property on data[lo, hi).
  41 // first is an offset into the array where the root of the heap lies.
  42 func siftDown(data Interface, lo, hi, first int) {
  43         root := lo
  44         for {
  45                 child := 2*root + 1
  46                 if child >= hi {
  47                         break
  48                 }
  49                 if child+1 < hi && data.Less(first+child, first+child+1) {
  50                         child++
  51                 }
  52                 if !data.Less(first+root, first+child) {
  53                         return
  54                 }
  55                 data.Swap(first+root, first+child)
  56                 root = child
  57         }
  58 }
  59
  60 func heapSort(data Interface, a, b int) {
  61         first := a
  62         lo := 0
  63         hi := b - a
  64
  65         // Build heap with greatest element at top.
  66         for i := (hi - 1) / 2; i >= 0; i-- {
  67                 siftDown(data, i, hi, first)
  68         }
  69
  70         // Pop elements, largest first, into end of data.
  71         for i := hi - 1; i >= 0; i-- {
  72                 data.Swap(first, first+i)
  73                 siftDown(data, lo, i, first)
  74         }
  75 }
  76
  77 // Quicksort, following Bentley and McIlroy,
  78 // ``Engineering a Sort Function,'' SP&E November 1993.
  79
  80 // medianOfThree moves the median of the three values data[a], data[b], data[c] into data[a].
  81 func medianOfThree(data Interface, a, b, c int) {
  82         m0 := b
  83         m1 := a
  84         m2 := c
  85         // bubble sort on 3 elements
  86         if data.Less(m1, m0) {
  87                 data.Swap(m1, m0)
  88         }
  89         if data.Less(m2, m1) {
  90                 data.Swap(m2, m1)
  91         }
  92         if data.Less(m1, m0) {
  93                 data.Swap(m1, m0)
  94         }
  95         // now data[m0] <= data[m1] <= data[m2]
  96 }
  97
  98 func swapRange(data Interface, a, b, n int) {
  99         for i := 0; i < n; i++ {
 100                 data.Swap(a+i, b+i)
 101         }
 102 }
 103
 104 func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
 105         m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
 106         if hi-lo > 40 {
 107                 // Tukey's ``Ninther,'' median of three medians of three.
 108                 s := (hi - lo) / 8
 109                 medianOfThree(data, lo, lo+s, lo+2*s)
 110                 medianOfThree(data, m, m-s, m+s)
 111                 medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
 112         }
 113         medianOfThree(data, lo, m, hi-1)
 114
 115         // Invariants are:
 116         //      data[lo] = pivot (set up by ChoosePivot)
 117         //      data[lo <= i < a] = pivot
 118         //      data[a <= i < b] < pivot
 119         //      data[b <= i < c] is unexamined
 120         //      data[c <= i < d] > pivot
 121         //      data[d <= i < hi] = pivot
 122         //
 123         // Once b meets c, can swap the "= pivot" sections
 124         // into the middle of the slice.
 125         pivot := lo
 126         a, b, c, d := lo+1, lo+1, hi, hi
 127         for b < c {
 128                 if data.Less(b, pivot) { // data[b] < pivot
 129                         b++
 130                         continue
 131                 }
 132                 if !data.Less(pivot, b) { // data[b] = pivot
 133                         data.Swap(a, b)
 134                         a++
 135                         b++
 136                         continue
 137                 }
 138                 if data.Less(pivot, c-1) { // data[c-1] > pivot
 139                         c--
 140                         continue
 141                 }
 142                 if !data.Less(c-1, pivot) { // data[c-1] = pivot
 143                         data.Swap(c-1, d-1)
 144                         c--
 145                         d--
 146                         continue
 147                 }
 148                 // data[b] > pivot; data[c-1] < pivot
 149                 data.Swap(b, c-1)
 150                 b++
 151                 c--
 152         }
 153
 154         n := min(b-a, a-lo)
 155         swapRange(data, lo, b-n, n)
 156
 157         n = min(hi-d, d-c)
 158         swapRange(data, c, hi-n, n)
 159
 160         return lo + b - a, hi - (d - c)
 161 }
 162
 163 func quickSort(data Interface, a, b, maxDepth int) {
 164         for b-a > 7 {
 165                 if maxDepth == 0 {
 166                         heapSort(data, a, b)
 167                         return
 168                 }
 169                 maxDepth--
 170                 mlo, mhi := doPivot(data, a, b)
 171                 // Avoiding recursion on the larger subproblem guarantees
 172                 // a stack depth of at most lg(b-a).
 173                 if mlo-a < b-mhi {
 174                         quickSort(data, a, mlo, maxDepth)
 175                         a = mhi // i.e., quickSort(data, mhi, b)
 176                 } else {
 177                         quickSort(data, mhi, b, maxDepth)
 178                         b = mlo // i.e., quickSort(data, a, mlo)
 179                 }
 180         }
 181         if b-a > 1 {
 182                 insertionSort(data, a, b)
 183         }
 184 }
 185
 186 func Sort(data Interface) {
 187         // Switch to heapsort if depth of 2*ceil(lg(n)) is reached.
 188         n := data.Len()
 189         maxDepth := 0
 190         for 1<<uint(maxDepth) < n {
 191                 maxDepth++
 192         }
 193         maxDepth *= 2
 194         quickSort(data, 0, data.Len(), maxDepth)
 195 }
 196
 197 func IsSorted(data Interface) bool {
 198         n := data.Len()
 199         for i := n - 1; i > 0; i-- {
 200                 if data.Less(i, i-1) {
 201                         return false
 202                 }
 203         }
 204         return true
 205 }
 206
 207 // Convenience types for common cases
 208
 209 // IntSlice attaches the methods of Interface to []int, sorting in increasing order.
 210 type IntSlice []int
 211
 212 func (p IntSlice) Len() int           { return len(p) }
 213 func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
 214 func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
 215
 216 // Sort is a convenience method.
 217 func (p IntSlice) Sort() { Sort(p) }
 218
 219 // Float64Slice attaches the methods of Interface to []float64, sorting in increasing order.
 220 type Float64Slice []float64
 221
 222 func (p Float64Slice) Len() int           { return len(p) }
 223 func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || math.IsNaN(p[i]) && !math.IsNaN(p[j]) }
 224 func (p Float64Slice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
 225
 226 // Sort is a convenience method.
 227 func (p Float64Slice) Sort() { Sort(p) }
 228
 229 // StringSlice attaches the methods of Interface to []string, sorting in increasing order.
 230 type StringSlice []string
 231
 232 func (p StringSlice) Len() int           { return len(p) }
 233 func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
 234 func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
 235
 236 // Sort is a convenience method.
 237 func (p StringSlice) Sort() { Sort(p) }
 238
 239 // Convenience wrappers for common cases
 240
 241 // Ints sorts a slice of ints in increasing order.
 242 func Ints(a []int) { Sort(IntSlice(a)) }
 243
 244 // Float64s sorts a slice of float64s in increasing order.
 245 func Float64s(a []float64) { Sort(Float64Slice(a)) }
 246
 247 // Strings sorts a slice of strings in increasing order.
 248 func Strings(a []string) { Sort(StringSlice(a)) }
 249
 250 // IntsAreSorted tests whether a slice of ints is sorted in increasing order.
 251 func IntsAreSorted(a []int) bool { return IsSorted(IntSlice(a)) }
 252
 253 // Float64sAreSorted tests whether a slice of float64s is sorted in increasing order.
 254 func Float64sAreSorted(a []float64) bool { return IsSorted(Float64Slice(a)) }
 255
 256 // StringsAreSorted tests whether a slice of strings is sorted in increasing order.
 257 func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }