Sort¶
Usage
use Sort;
The Sort module is designed to support standard sort routines.
Comparators¶
Comparators allow sorting data by a mechanism other than the default comparison operations between array elements. To use a comparator, define a record or a class with an appropriate method and then pass an instance of it to the sort function. Examples are shown below.
Comparators need to include at least one of the following methods:
key(a)
-- see The .key methodcompare(a, b)
-- see The .compare methodkeyPart(a, i)
-- see The .keyPart method
See the section below for discussion of each of these methods.
A comparator can contain both compare
and keyPart
methods. In that
event, the sort algorithm will use whichever is appropriate for the algorithm
and expect that they have consistent results.
It is an error for a comparator to contain a key
method as well as one of
the other methods.
The .key method¶
The key(a)
method accepts 1 argument, which will be an element from the
array being sorted.
The default key method would look like this:
proc DefaultComparator.key(a) {
return a;
}
As an example, if the user wants to sort an array by the absolute values of its elements, the user can define a comparator with a key method as follows:
var Array = [-1, -4, 2, 3];
// Empty record serves as comparator
record Comparator { }
// key method maps an element to the value to be used for comparison
proc Comparator.key(a) { return abs(a); }
var absComparator: Comparator;
sort(Array, comparator=absComparator);
// This will output: -1, 2, 3, -4
writeln(Array);
The return type of key(a)
must support the <
operator, which is used by the base compare method of all sort routines. If the
<
operator is not defined for the return type, the user may define it
themselves like so:
proc op<(a: returnType, b: returnType): bool {
...
}
The .compare method¶
The compare(a, b)
method accepts 2 arguments, which will be 2 elements from
the array being sorted. The return value should be a numeric signed type
indicating how a and b compare to each other. The conditions between a
and
b
should result in the following return values for compare(a, b)
:
Return Value Condition > 0
a > b
0
a == b
< 0
a < b
The default compare method for a signed integral type can look like this:
proc DefaultComparator.compare(a, b) {
return a - b;
}
The absolute value comparison example from above can alternatively be implemented with a compare method:
var Array = [-1, -4, 2, 3];
// Empty record serves as comparator
record Comparator { }
// compare method defines how 2 elements are compared
proc Comparator.compare(a, b) {
return abs(a) - abs(b);
}
var absComparator: Comparator;
sort(Array, comparator=absComparator);
// This will output: -1, 2, 3, -4
writeln(Array);
The .keyPart method¶
A keyPart(a, i)
method returns parts of key value at a time. This
interface supports radix sorting for variable length data types, such as
strings. It accepts two arguments:
a
is the element being sortedi
is the part number of the key requested, starting from 1
A keyPart
method should return a tuple consisting of section and a part.
The section can be any signed integral type and should have the value -1, 0, or 1. It indicates when the end of the
a
has been reached and in that event how it should be sorted relative to other array elements.
Returned section Interpretation -1
no more key parts for a
, sort it before those with more parts0
a key part for a
is returned in the second tuple element1
no more key parts for a
, sort it after those with more partsThe part can be any signed or unsigned integral type and can contain any value. The part will be ignored unless the section returned is
0
.
Let's consider several example keyPart
methods. All of these are
simplifications of keyPart
methods already available in the
DefaultComparator
.
This keyPart
method supports sorting tuples of 2 integers:
proc keyPart(x:2*int, i:int) {
if i > 2 then
return (-1, 0);
return (0, x(i));
}
Here is a keyPart
to support sorting of strings:
proc keyPart(x:string, i:int):(int(8), uint(8)) {
var len = x.length;
var section = if i <= len then 0:int(8) else -1:int(8);
var part = if i <= len then x.byte(i) else 0:uint(8);
return (section, part);
}
Reverse Comparator¶
Sort functions in Chapel do not have a reverse
argument. Instead, reverse
sorting is handled through the comparator interface.
A module-defined reverseComparator
can be passed to a sort function to
reverse the default sorting order.
var Array = [-1, -4, 2, 3];
// Using module-defined 'reverseComparator'
sort(Array, comparator=reverseComparator)
// This will output: 3, 2, -1, -4
writeln(Array);
To reverse the sort order of a user-defined comparator, pass the user-defined
comparator to the initializer of the module-defined
ReverseComparator
record, which can be passed to the sort function.
var Array = [-1, -4, 2, 3];
// Empty record serves as comparator
record Comparator { }
// compare method defines how 2 elements are compared
proc Comparator.compare(a, b) {
return abs(a) - abs(b);
}
var absReverseComparator: ReverseComparator(Comparator);
sort(Array, comparator=absReverseComparator);
// This will output: -4, 3, 2, -1
writeln(Array);
-
const
defaultComparator
: DefaultComparator¶ Instance of
DefaultComparator
used as defaultcomparator=
argument when no comparator is passed to a sort function
-
const
reverseComparator
: ReverseComparator(DefaultComparator)¶ Instance of
ReverseComparator
. Pass this as thecomparator=
argument of a sort function to reverse the sort order.
-
proc
sort
(Data: [?Dom] ?eltType, comparator: ?rec = defaultComparator)¶ Sort the elements in an array. It is up to the implementation to choose the sorting algorithm.
Note
This function currently either uses a parallel radix sort or a serial quickSort. The algorithms used will change over time.
It currently uses parallel radix sort if the following conditions are met:
- the array being sorted is over a non-strided domain
comparator
includes akeyPart
method foreltType
or includes akey
returning a value for which the default comparator includes akeyPart
method
Note that the default comparator includes
keyPart
methods for:int
- tuples of
int
uint
- tuples of
uint
string
Arguments: - Data : [] eltType -- The array to be sorted
- comparator -- Comparator record that defines how the data is sorted.
-
proc
isSorted
(Data: [?Dom] ?eltType, comparator: ?rec = defaultComparator): bool¶ Check if array Data is in sorted order
Arguments: - Data : [] eltType -- The array to verify
- comparator -- Comparator record that defines how the data is sorted.
Returns: true
if array is sortedReturn type: bool
-
iter
sorted
(x, comparator: ?rec = defaultComparator)¶ Yield the elements of argument x in sorted order, using sort algorithm.
Arguments: - x : iterable -- An iterable value to be sorted and yielded element by element
- comparator -- Comparator record that defines how the data is sorted.
Yields: The elements of x in sorted order
Yield type: x's element type
-
proc
bubbleSort
(Data: [?Dom] ?eltType, comparator: ?rec = defaultComparator)¶ Sort the 1D array Data in-place using a sequential bubble sort algorithm.
Arguments: - Data : [] eltType -- The array to be sorted
- comparator -- Comparator record that defines how the data is sorted.
-
proc
heapSort
(Data: [?Dom] ?eltType, comparator: ?rec = defaultComparator)¶ Sort the 1D array Data in-place using a sequential heap sort algorithm.
Arguments: - Data : [] eltType -- The array to be sorted
- comparator -- Comparator record that defines how the data is sorted.
-
proc
insertionSort
(Data: [?Dom] ?eltType, comparator: ?rec = defaultComparator)¶ Sort the 1D array Data in-place using a sequential insertion sort algorithm.
Arguments: - Data : [] eltType -- The array to be sorted
- comparator -- Comparator record that defines how the data is sorted.
-
proc
binaryInsertionSort
(Data: [?Dom] ?eltType, comparator: ?rec = defaultComparator)¶ Sort the 1D array Data in-place using a sequential, stable binary insertion sort algorithm. Should be used when there is a high cost of comparison.
Arguments: - Data : [] eltType -- The array to be sorted
- comparator -- Comparator record that defines how the data is sorted.
-
proc
mergeSort
(Data: [?Dom] ?eltType, minlen = 16, comparator: ?rec = defaultComparator)¶ Sort the 1D array Data using a parallel merge sort algorithm.
Arguments: - Data : [] eltType -- The array to be sorted
- minlen : integral -- When the array size is less than minlen use
insertionSort
algorithm - comparator -- Comparator record that defines how the data is sorted.
-
proc
quickSort
(Data: [?Dom] ?eltType, minlen = 16, comparator: ?rec = defaultComparator)¶ Sort the 1D array Data in-place using a sequential quick sort algorithm.
Arguments: - Data : [] eltType -- The array to be sorted
- minlen : integral -- When the array size is less than minlen use
insertionSort
algorithm - comparator -- Comparator record that defines how the data is sorted.
-
proc
selectionSort
(Data: [?Dom] ?eltType, comparator: ?rec = defaultComparator)¶ Sort the 1D array Data in-place using a sequential selection sort algorithm.
Arguments: - Data : [] eltType -- The array to be sorted
- comparator -- Comparator record that defines how the data is sorted.
-
record
DefaultComparator
¶ Default comparator used in sort functions.
-
proc
compare
(a, b)¶ Default compare method used in sort functions. Uses the < operator to compute the ordering between
a
andb
. See also The .compare method.Returns: 1 if b < a
Returns: 0 if a == b
Returns: -1 if a < b
-
proc
keyPart
(x: integral, i: int): (int(8), x.type )¶ Default
keyPart
method for integral values. See also The .keyPart method.Arguments: - x -- the int or uint of any size to sort
- i -- the part number requested
Returns: (0, x)
ifi==0
, or(-1, x)
otherwise
-
proc
keyPart
(x: _tuple, i: int) Default
keyPart
method for tuples of integral values. See also The .keyPart method.Arguments: - x -- tuple of the int or uint (of any bit width) to sort
- i -- the part number requested
Returns: (0, x(i))
ifi <= x.size
, or(-1, 0)
otherwise
-
proc
keyPart
(x: string, i: int): (int(8), uint(8)) Default
keyPart
method for sorting strings. See also The .keyPart method.Note
Currently assumes that the string is local.
Arguments: - x -- the string to sort
- i -- the part number requested
Returns: (0, byte i of string)
or(-1, 0)
ifi > x.size
-
proc
-
record
ReverseComparator
¶ Reverse comparator built from another comparator.
-
var
comparator
¶ Generic comparator defined in initializer.
-
proc
init
()¶ Initializer - builds a comparator with a compare method that reverses the sort order of the default comparator.
-
proc
init
(comparator) Initializer - builds a comparator with a compare method that reverses the sort order of the argument-provided comparator.
Arguments: comparator -- Comparator record that defines how the data is sorted.
-
proc
keyPart
(a, i)¶ Reverses
comparator.keyPart
. See also The .keyPart method.
-
proc
compare
(a, b)¶ Reverses
comparator.compare
. See also The .compare method.
-
var