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.
5 // Package sort provides primitives for sorting slices and user-defined
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.
17 // Less returns whether the element with index i should sort
18 // before the element with index j.
20 // Swap swaps the elements with indexes i and j.
24 func min(a
, b
int) int {
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
-- {
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) {
49 if child
+1 < hi
&& data
.Less(first
+child
, first
+child
+1) {
52 if !data
.Less(first
+root
, first
+child
) {
55 data
.Swap(first
+root
, first
+child
)
60 func heapSort(data Interface
, a
, b
int) {
65 // Build heap with greatest element at top.
66 for i
:= (hi
- 1) / 2; i
>= 0; i
-- {
67 siftDown(data
, i
, hi
, first
)
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
)
77 // Quicksort, following Bentley and McIlroy,
78 // ``Engineering a Sort Function,'' SP&E November 1993.
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) {
85 // bubble sort on 3 elements
86 if data
.Less(m1
, m0
) {
89 if data
.Less(m2
, m1
) {
92 if data
.Less(m1
, m0
) {
95 // now data[m0] <= data[m1] <= data[m2]
98 func swapRange(data Interface
, a
, b
, n
int) {
99 for i
:= 0; i
< n
; i
++ {
104 func doPivot(data Interface
, lo
, hi
int) (midlo
, midhi
int) {
105 m
:= lo
+ (hi
-lo
)/2 // Written like this to avoid integer overflow.
107 // Tukey's ``Ninther,'' median of three medians of three.
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
)
113 medianOfThree(data
, lo
, m
, hi
-1)
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
123 // Once b meets c, can swap the "= pivot" sections
124 // into the middle of the slice.
126 a
, b
, c
, d
:= lo
+1, lo
+1, hi
, hi
128 if data
.Less(b
, pivot
) { // data[b] < pivot
132 if !data
.Less(pivot
, b
) { // data[b] = pivot
138 if data
.Less(pivot
, c
-1) { // data[c-1] > pivot
142 if !data
.Less(c
-1, pivot
) { // data[c-1] = pivot
148 // data[b] > pivot; data[c-1] < pivot
155 swapRange(data
, lo
, b
-n
, n
)
158 swapRange(data
, c
, hi
-n
, n
)
160 return lo
+ b
- a
, hi
- (d
- c
)
163 func quickSort(data Interface
, a
, b
, maxDepth
int) {
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).
174 quickSort(data
, a
, mlo
, maxDepth
)
175 a
= mhi
// i.e., quickSort(data, mhi, b)
177 quickSort(data
, mhi
, b
, maxDepth
)
178 b
= mlo
// i.e., quickSort(data, a, mlo)
182 insertionSort(data
, a
, b
)
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.
193 for i
:= n
; i
> 0; i
>>= 1 {
197 quickSort(data
, 0, n
, maxDepth
)
200 // IsSorted reports whether data is sorted.
201 func IsSorted(data Interface
) bool {
203 for i
:= n
- 1; i
> 0; i
-- {
204 if data
.Less(i
, i
-1) {
211 // Convenience types for common cases
213 // IntSlice attaches the methods of Interface to []int, sorting in increasing order.
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
] }
220 // Sort is a convenience method.
221 func (p IntSlice
) Sort() { Sort(p
) }
223 // Float64Slice attaches the methods of Interface to []float64, sorting in increasing order.
224 type Float64Slice
[]float64
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
] }
230 // Sort is a convenience method.
231 func (p Float64Slice
) Sort() { Sort(p
) }
233 // StringSlice attaches the methods of Interface to []string, sorting in increasing order.
234 type StringSlice
[]string
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
] }
240 // Sort is a convenience method.
241 func (p StringSlice
) Sort() { Sort(p
) }
243 // Convenience wrappers for common cases
245 // Ints sorts a slice of ints in increasing order.
246 func Ints(a
[]int) { Sort(IntSlice(a
)) }
248 // Float64s sorts a slice of float64s in increasing order.
249 func Float64s(a
[]float64) { Sort(Float64Slice(a
)) }
251 // Strings sorts a slice of strings in increasing order.
252 func Strings(a
[]string) { Sort(StringSlice(a
)) }
254 // IntsAreSorted tests whether a slice of ints is sorted in increasing order.
255 func IntsAreSorted(a
[]int) bool { return IsSorted(IntSlice(a
)) }
257 // Float64sAreSorted tests whether a slice of float64s is sorted in increasing order.
258 func Float64sAreSorted(a
[]float64) bool { return IsSorted(Float64Slice(a
)) }
260 // StringsAreSorted tests whether a slice of strings is sorted in increasing order.
261 func StringsAreSorted(a
[]string) bool { return IsSorted(StringSlice(a
)) }