quickSortLomuto<E> function

void quickSortLomuto<E>(
  1. List<E> list, {
  2. int? begin,
  3. int? end,
  4. Comparator<E>? compare,
  5. int threshold = 32,
})

Sorts the list of numbers using the quicksort algorithm following Lomuto partition scheme with several optimizations.

Parameters

  • list is any list of items to be sorted.
  • To perform partial sorting, you can specify the begin or end.
  • begin is the start index of the range to be sorted.
  • If begin is negative, range starts at the 0
  • If begin is not below the length of the list, range will be empty.
  • end is the final index if the range to be sorted. It is exclusive.
  • If end is above the length of the list, it will be ignored.
  • If end is negative, the absolute value of it will be subtracted from the length of the list to determine where the range ends.
  • If end is not greater than the begin, the range will be empty.
  • compare is a custom compare to order the list elements. If it is null and list items are not Comparable, TypeError is thrown.
  • threshold is the maximum limit for which a range can be sorted using insertion sort.

Optimizations

  1. Using iterative approach to avoid recursion. (function calls are slow)
  2. Keeping stack smaller by tail-call optimization. (reduces memory usage)
  3. Use insertion sort on smaller ranges. (configurable by threshold parameter)
  4. Following Sedwick's optimization and using median-of-3 to choose the pivot. (avoiding worst-case performance on already sorted list)
  5. Exclude items equal to the pivot to avoid worst-case performance on list with repeatitive items.
  6. Keeping separate logic for when compare function is provided or not.

Details

Quicksort is a type of divide and conquer algorithm for sorting an array, based on a partitioning routine; the details of this partitioning can vary somewhat, so that quicksort is really a family of closely related algorithms.

Lomuto scheme is attributed to Nico Lomuto. This scheme chooses a pivot that is typically the last element in the array. The algorithm maintains a temporary pivot index p as it scans the array using another index i such that the elements at l through i-1 (inclusive) are less than the pivot, and the elements at i through p (inclusive) are equal to or greater than the pivot.

This scheme degrades to O(n^2) when the list is already sorted, or items are repetitive, but some optimizations can be done to overcome that. Still this is less efficient than Haore's original scheme implemented in quickSortHaore.

Complexity: Time O(n log n) | Space O(log n)
Worst-case: Time O(n^2) | Space O(log n)

Implementation

void quickSortLomuto<E>(
  List<E> list, {
  int? begin,
  int? end,
  Comparator<E>? compare,
  int threshold = 32,
}) {
  int b, e;
  int n = list.length;

  // Find the range given the parameters.
  b = 0;
  e = n;
  if (begin != null && b < begin) {
    b = begin;
  }
  if (end != null && end < e) {
    e = end;
    if (e < 0) e += n;
  }

  // If the range has less than two items, returns immediately.
  if (b + 1 >= e) return;

  if (compare == null) {
    quickSortDefault(list, b, e, threshold);
  } else {
    quickSortCustom(list, b, e, threshold, compare);
  }
}