Source file src/pkg/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 // Sort sorts data. 187 // It makes one call to data.Len to determine n, and O(n*log(n)) calls to 188 // data.Less and data.Swap. The sort is not guaranteed to be stable. 189 func Sort(data Interface) { 190 // Switch to heapsort if depth of 2*ceil(lg(n+1)) is reached. 191 n := data.Len() 192 maxDepth := 0 193 for i := n; i > 0; i >>= 1 { 194 maxDepth++ 195 } 196 maxDepth *= 2 197 quickSort(data, 0, n, maxDepth) 198 } 199 200 // IsSorted reports whether data is sorted. 201 func IsSorted(data Interface) bool { 202 n := data.Len() 203 for i := n - 1; i > 0; i-- { 204 if data.Less(i, i-1) { 205 return false 206 } 207 } 208 return true 209 } 210 211 // Convenience types for common cases 212 213 // IntSlice attaches the methods of Interface to []int, sorting in increasing order. 214 type IntSlice []int 215 216 func (p IntSlice) Len() int { return len(p) } 217 func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] } 218 func (p IntSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 219 220 // Sort is a convenience method. 221 func (p IntSlice) Sort() { Sort(p) } 222 223 // Float64Slice attaches the methods of Interface to []float64, sorting in increasing order. 224 type Float64Slice []float64 225 226 func (p Float64Slice) Len() int { return len(p) } 227 func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || math.IsNaN(p[i]) && !math.IsNaN(p[j]) } 228 func (p Float64Slice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 229 230 // Sort is a convenience method. 231 func (p Float64Slice) Sort() { Sort(p) } 232 233 // StringSlice attaches the methods of Interface to []string, sorting in increasing order. 234 type StringSlice []string 235 236 func (p StringSlice) Len() int { return len(p) } 237 func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] } 238 func (p StringSlice) Swap(i, j int) { p[i], p[j] = p[j], p[i] } 239 240 // Sort is a convenience method. 241 func (p StringSlice) Sort() { Sort(p) } 242 243 // Convenience wrappers for common cases 244 245 // Ints sorts a slice of ints in increasing order. 246 func Ints(a []int) { Sort(IntSlice(a)) } 247 248 // Float64s sorts a slice of float64s in increasing order. 249 func Float64s(a []float64) { Sort(Float64Slice(a)) } 250 251 // Strings sorts a slice of strings in increasing order. 252 func Strings(a []string) { Sort(StringSlice(a)) } 253 254 // IntsAreSorted tests whether a slice of ints is sorted in increasing order. 255 func IntsAreSorted(a []int) bool { return IsSorted(IntSlice(a)) } 256 257 // Float64sAreSorted tests whether a slice of float64s is sorted in increasing order. 258 func Float64sAreSorted(a []float64) bool { return IsSorted(Float64Slice(a)) } 259 260 // StringsAreSorted tests whether a slice of strings is sorted in increasing order. 261 func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }