quickSelect<T> function

dynamic quickSelect<T>(List<T> arr, int k, [ int left = 0, int? right, Comparator<T>? compare, ])

This function implements a fast selection algorithm (specifically, Floyd-Rivest selection).

Rearranges items so that all items in the [left, k] are the smallest. The k-th element will have the (k - left + 1)-th smallest value in [left, right].

• arr: the list to partially sort (in place)
• k: middle index for partial sorting (as defined above)
• left: left index of the range to sort (0 by default)
• right: right index (last index of the array by default)
• compare: compare function, if items in the list are not Comparable.

Example:

var arr = [65, 28, 59, 33, 21, 56, 22, 95, 50, 12, 90, 53, 28, 77, 39];

quickSelect(arr, 8);

// arr is [39, 28, 28, 33, 21, 12, 22, 50, 53, 56, 59, 65, 90, 77, 95]
//                                         ^^ middle index

Implementation

quickSelect<T>(List<T> arr, int k,
    [int left = 0, int? right, Comparator<T>? compare]) {
  if (arr.isEmpty) return;
  if (compare == null && arr.first is! Comparable) {
    throw ArgumentError(
        'Please either provide a comparator or use a list of Comparable elements.');
  }
  _quickSelectStep(arr, k, left, right ?? arr.length - 1,
      compare ?? (T a, T b) => (a as Comparable).compareTo(b));
}