Module: stdgo.sort
Overview
Package sort provides primitives for sorting slices and user-defined collections.
Index
-
function _breakPatterns(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _breakPatterns_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _heapSort(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _heapSort_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _insertionSort(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _insertionSort_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _partialInsertionSort(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Bool
-
function _reverseRange(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _reverseRange_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _rotate(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _m:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function _stable(_data:stdgo.sort.Interface, _n:stdgo.GoInt):Void
-
function _stable_func(_data:stdgo.sort.T_lessSwap, _n:stdgo.GoInt):Void
-
function _swapRange(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt, _n:stdgo.GoInt):Void
-
function _symMerge(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _m:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function find(_n:stdgo.GoInt, _cmp:()):{ _1:Bool; _0:stdgo.GoInt; }
-
function float64sAreSorted(_x:stdgo.Slice<stdgo.GoFloat64>):Bool
-
function reverse(_data:stdgo.sort.Interface):stdgo.sort.Interface
-
function reverseRange(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
-
function searchFloat64s(_a:stdgo.Slice<stdgo.GoFloat64>, _x:stdgo.GoFloat64):stdgo.GoInt
-
function searchInts(_a:stdgo.Slice<stdgo.GoInt>, _x:stdgo.GoInt):stdgo.GoInt
-
function searchStrings(_a:stdgo.Slice<stdgo.GoString>, _x:stdgo.GoString):stdgo.GoInt
-
function slice(_x:stdgo.AnyInterface, _less:(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool):Void
-
function sliceIsSorted(_x:stdgo.AnyInterface, _less:(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool):Bool
-
function sliceStable(_x:stdgo.AnyInterface, _less:(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool):Void
-
function stringsAreSorted(_x:stdgo.Slice<stdgo.GoString>):Bool
Examples
Constants
import stdgo.sort.Sort
final _decreasingHint:stdgo.sort.T_sortedHint = ((2 : stdgo.sort.Sort.T_sortedHint))
final _increasingHint:stdgo.sort.T_sortedHint = ((2 : stdgo.sort.Sort.T_sortedHint))
final _unknownHint:stdgo.sort.T_sortedHint = ((2 : stdgo.sort.Sort.T_sortedHint))
Functions
import stdgo.sort.Sort
function _breakPatterns
function _breakPatterns(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
breakPatterns scatters some elements around in an attempt to break some patterns that might cause imbalanced partitions in quicksort.
function _breakPatterns_func
function _breakPatterns_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
breakPatterns_func scatters some elements around in an attempt to break some patterns that might cause imbalanced partitions in quicksort.
function _choosePivot
function _choosePivot(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):{
_1:stdgo.sort.T_sortedHint;
_0:stdgo.GoInt;
}
choosePivot chooses a pivot in data[a:b].
[0,8): chooses a static pivot. [8,shortestNinther): uses the simple median-of-three method. [shortestNinther,∞): uses the Tukey ninther method.
function _choosePivot_func
function _choosePivot_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):{
_1:stdgo.sort.T_sortedHint;
_0:stdgo.GoInt;
}
choosePivot_func chooses a pivot in data[a:b].
[0,8): chooses a static pivot. [8,shortestNinther): uses the simple median-of-three method. [shortestNinther,∞): uses the Tukey ninther method.
function _heapSort
function _heapSort(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
function _heapSort_func
function _heapSort_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
function _insertionSort
function _insertionSort(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
insertionSort sorts data[a:b] using insertion sort.
function _insertionSort_func
function _insertionSort_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
insertionSort_func sorts data[a:b] using insertion sort.
function _isNaN
function _isNaN(_f:stdgo.GoFloat64):Bool
isNaN is a copy of math.IsNaN to avoid a dependency on the math package.
function _median
function _median(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt, _c:stdgo.GoInt, _swaps:stdgo.Pointer<stdgo.GoInt>):stdgo.GoInt
median returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.
function _medianAdjacent
function _medianAdjacent(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _swaps:stdgo.Pointer<stdgo.GoInt>):stdgo.GoInt
medianAdjacent finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.
function _medianAdjacent_func
function _medianAdjacent_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _swaps:stdgo.Pointer<stdgo.GoInt>):stdgo.GoInt
medianAdjacent_func finds the median of data[a - 1], data[a], data[a + 1] and stores the index into a.
function _median_func
function _median_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt, _c:stdgo.GoInt, _swaps:stdgo.Pointer<stdgo.GoInt>):stdgo.GoInt
median_func returns x where data[x] is the median of data[a],data[b],data[c], where x is a, b, or c.
function _nextPowerOfTwo
function _nextPowerOfTwo(_length:stdgo.GoInt):stdgo.GoUInt
function _order2
function _order2(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt, _swaps:stdgo.Pointer<stdgo.GoInt>):{
_1:stdgo.GoInt;
_0:stdgo.GoInt;
}
order2 returns x,y where data[x] \<= data[y], where x,y=a,b or x,y=b,a.
function _order2_func
function _order2_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt, _swaps:stdgo.Pointer<stdgo.GoInt>):{
_1:stdgo.GoInt;
_0:stdgo.GoInt;
}
order2_func returns x,y where data[x] \<= data[y], where x,y=a,b or x,y=b,a.
function _partialInsertionSort
function _partialInsertionSort(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Bool
partialInsertionSort partially sorts a slice, returns true if the slice is sorted at the end.
function _partialInsertionSort_func
function _partialInsertionSort_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Bool
partialInsertionSort_func partially sorts a slice, returns true if the slice is sorted at the end.
function _partition
function _partition(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt, _pivot:stdgo.GoInt):{
_1:Bool;
_0:stdgo.GoInt;
}
partition does one quicksort partition. Let p = data[pivot] Moves elements in data[a:b] around, so that data[i]\
=p for i\
function _partitionEqual
function _partitionEqual(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt, _pivot:stdgo.GoInt):stdgo.GoInt
partitionEqual partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot]. It assumed that data[a:b] does not contain elements smaller than the data[pivot].
function _partitionEqual_func
function _partitionEqual_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt, _pivot:stdgo.GoInt):stdgo.GoInt
partitionEqual_func partitions data[a:b] into elements equal to data[pivot] followed by elements greater than data[pivot]. It assumed that data[a:b] does not contain elements smaller than the data[pivot].
function _partition_func
function _partition_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt, _pivot:stdgo.GoInt):{
_1:Bool;
_0:stdgo.GoInt;
}
partition_func does one quicksort partition. Let p = data[pivot] Moves elements in data[a:b] around, so that data[i]\
=p for i\
function _pdqsort
function _pdqsort(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt, _limit:stdgo.GoInt):Void
pdqsort sorts data[a:b]. The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf C++ implementation: https://github.com/orlp/pdqsort Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
function _pdqsort_func
function _pdqsort_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt, _limit:stdgo.GoInt):Void
pdqsort_func sorts data[a:b]. The algorithm based on pattern-defeating quicksort(pdqsort), but without the optimizations from BlockQuicksort. pdqsort paper: https://arxiv.org/pdf/2106.05123.pdf C++ implementation: https://github.com/orlp/pdqsort Rust implementation: https://docs.rs/pdqsort/latest/pdqsort/ limit is the number of allowed bad (very unbalanced) pivots before falling back to heapsort.
function _reverseRange
function _reverseRange(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
function _reverseRange_func
function _reverseRange_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
function _rotate
function _rotate(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _m:stdgo.GoInt, _b:stdgo.GoInt):Void
rotate rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data: Data of the form 'x u v y' is changed to 'x v u y'. rotate performs at most b-a many calls to data.Swap, and it assumes non-degenerate arguments: a \< m && m \< b.
function _rotate_func
function _rotate_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _m:stdgo.GoInt, _b:stdgo.GoInt):Void
rotate_func rotates two consecutive blocks u = data[a:m] and v = data[m:b] in data: Data of the form 'x u v y' is changed to 'x v u y'. rotate performs at most b-a many calls to data.Swap, and it assumes non-degenerate arguments: a \< m && m \< b.
function _siftDown
function _siftDown(_data:stdgo.sort.Interface, _lo:stdgo.GoInt, _hi:stdgo.GoInt, _first:stdgo.GoInt):Void
siftDown implements the heap property on data[lo:hi]. first is an offset into the array where the root of the heap lies.
function _siftDown_func
function _siftDown_func(_data:stdgo.sort.T_lessSwap, _lo:stdgo.GoInt, _hi:stdgo.GoInt, _first:stdgo.GoInt):Void
siftDown_func implements the heap property on data[lo:hi]. first is an offset into the array where the root of the heap lies.
function _stable
function _stable(_data:stdgo.sort.Interface, _n:stdgo.GoInt):Void
function _stable_func
function _stable_func(_data:stdgo.sort.T_lessSwap, _n:stdgo.GoInt):Void
function _swapRange
function _swapRange(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt, _n:stdgo.GoInt):Void
function _swapRange_func
function _swapRange_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _b:stdgo.GoInt, _n:stdgo.GoInt):Void
function _symMerge
function _symMerge(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _m:stdgo.GoInt, _b:stdgo.GoInt):Void
symMerge merges the two sorted subsequences data[a:m] and data[m:b] using the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in Computer Science, pages 714-723. Springer, 2004.
Let M = m-a and N = b-n. Wolog M \< N. The recursion depth is bound by ceil(log(N+M)). The algorithm needs O(M\log(N/M + 1)) calls to data.Less. The algorithm needs O((M+N)\log(M)) calls to data.Swap.
The paper gives O((M+N)*log(M)) as the number of assignments assuming a rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation in the paper carries through for Swap operations, especially as the block swapping rotate uses only O(M+N) Swaps.
symMerge assumes non-degenerate arguments: a \< m && m \< b. Having the caller check this condition eliminates many leaf recursion calls, which improves performance.
function _symMerge_func
function _symMerge_func(_data:stdgo.sort.T_lessSwap, _a:stdgo.GoInt, _m:stdgo.GoInt, _b:stdgo.GoInt):Void
symMerge_func merges the two sorted subsequences data[a:m] and data[m:b] using the SymMerge algorithm from Pok-Son Kim and Arne Kutzner, "Stable Minimum Storage Merging by Symmetric Comparisons", in Susanne Albers and Tomasz Radzik, editors, Algorithms - ESA 2004, volume 3221 of Lecture Notes in Computer Science, pages 714-723. Springer, 2004.
Let M = m-a and N = b-n. Wolog M \< N. The recursion depth is bound by ceil(log(N+M)). The algorithm needs O(M\log(N/M + 1)) calls to data.Less. The algorithm needs O((M+N)\log(M)) calls to data.Swap.
The paper gives O((M+N)*log(M)) as the number of assignments assuming a rotation algorithm which uses O(M+N+gcd(M+N)) assignments. The argumentation in the paper carries through for Swap operations, especially as the block swapping rotate uses only O(M+N) Swaps.
symMerge assumes non-degenerate arguments: a \< m && m \< b. Having the caller check this condition eliminates many leaf recursion calls, which improves performance.
function find
function find(_n:stdgo.GoInt, _cmp:()):{
_1:Bool;
_0:stdgo.GoInt;
}
Find uses binary search to find and return the smallest index i in [0, n) at which cmp(i) \<= 0. If there is no such index i, Find returns i = n. The found result is true if i \< n and cmp(i) == 0. Find calls cmp(i) only for i in the range [0, n).
To permit binary search, Find requires that cmp(i) \> 0 for a leading prefix of the range, cmp(i) == 0 in the middle, and cmp(i) \< 0 for the final suffix of the range. (Each subrange could be empty.) The usual way to establish this condition is to interpret cmp(i) as a comparison of a desired target value t against entry i in an underlying indexed data structure x, returning \<0, 0, and \>0 when t \< x[i], t == x[i], and t \> x[i], respectively.
For example, to look for a particular string in a sorted, random-access list of strings:
i, found := sort.Find(x.Len(), func(i int) int {
return strings.Compare(target, x.At(i))
})
if found {
fmt.Printf("found %s at entry %d\n", target, i)
} else {
fmt.Printf("%s not found, would insert at %d", target, i)
}
function float64s
function float64s(_x:stdgo.Slice<stdgo.GoFloat64>):Void
Float64s sorts a slice of float64s in increasing order. Not-a-number (NaN) values are ordered before other values.
Note: consider using the newer slices.Sort function, which runs faster.
exampleFloat64s
function exampleFloat64s():Void {
var _s = (new stdgo.Slice<stdgo.GoFloat64>(5, 5, (5.2 : stdgo.GoFloat64), (-1.3 : stdgo.GoFloat64), (0.7 : stdgo.GoFloat64), (-3.8 : stdgo.GoFloat64), (2.6 : stdgo.GoFloat64)) : stdgo.Slice<stdgo.GoFloat64>);
stdgo.sort.Sort.float64s(_s);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(_s));
_s = (new stdgo.Slice<stdgo.GoFloat64>(4, 4, stdgo.math.Math.inf((1 : stdgo.GoInt)), stdgo.math.Math.naN(), stdgo.math.Math.inf((-1 : stdgo.GoInt)), (0 : stdgo.GoFloat64)) : stdgo.Slice<stdgo.GoFloat64>);
stdgo.sort.Sort.float64s(_s);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(_s));
}
function float64sAreSorted
function float64sAreSorted(_x:stdgo.Slice<stdgo.GoFloat64>):Bool
Float64sAreSorted reports whether the slice x is sorted in increasing order, with not-a-number (NaN) values before any other values.
Note: consider using the newer slices.IsSorted function, which runs faster.
exampleFloat64sAreSorted
function exampleFloat64sAreSorted():Void {
var _s = (new stdgo.Slice<stdgo.GoFloat64>(5, 5, (0.7 : stdgo.GoFloat64), (1.3 : stdgo.GoFloat64), (2.6 : stdgo.GoFloat64), (3.8 : stdgo.GoFloat64), (5.2 : stdgo.GoFloat64)) : stdgo.Slice<stdgo.GoFloat64>);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(stdgo.sort.Sort.float64sAreSorted(_s)));
_s = (new stdgo.Slice<stdgo.GoFloat64>(5, 5, (5.2 : stdgo.GoFloat64), (3.8 : stdgo.GoFloat64), (2.6 : stdgo.GoFloat64), (1.3 : stdgo.GoFloat64), (0.7 : stdgo.GoFloat64)) : stdgo.Slice<stdgo.GoFloat64>);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(stdgo.sort.Sort.float64sAreSorted(_s)));
_s = (new stdgo.Slice<stdgo.GoFloat64>(5, 5, (5.2 : stdgo.GoFloat64), (1.3 : stdgo.GoFloat64), (0.7 : stdgo.GoFloat64), (3.8 : stdgo.GoFloat64), (2.6 : stdgo.GoFloat64)) : stdgo.Slice<stdgo.GoFloat64>);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(stdgo.sort.Sort.float64sAreSorted(_s)));
}
function heapsort
function heapsort(_data:stdgo.sort.Interface):Void
function ints
function ints(_x:stdgo.Slice<stdgo.GoInt>):Void
Ints sorts a slice of ints in increasing order.
Note: consider using the newer slices.Sort function, which runs faster.
exampleInts
function exampleInts():Void {
var _s = (new stdgo.Slice<stdgo.GoInt>(6, 6, (5 : stdgo.GoInt), (2 : stdgo.GoInt), (6 : stdgo.GoInt), (3 : stdgo.GoInt), (1 : stdgo.GoInt), (4 : stdgo.GoInt)) : stdgo.Slice<stdgo.GoInt>);
stdgo.sort.Sort.ints(_s);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(_s));
}
function intsAreSorted
function intsAreSorted(_x:stdgo.Slice<stdgo.GoInt>):Bool
IntsAreSorted reports whether the slice x is sorted in increasing order.
Note: consider using the newer slices.IsSorted function, which runs faster.
exampleIntsAreSorted
function exampleIntsAreSorted():Void {
var _s = (new stdgo.Slice<stdgo.GoInt>(6, 6, (1 : stdgo.GoInt), (2 : stdgo.GoInt), (3 : stdgo.GoInt), (4 : stdgo.GoInt), (5 : stdgo.GoInt), (6 : stdgo.GoInt)) : stdgo.Slice<stdgo.GoInt>);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(stdgo.sort.Sort.intsAreSorted(_s)));
_s = (new stdgo.Slice<stdgo.GoInt>(6, 6, (6 : stdgo.GoInt), (5 : stdgo.GoInt), (4 : stdgo.GoInt), (3 : stdgo.GoInt), (2 : stdgo.GoInt), (1 : stdgo.GoInt)) : stdgo.Slice<stdgo.GoInt>);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(stdgo.sort.Sort.intsAreSorted(_s)));
_s = (new stdgo.Slice<stdgo.GoInt>(5, 5, (3 : stdgo.GoInt), (2 : stdgo.GoInt), (4 : stdgo.GoInt), (1 : stdgo.GoInt), (5 : stdgo.GoInt)) : stdgo.Slice<stdgo.GoInt>);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(stdgo.sort.Sort.intsAreSorted(_s)));
}
function isSorted
function isSorted(_data:stdgo.sort.Interface):Bool
IsSorted reports whether data is sorted.
Note: in many situations, the newer slices.IsSortedFunc function is more ergonomic and runs faster.
function reverse
function reverse(_data:stdgo.sort.Interface):stdgo.sort.Interface
Reverse returns the reverse order for data.
exampleReverse
function exampleReverse():Void {
var _s = (new stdgo.Slice<stdgo.GoInt>(6, 6, (5 : stdgo.GoInt), (2 : stdgo.GoInt), (6 : stdgo.GoInt), (3 : stdgo.GoInt), (1 : stdgo.GoInt), (4 : stdgo.GoInt)) : stdgo.Slice<stdgo.GoInt>);
stdgo.sort.Sort.sort(stdgo.sort.Sort.reverse(stdgo.Go.asInterface((_s : stdgo.sort.Sort.IntSlice))));
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(_s));
}
function reverseRange
function reverseRange(_data:stdgo.sort.Interface, _a:stdgo.GoInt, _b:stdgo.GoInt):Void
function search
function search(_n:stdgo.GoInt, _f:()):stdgo.GoInt
Search uses binary search to find and return the smallest index i in [0, n) at which f(i) is true, assuming that on the range [0, n), f(i) == true implies f(i+1) == true. That is, Search requires that f is false for some (possibly empty) prefix of the input range [0, n) and then true for the (possibly empty) remainder; Search returns the first true index. If there is no such index, Search returns n. (Note that the "not found" return value is not -1 as in, for instance, strings.Index.) Search calls f(i) only for i in the range [0, n).
A common use of Search is to find the index i for a value x in a sorted, indexable data structure such as an array or slice. In this case, the argument f, typically a closure, captures the value to be searched for, and how the data structure is indexed and ordered.
For instance, given a slice data sorted in ascending order, the call Search(len(data), func(i int) bool { return data[i] \>= 23 }) returns the smallest index i such that data[i] \>= 23. If the caller wants to find whether 23 is in the slice, it must test data[i] == 23 separately.
Searching data sorted in descending order would use the \<= operator instead of the \>= operator.
To complete the example above, the following code tries to find the value x in an integer slice data sorted in ascending order:
x := 23
i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
if i < len(data) && data[i] == x {
// x is present at data[i]
} else {
// x is not present in data,
// but i is the index where it would be inserted.
}
As a more whimsical example, this program guesses your number:
func GuessingGame() {
var s string
fmt.Printf("Pick an integer from 0 to 100.\n")
answer := sort.Search(100, func(i int) bool {
fmt.Printf("Is your number <= %d? ", i)
fmt.Scanf("%s", &s)
return s != "" && s[0] == 'y'
})
fmt.Printf("Your number is %d.\n", answer)
}
exampleSearch
function exampleSearch():Void {
var _a = (new stdgo.Slice<stdgo.GoInt>(
10,
10,
(1 : stdgo.GoInt),
(3 : stdgo.GoInt),
(6 : stdgo.GoInt),
(10 : stdgo.GoInt),
(15 : stdgo.GoInt),
(21 : stdgo.GoInt),
(28 : stdgo.GoInt),
(36 : stdgo.GoInt),
(45 : stdgo.GoInt),
(55 : stdgo.GoInt)) : stdgo.Slice<stdgo.GoInt>);
var _x:stdgo.GoInt = (6 : stdgo.GoInt);
var _i:stdgo.GoInt = stdgo.sort.Sort.search((_a.length), function(_i:stdgo.GoInt):Bool {
return _a[(_i : stdgo.GoInt)] >= _x;
});
if ((_i < _a.length) && (_a[(_i : stdgo.GoInt)] == _x)) {
stdgo.fmt.Fmt.printf(("found %d at index %d in %v\n" : stdgo.GoString), stdgo.Go.toInterface(_x), stdgo.Go.toInterface(_i), stdgo.Go.toInterface(_a));
} else {
stdgo.fmt.Fmt.printf(("%d not found in %v\n" : stdgo.GoString), stdgo.Go.toInterface(_x), stdgo.Go.toInterface(_a));
};
}
exampleSearch_descendingOrder
function exampleSearch_descendingOrder():Void {
var _a = (new stdgo.Slice<stdgo.GoInt>(
10,
10,
(55 : stdgo.GoInt),
(45 : stdgo.GoInt),
(36 : stdgo.GoInt),
(28 : stdgo.GoInt),
(21 : stdgo.GoInt),
(15 : stdgo.GoInt),
(10 : stdgo.GoInt),
(6 : stdgo.GoInt),
(3 : stdgo.GoInt),
(1 : stdgo.GoInt)) : stdgo.Slice<stdgo.GoInt>);
var _x:stdgo.GoInt = (6 : stdgo.GoInt);
var _i:stdgo.GoInt = stdgo.sort.Sort.search((_a.length), function(_i:stdgo.GoInt):Bool {
return _a[(_i : stdgo.GoInt)] <= _x;
});
if ((_i < _a.length) && (_a[(_i : stdgo.GoInt)] == _x)) {
stdgo.fmt.Fmt.printf(("found %d at index %d in %v\n" : stdgo.GoString), stdgo.Go.toInterface(_x), stdgo.Go.toInterface(_i), stdgo.Go.toInterface(_a));
} else {
stdgo.fmt.Fmt.printf(("%d not found in %v\n" : stdgo.GoString), stdgo.Go.toInterface(_x), stdgo.Go.toInterface(_a));
};
}
function searchFloat64s
function searchFloat64s(_a:stdgo.Slice<stdgo.GoFloat64>, _x:stdgo.GoFloat64):stdgo.GoInt
SearchFloat64s searches for x in a sorted slice of float64s and returns the index as specified by Search. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.
exampleSearchFloat64s
function exampleSearchFloat64s():Void {
var _a = (new stdgo.Slice<stdgo.GoFloat64>(7, 7, (1 : stdgo.GoFloat64), (2 : stdgo.GoFloat64), (3.3 : stdgo.GoFloat64), (4.6 : stdgo.GoFloat64), (6.1 : stdgo.GoFloat64), (7.2 : stdgo.GoFloat64), (8 : stdgo.GoFloat64)) : stdgo.Slice<stdgo.GoFloat64>);
var _x:stdgo.GoFloat64 = (2 : stdgo.GoFloat64);
var _i:stdgo.GoInt = stdgo.sort.Sort.searchFloat64s(_a, _x);
stdgo.fmt.Fmt.printf(("found %g at index %d in %v\n" : stdgo.GoString), stdgo.Go.toInterface(_x), stdgo.Go.toInterface(_i), stdgo.Go.toInterface(_a));
_x = (0.5 : stdgo.GoFloat64);
_i = stdgo.sort.Sort.searchFloat64s(_a, _x);
stdgo.fmt.Fmt.printf(("%g not found, can be inserted at index %d in %v\n" : stdgo.GoString), stdgo.Go.toInterface(_x), stdgo.Go.toInterface(_i), stdgo.Go.toInterface(_a));
}
function searchInts
function searchInts(_a:stdgo.Slice<stdgo.GoInt>, _x:stdgo.GoInt):stdgo.GoInt
SearchInts searches for x in a sorted slice of ints and returns the index as specified by Search. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.
exampleSearchInts
function exampleSearchInts():Void {
var _a = (new stdgo.Slice<stdgo.GoInt>(7, 7, (1 : stdgo.GoInt), (2 : stdgo.GoInt), (3 : stdgo.GoInt), (4 : stdgo.GoInt), (6 : stdgo.GoInt), (7 : stdgo.GoInt), (8 : stdgo.GoInt)) : stdgo.Slice<stdgo.GoInt>);
var _x:stdgo.GoInt = (2 : stdgo.GoInt);
var _i:stdgo.GoInt = stdgo.sort.Sort.searchInts(_a, _x);
stdgo.fmt.Fmt.printf(("found %d at index %d in %v\n" : stdgo.GoString), stdgo.Go.toInterface(_x), stdgo.Go.toInterface(_i), stdgo.Go.toInterface(_a));
_x = (5 : stdgo.GoInt);
_i = stdgo.sort.Sort.searchInts(_a, _x);
stdgo.fmt.Fmt.printf(("%d not found, can be inserted at index %d in %v\n" : stdgo.GoString), stdgo.Go.toInterface(_x), stdgo.Go.toInterface(_i), stdgo.Go.toInterface(_a));
}
function searchStrings
function searchStrings(_a:stdgo.Slice<stdgo.GoString>, _x:stdgo.GoString):stdgo.GoInt
SearchStrings searches for x in a sorted slice of strings and returns the index as specified by Search. The return value is the index to insert x if x is not present (it could be len(a)). The slice must be sorted in ascending order.
function slice
function slice(_x:stdgo.AnyInterface, _less:(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool):Void
Slice sorts the slice x given the provided less function. It panics if x is not a slice.
The sort is not guaranteed to be stable: equal elements may be reversed from their original order. For a stable sort, use SliceStable.
The less function must satisfy the same requirements as the Interface type's Less method.
exampleSlice
function exampleSlice():Void {
var _people = (new stdgo.Slice<Person>(4, 4, (new Person(("Gopher" : stdgo.GoString), (7 : stdgo.GoInt)) : Person), (new Person(("Alice" : stdgo.GoString), (55 : stdgo.GoInt)) : Person), (new Person(("Vera" : stdgo.GoString), (24 : stdgo.GoInt)) : Person), (new Person(("Bob" : stdgo.GoString), (75 : stdgo.GoInt)) : Person)) : stdgo.Slice<Person>);
stdgo.sort.Sort.slice(stdgo.Go.toInterface(_people), function(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool {
return _people[(_i : stdgo.GoInt)].name < _people[(_j : stdgo.GoInt)].name;
});
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(("By name:" : stdgo.GoString)), stdgo.Go.toInterface(_people));
stdgo.sort.Sort.slice(stdgo.Go.toInterface(_people), function(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool {
return _people[(_i : stdgo.GoInt)].age < _people[(_j : stdgo.GoInt)].age;
});
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(("By age:" : stdgo.GoString)), stdgo.Go.toInterface(_people));
}
function sliceIsSorted
function sliceIsSorted(_x:stdgo.AnyInterface, _less:(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool):Bool
SliceIsSorted reports whether the slice x is sorted according to the provided less function. It panics if x is not a slice.
function sliceStable
function sliceStable(_x:stdgo.AnyInterface, _less:(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool):Void
SliceStable sorts the slice x using the provided less function, keeping equal elements in their original order. It panics if x is not a slice.
The less function must satisfy the same requirements as the Interface type's Less method.
exampleSliceStable
function exampleSliceStable():Void {
var _people = (new stdgo.Slice<Person>(8, 8, (new Person(("Alice" : stdgo.GoString), (25 : stdgo.GoInt)) : Person), (new Person(("Elizabeth" : stdgo.GoString), (75 : stdgo.GoInt)) : Person), (new Person(("Alice" : stdgo.GoString), (75 : stdgo.GoInt)) : Person), (new Person(("Bob" : stdgo.GoString), (75 : stdgo.GoInt)) : Person), (new Person(("Alice" : stdgo.GoString), (75 : stdgo.GoInt)) : Person), (new Person(("Bob" : stdgo.GoString), (25 : stdgo.GoInt)) : Person), (new Person(("Colin" : stdgo.GoString), (25 : stdgo.GoInt)) : Person), (new Person(("Elizabeth" : stdgo.GoString), (25 : stdgo.GoInt)) : Person)) : stdgo.Slice<Person>);
stdgo.sort.Sort.sliceStable(stdgo.Go.toInterface(_people), function(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool {
return _people[(_i : stdgo.GoInt)].name < _people[(_j : stdgo.GoInt)].name;
});
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(("By name:" : stdgo.GoString)), stdgo.Go.toInterface(_people));
stdgo.sort.Sort.sliceStable(stdgo.Go.toInterface(_people), function(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool {
return _people[(_i : stdgo.GoInt)].age < _people[(_j : stdgo.GoInt)].age;
});
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(("By age,name:" : stdgo.GoString)), stdgo.Go.toInterface(_people));
}
function sort
function sort(_data:stdgo.sort.Interface):Void
Sort sorts data in ascending order as determined by the Less method. It makes one call to data.Len to determine n and O(n*log(n)) calls to data.Less and data.Swap. The sort is not guaranteed to be stable.
Note: in many situations, the newer slices.SortFunc function is more ergonomic and runs faster.
function stable
function stable(_data:stdgo.sort.Interface):Void
Stable sorts data in ascending order as determined by the Less method, while keeping the original order of equal elements.
It makes one call to data.Len to determine n, O(n\log(n)) calls to data.Less and O(n\log(n)*log(n)) calls to data.Swap.
Note: in many situations, the newer slices.SortStableFunc function is more ergonomic and runs faster.
function strings
function strings(_x:stdgo.Slice<stdgo.GoString>):Void
Strings sorts a slice of strings in increasing order.
Note: consider using the newer slices.Sort function, which runs faster.
exampleStrings
function exampleStrings():Void {
var _s = (new stdgo.Slice<stdgo.GoString>(6, 6, ("Go" : stdgo.GoString), ("Bravo" : stdgo.GoString), ("Gopher" : stdgo.GoString), ("Alpha" : stdgo.GoString), ("Grin" : stdgo.GoString), ("Delta" : stdgo.GoString)) : stdgo.Slice<stdgo.GoString>);
stdgo.sort.Sort.strings(_s);
stdgo.fmt.Fmt.println(stdgo.Go.toInterface(_s));
}
function stringsAreSorted
function stringsAreSorted(_x:stdgo.Slice<stdgo.GoString>):Bool
StringsAreSorted reports whether the slice x is sorted in increasing order.
Note: consider using the newer slices.IsSorted function, which runs faster.
Typedefs
import stdgo.sort.*
typedef Float64Slice
typedef Float64Slice = stdgo.Slice<stdgo.GoFloat64>;
Float64Slice implements Interface for a []float64, sorting in increasing order, with not-a-number (NaN) values ordered before other values.
typedef IntSlice
typedef IntSlice = stdgo.Slice<stdgo.GoInt>;
IntSlice attaches the methods of Interface to []int, sorting in increasing order.
typedef Interface
typedef Interface = {
public function swap(_i:stdgo.GoInt, _j:stdgo.GoInt):Void; // Swap swaps the elements with indexes i and j.
public function less(_i:stdgo.GoInt, _j:stdgo.GoInt):Bool; // Less reports whether the element with index i must sort before the element with index j. If both Less(i, j) and Less(j, i) are false, then the elements at index i and j are considered equal. Sort may place equal elements in any order in the final result, while Stable preserves the original input order of equal elements. Less must describe a transitive ordering: - if both Less(i, j) and Less(j, k) are true, then Less(i, k) must be true as well. - if both Less(i, j) and Less(j, k) are false, then Less(i, k) must be false as well. Note that floating-point comparison (the < operator on float32 or float64 values) is not a transitive ordering when not-a-number (NaN) values are involved. See Float64Slice.Less for a correct implementation for floating-point values.
public function len():stdgo.GoInt; // Len is the number of elements in the collection.
};
An implementation of Interface can be sorted by the routines in this package. The methods refer to elements of the underlying collection by integer index.
typedef StringSlice
typedef StringSlice = stdgo.Slice<stdgo.GoString>;
StringSlice attaches the methods of Interface to []string, sorting in increasing order.
typedef T_sortedHint
typedef T_sortedHint = stdgo.GoInt;
typedef T_xorshift
typedef T_xorshift = stdgo.GoUInt64;
xorshift paper: https://www.jstatsoft.org/article/view/v008i14/xorshift.pdf