quickSort<T>

A generic implementation of the Quick Sort algorithm that can sort any list of comparable elements using a divide-and-conquer strategy.

Function Signature

List<T> quickSort<T extends Comparable<T>>(List<T> list)

Parameters

• list: A list of elements of type T that implements the Comparable interface

Return Value

• Returns the sorted list of type List<T>

Type Parameters

• T extends Comparable<T>: The type parameter T must implement the Comparable interface to ensure elements can be compared

Complexity Analysis

Time Complexity

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n²) - When the pivot selection consistently results in the most unbalanced partition

Space Complexity

• O(log n) - Due to the recursive call stack

Implementation

List<T> quickSort<T extends Comparable<T>>(List<T> list) {
  if (list.length <= 1) return list;

  final pivot = list[list.length ~/ 2];
  final less = list.where((element) => element.compareTo(pivot) < 0).toList();
  final equal = list.where((element) => element.compareTo(pivot) == 0).toList();
  final greater =
      list.where((element) => element.compareTo(pivot) > 0).toList();

  return [...quickSort(less), ...equal, ...quickSort(greater)];
}

Implementation Details

1. Function Declaration:

   • The function is generic, accepting any type T that implements Comparable<T>
   • Takes a single parameter list of type List<T>
   • Returns a sorted list of the same type

2. Algorithm Steps:

   • Checks if the list length is 1 or less (base case)
   • Selects a pivot element (middle element)
   • Partitions elements into three lists: less than, equal to, and greater than the pivot
   • Recursively sorts the sub-arrays
   • Combines the sorted results

Example Usage

void main() {
  // Sorting integers
  var numbers = [64, 34, 25, 12, 22, 11, 90];
  print('Original list: $numbers');
  var sortedNumbers = quickSort(numbers);
  print('Sorted list: $sortedNumbers');

  // Sorting strings
  var fruits = ['banana', 'apple', 'orange', 'grape'];
  print('Original list: $fruits');
  var sortedFruits = quickSort(fruits);
  print('Sorted list: $sortedFruits');
}

Output

Original list: [64, 34, 25, 12, 22, 11, 90]
Sorted list: [11, 12, 22, 25, 34, 64, 90]

Original list: [banana, apple, orange, grape]
Sorted list: [apple, banana, grape, orange]

Usage Notes

1. Type Constraints:

   • The type T must implement Comparable<T>
   • Built-in types like int, double, and String already implement Comparable
   • Custom classes must implement Comparable interface to be sorted

2. Performance Considerations:

   • Efficient for large datasets
   • Average case time complexity of O(n log n)
   • Performance depends on pivot selection strategy

3. Stability:

   • Not a stable sorting algorithm
   • Does not preserve the relative order of equal elements
   • May produce different orderings of equal elements across multiple sorts