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 with either a key(a) or compare(a, b) method, and pass an instance of that record to the sort function (examples shown below).

If both methods are implemented on the record passed as the comparator, the key(a) method will take priority over the compare(a, b) method.

Key Comparator

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 {
  ...
}

Compare Comparator

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 numeric signed type would 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);

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 constructor 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 default comparator= argument when no comparator is passed to a sort function

const reverseComparator: ReverseComparator(DefaultComparator)

Instance of ReverseComparator. Pass this as the comparator= argument of a sort function to reverse the sort order.

proc sort(Data: [?Dom] ?eltType, comparator: ?rec = defaultComparator)

General purpose sorting interface.

Note

Currently this method calls a sequential quickSort, but this may change the future as other algorithms are implemented.

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 sorted
Return 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 in-place 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.

Arguments:
  • a : eltType -- Array element
  • b : eltType -- Array element
Returns:

1 if b < a
Returns:

0 if a == b
Returns:

-1 if a < b
record ReverseComparator

Reverse comparator built from another comparator.

var comparator

Generic comparator defined in constructor.

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 compare(a, b)

Reversed compare method defined based on comparator.key if defined, otherwise comparator.compare.

Arguments:
  • a : eltType -- Array element
  • b : eltType -- Array element
Returns:

-1 if b < a
Returns:

0 if a == b
Returns:

1 if a < b