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

View as plain text