The Go Programming Language

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	// Quicksort, following Bentley and McIlroy,
    41	// ``Engineering a Sort Function,'' SP&E November 1993.
    42	
    43	// Move the median of the three values data[a], data[b], data[c] into data[a].
    44	func medianOfThree(data Interface, a, b, c int) {
    45		m0 := b
    46		m1 := a
    47		m2 := c
    48		// bubble sort on 3 elements
    49		if data.Less(m1, m0) {
    50			data.Swap(m1, m0)
    51		}
    52		if data.Less(m2, m1) {
    53			data.Swap(m2, m1)
    54		}
    55		if data.Less(m1, m0) {
    56			data.Swap(m1, m0)
    57		}
    58		// now data[m0] <= data[m1] <= data[m2]
    59	}
    60	
    61	func swapRange(data Interface, a, b, n int) {
    62		for i := 0; i < n; i++ {
    63			data.Swap(a+i, b+i)
    64		}
    65	}
    66	
    67	func doPivot(data Interface, lo, hi int) (midlo, midhi int) {
    68		m := lo + (hi-lo)/2 // Written like this to avoid integer overflow.
    69		if hi-lo > 40 {
    70			// Tukey's ``Ninther,'' median of three medians of three.
    71			s := (hi - lo) / 8
    72			medianOfThree(data, lo, lo+s, lo+2*s)
    73			medianOfThree(data, m, m-s, m+s)
    74			medianOfThree(data, hi-1, hi-1-s, hi-1-2*s)
    75		}
    76		medianOfThree(data, lo, m, hi-1)
    77	
    78		// Invariants are:
    79		//	data[lo] = pivot (set up by ChoosePivot)
    80		//	data[lo <= i < a] = pivot
    81		//	data[a <= i < b] < pivot
    82		//	data[b <= i < c] is unexamined
    83		//	data[c <= i < d] > pivot
    84		//	data[d <= i < hi] = pivot
    85		//
    86		// Once b meets c, can swap the "= pivot" sections
    87		// into the middle of the slice.
    88		pivot := lo
    89		a, b, c, d := lo+1, lo+1, hi, hi
    90		for b < c {
    91			if data.Less(b, pivot) { // data[b] < pivot
    92				b++
    93				continue
    94			}
    95			if !data.Less(pivot, b) { // data[b] = pivot
    96				data.Swap(a, b)
    97				a++
    98				b++
    99				continue
   100			}
   101			if data.Less(pivot, c-1) { // data[c-1] > pivot
   102				c--
   103				continue
   104			}
   105			if !data.Less(c-1, pivot) { // data[c-1] = pivot
   106				data.Swap(c-1, d-1)
   107				c--
   108				d--
   109				continue
   110			}
   111			// data[b] > pivot; data[c-1] < pivot
   112			data.Swap(b, c-1)
   113			b++
   114			c--
   115		}
   116	
   117		n := min(b-a, a-lo)
   118		swapRange(data, lo, b-n, n)
   119	
   120		n = min(hi-d, d-c)
   121		swapRange(data, c, hi-n, n)
   122	
   123		return lo + b - a, hi - (d - c)
   124	}
   125	
   126	func quickSort(data Interface, a, b int) {
   127		for b-a > 7 {
   128			mlo, mhi := doPivot(data, a, b)
   129			// Avoiding recursion on the larger subproblem guarantees
   130			// a stack depth of at most lg(b-a).
   131			if mlo-a < b-mhi {
   132				quickSort(data, a, mlo)
   133				a = mhi // i.e., quickSort(data, mhi, b)
   134			} else {
   135				quickSort(data, mhi, b)
   136				b = mlo // i.e., quickSort(data, a, mlo)
   137			}
   138		}
   139		if b-a > 1 {
   140			insertionSort(data, a, b)
   141		}
   142	}
   143	
   144	func Sort(data Interface) { quickSort(data, 0, data.Len()) }
   145	
   146	func IsSorted(data Interface) bool {
   147		n := data.Len()
   148		for i := n - 1; i > 0; i-- {
   149			if data.Less(i, i-1) {
   150				return false
   151			}
   152		}
   153		return true
   154	}
   155	
   156	// Convenience types for common cases
   157	
   158	// IntSlice attaches the methods of Interface to []int, sorting in increasing order.
   159	type IntSlice []int
   160	
   161	func (p IntSlice) Len() int           { return len(p) }
   162	func (p IntSlice) Less(i, j int) bool { return p[i] < p[j] }
   163	func (p IntSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
   164	
   165	// Sort is a convenience method.
   166	func (p IntSlice) Sort() { Sort(p) }
   167	
   168	// Float64Slice attaches the methods of Interface to []float64, sorting in increasing order.
   169	type Float64Slice []float64
   170	
   171	func (p Float64Slice) Len() int           { return len(p) }
   172	func (p Float64Slice) Less(i, j int) bool { return p[i] < p[j] || math.IsNaN(p[i]) && !math.IsNaN(p[j]) }
   173	func (p Float64Slice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
   174	
   175	// Sort is a convenience method.
   176	func (p Float64Slice) Sort() { Sort(p) }
   177	
   178	// StringSlice attaches the methods of Interface to []string, sorting in increasing order.
   179	type StringSlice []string
   180	
   181	func (p StringSlice) Len() int           { return len(p) }
   182	func (p StringSlice) Less(i, j int) bool { return p[i] < p[j] }
   183	func (p StringSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
   184	
   185	// Sort is a convenience method.
   186	func (p StringSlice) Sort() { Sort(p) }
   187	
   188	// Convenience wrappers for common cases
   189	
   190	// Ints sorts a slice of ints in increasing order.
   191	func Ints(a []int) { Sort(IntSlice(a)) }
   192	// Float64s sorts a slice of float64s in increasing order.
   193	func Float64s(a []float64) { Sort(Float64Slice(a)) }
   194	// Strings sorts a slice of strings in increasing order.
   195	func Strings(a []string) { Sort(StringSlice(a)) }
   196	
   197	// IntsAreSorted tests whether a slice of ints is sorted in increasing order.
   198	func IntsAreSorted(a []int) bool { return IsSorted(IntSlice(a)) }
   199	// Float64sAreSorted tests whether a slice of float64s is sorted in increasing order.
   200	func Float64sAreSorted(a []float64) bool { return IsSorted(Float64Slice(a)) }
   201	// StringsAreSorted tests whether a slice of strings is sorted in increasing order.
   202	func StringsAreSorted(a []string) bool { return IsSorted(StringSlice(a)) }

release.r60.3. Except as noted, this content is licensed under a Creative Commons Attribution 3.0 License.