Implement the Quick Sort algorithm in Dart. Explain the partitioning logic and time complexity. What is the worst-case scenario?

Overview

Quick Sort is a highly efficient, divide-and-conquer sorting algorithm invented by Tony Hoare in 1959. It's one of the most widely used sorting algorithms in practice due to its excellent average-case performance and in-place sorting capability.

Core concept:

1. Choose a "pivot" element
2. Partition array: elements < pivot go left, elements > pivot go right
3. Recursively sort left and right partitions
4. Pivot ends up in its final sorted position

Key characteristics:

• Divide and conquer strategy
• In-place sorting (O(log n) space for recursion)
• Not stable (equal elements may swap order)
• Average: O(n log n), Worst: O(n²)
• Used in many standard libraries (C, Unix)

Real-world applications:

• Dart's
  textCopy

  List.sort()

  uses a hybrid algorithm including quicksort
• Database sorting for indexed queries
• Numerical computations
• File system operations

Algorithm Explanation

Quick Sort Steps:

1. Base case: If array has 0 or 1 element, it's sorted
2. Choose pivot: Select an element (last, first, middle, or random)
3. Partition: Rearrange array so:
   • All elements < pivot are on the left
   • All elements > pivot are on the right
   • Pivot is in its final position
4. Recursively sort: Apply quicksort to left and right partitions

Visual Example:

textCopy
Initial: [5, 2, 9, 1, 7, 6, 3]
Pivot: 3 (last element)

Partition:
  [2, 1] | 3 | [5, 9, 7, 6]

Recurse left [2, 1]:
  [1] | 2 | []

Recurse right [5, 9, 7, 6]:
  [5] | 6 | [9, 7]
  [5] | 6 | [7] | 9 | []

Final: [1, 2, 3, 5, 6, 7, 9]

Partitioning Schemes

Lomuto Partition Scheme (Simpler)

Easier to understand, uses last element as pivot.

dartCopy
int lomutoPartition(List<int> arr, int low, int high) {
  int pivot = arr[high];  // Choose last element as pivot
  int i = low - 1;        // Index of smaller element

  for (int j = low; j < high; j++) {
    // If current element <= pivot
    if (arr[j] <= pivot) {
      i++;
      // Swap arr[i] and arr[j]
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
  }

  // Place pivot in correct position
  int temp = arr[i + 1];
  arr[i + 1] = arr[high];
  arr[high] = temp;

  return i + 1;  // Return pivot index
}

How it works:

• textCopy

  i

  tracks position of last element ≤ pivot
• textCopy

  j

  scans through array
• When element ≤ pivot found, swap to left partition
• Finally, swap pivot to middle

Hoare Partition Scheme (Efficient)

More efficient, uses fewer swaps, invented by Hoare himself.

dartCopy
int hoarePartition(List<int> arr, int low, int high) {
  int pivot = arr[low];  // Choose first element as pivot
  int i = low - 1;
  int j = high + 1;

  while (true) {
    // Find element >= pivot from left
    do {
      i++;
    } while (arr[i] < pivot);

    // Find element <= pivot from right
    do {
      j--;
    } while (arr[j] > pivot);

    // If pointers crossed, partition done
    if (i >= j) {
      return j;
    }

    // Swap arr[i] and arr[j]
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

Advantage: Fewer swaps on average

Approach 1: Quick Sort with Lomuto Partition

Standard implementation using Lomuto scheme.

dartCopy
void quickSort(List<int> arr, [int? low, int? high]) {
  low ??= 0;
  high ??= arr.length - 1;

  if (low < high) {
    // Partition and get pivot index
    int pivotIndex = lomutoPartition(arr, low, high);

    // Recursively sort left and right
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
}

int lomutoPartition(List<int> arr, int low, int high) {
  int pivot = arr[high];
  int i = low - 1;

  for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      _swap(arr, i, j);
    }
  }

  _swap(arr, i + 1, high);
  return i + 1;
}

void _swap(List<int> arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

void main() {
  List<int> numbers = [64, 34, 25, 12, 22, 11, 90];
  print('Before: $numbers');

  quickSort(numbers);
  print('After: $numbers');
  // Output: [11, 12, 22, 25, 34, 64, 90]
}

Time Complexity:

• Best Case: O(n log n) - balanced partitions
• Average Case: O(n log n)
• Worst Case: O(n²) - already sorted, poor pivot choice

Space Complexity: O(log n) - recursion stack for balanced partitions

Approach 2: Quick Sort with Hoare Partition

More efficient version with Hoare scheme.

dartCopy
void quickSortHoare(List<int> arr, [int? low, int? high]) {
  low ??= 0;
  high ??= arr.length - 1;

  if (low < high) {
    int pivotIndex = hoarePartition(arr, low, high);

    // Note: Hoare partition doesn't place pivot in final position
    quickSortHoare(arr, low, pivotIndex);
    quickSortHoare(arr, pivotIndex + 1, high);
  }
}

int hoarePartition(List<int> arr, int low, int high) {
  int pivot = arr[low];
  int i = low - 1;
  int j = high + 1;

  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);

    if (i >= j) return j;

    _swap(arr, i, j);
  }
}

void main() {
  List<int> numbers = [5, 2, 9, 1, 7, 6, 3];
  quickSortHoare(numbers);
  print(numbers);  // [1, 2, 3, 5, 6, 7, 9]
}

Advantage: ~3x fewer swaps than Lomuto on average

Approach 3: Randomized Quick Sort (Avoid Worst Case)

Choose random pivot to avoid O(n²) on sorted data.

dartCopy
import 'dart:math';

void quickSortRandomized(List<int> arr, [int? low, int? high]) {
  low ??= 0;
  high ??= arr.length - 1;

  if (low < high) {
    int pivotIndex = randomizedPartition(arr, low, high);
    quickSortRandomized(arr, low, pivotIndex - 1);
    quickSortRandomized(arr, pivotIndex + 1, high);
  }
}

int randomizedPartition(List<int> arr, int low, int high) {
  // Choose random pivot and swap with last element
  int randomIndex = low + Random().nextInt(high - low + 1);
  _swap(arr, randomIndex, high);

  // Use Lomuto partition
  return lomutoPartition(arr, low, high);
}

void main() {
  List<int> sorted = [1, 2, 3, 4, 5, 6, 7, 8, 9];

  // Deterministic quicksort: O(n²) on sorted data
  quickSort(sorted);

  // Randomized quicksort: O(n log n) expected even on sorted
  quickSortRandomized(sorted);
}

Advantage: Expected O(n log n) even on sorted/reverse sorted data

Approach 4: Three-Way Partition (Handle Duplicates)

Optimized for arrays with many duplicate elements.

dartCopy
void quickSort3Way(List<int> arr, [int? low, int? high]) {
  low ??= 0;
  high ??= arr.length - 1;

  if (low < high) {
    var result = partition3Way(arr, low, high);
    int lt = result[0];  // Less than region end
    int gt = result[1];  // Greater than region start

    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
  }
}

List<int> partition3Way(List<int> arr, int low, int high) {
  int pivot = arr[low];
  int lt = low;       // arr[low..lt-1] < pivot
  int i = low + 1;    // arr[lt..i-1] == pivot
  int gt = high;      // arr[gt+1..high] > pivot

  while (i <= gt) {
    if (arr[i] < pivot) {
      _swap(arr, lt, i);
      lt++;
      i++;
    } else if (arr[i] > pivot) {
      _swap(arr, i, gt);
      gt--;
    } else {
      i++;  // Equal to pivot
    }
  }

  return [lt, gt];
}

void main() {
  List<int> withDuplicates = [3, 1, 3, 2, 3, 1, 3];
  quickSort3Way(withDuplicates);
  print(withDuplicates);  // [1, 1, 2, 3, 3, 3, 3]
}

Advantage: O(n) time when all elements are equal!

Complete Solution Class

Production-ready implementation with all features.

dartCopy
class QuickSort {
  static final Random _random = Random();

  /// Standard quicksort with Lomuto partition
  static void sort(List<int> arr, [int? low, int? high]) {
    low ??= 0;
    high ??= arr.length - 1;

    if (low < high) {
      int pivotIndex = _lomutoPartition(arr, low, high);
      sort(arr, low, pivotIndex - 1);
      sort(arr, pivotIndex + 1, high);
    }
  }

  /// Randomized quicksort (avoid worst case)
  static void sortRandomized(List<int> arr, [int? low, int? high]) {
    low ??= 0;
    high ??= arr.length - 1;

    if (low < high) {
      int pivotIndex = _randomizedPartition(arr, low, high);
      sortRandomized(arr, low, pivotIndex - 1);
      sortRandomized(arr, pivotIndex + 1, high);
    }
  }

  /// Three-way quicksort (handles duplicates)
  static void sort3Way(List<int> arr, [int? low, int? high]) {
    low ??= 0;
    high ??= arr.length - 1;

    if (low < high) {
      var result = _partition3Way(arr, low, high);
      sort3Way(arr, low, result[0] - 1);
      sort3Way(arr, result[1] + 1, high);
    }
  }

  /// Hoare partition (efficient)
  static void sortHoare(List<int> arr, [int? low, int? high]) {
    low ??= 0;
    high ??= arr.length - 1;

    if (low < high) {
      int pivotIndex = _hoarePartition(arr, low, high);
      sortHoare(arr, low, pivotIndex);
      sortHoare(arr, pivotIndex + 1, high);
    }
  }

  // Partition implementations

  static int _lomutoPartition(List<int> arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
      if (arr[j] <= pivot) {
        i++;
        _swap(arr, i, j);
      }
    }

    _swap(arr, i + 1, high);
    return i + 1;
  }

  static int _randomizedPartition(List<int> arr, int low, int high) {
    int randomIndex = low + _random.nextInt(high - low + 1);
    _swap(arr, randomIndex, high);
    return _lomutoPartition(arr, low, high);
  }

  static List<int> _partition3Way(List<int> arr, int low, int high) {
    int pivot = arr[low];
    int lt = low, i = low + 1, gt = high;

    while (i <= gt) {
      if (arr[i] < pivot) {
        _swap(arr, lt++, i++);
      } else if (arr[i] > pivot) {
        _swap(arr, i, gt--);
      } else {
        i++;
      }
    }

    return [lt, gt];
  }

  static int _hoarePartition(List<int> arr, int low, int high) {
    int pivot = arr[low];
    int i = low - 1, j = high + 1;

    while (true) {
      do { i++; } while (arr[i] < pivot);
      do { j--; } while (arr[j] > pivot);
      if (i >= j) return j;
      _swap(arr, i, j);
    }
  }

  static void _swap(List<int> arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

Comparison Table

Pivot Selection Strategies

Visualization Example

Sorting

[5, 2, 9, 1, 7, 6, 3]

dartCopy
void visualize() {
  List<int> arr = [5, 2, 9, 1, 7, 6, 3];
  print('Initial: $arr
');

  print('Partition with pivot=3 (last element):');
  print('  [2, 1] < 3 < [5, 9, 7, 6]');
  print('  After partition: [2, 1, 3, 5, 9, 7, 6]
');

  print('Recurse left [2, 1]:');
  print('  Pivot=1');
  print('  [] < 1 < [2]');
  print('  Result: [1, 2]
');

  print('Recurse right [5, 9, 7, 6]:');
  print('  Pivot=6');
  print('  [5] < 6 < [9, 7]');
  print('  After: [5, 6, 9, 7]
');

  print('Recurse [9, 7]:');
  print('  Pivot=7');
  print('  [] < 7 < [9]');
  print('  Result: [7, 9]
');

  print('Final: [1, 2, 3, 5, 6, 7, 9]');
}

Edge Cases

dartCopy
void testEdgeCases() {
  // Empty array
  List<int> empty = [];
  QuickSort.sort(empty);
  assert(empty.isEmpty);

  // Single element
  List<int> single = [42];
  QuickSort.sort(single);
  assert(single == [42]);

  // Two elements
  List<int> two = [2, 1];
  QuickSort.sort(two);
  assert(two == [1, 2]);

  // Already sorted (worst case for basic quicksort)
  List<int> sorted = [1, 2, 3, 4, 5];
  QuickSort.sortRandomized(sorted);  // Use randomized!
  assert(sorted == [1, 2, 3, 4, 5]);

  // Reverse sorted
  List<int> reverse = [5, 4, 3, 2, 1];
  QuickSort.sort(reverse);
  assert(reverse == [1, 2, 3, 4, 5]);

  // All duplicates
  List<int> duplicates = [3, 3, 3, 3, 3];
  QuickSort.sort3Way(duplicates);  // Use 3-way!
  assert(duplicates == [3, 3, 3, 3, 3]);

  // Some duplicates
  List<int> someDups = [3, 1, 2, 3, 1, 2];
  QuickSort.sort(someDups);
  assert(someDups == [1, 1, 2, 2, 3, 3]);
}

Best Practices

1. Use Randomized Pivot for Production

dartCopy
// ✅ Good - avoids O(n²) on sorted data
QuickSort.sortRandomized(arr);

// ❌ Bad - O(n²) on already sorted arrays
QuickSort.sort(arr);

2. Use 3-Way Partition for Duplicates

dartCopy
// If many duplicates expected
List<int> dataWithDuplicates = [...];
QuickSort.sort3Way(dataWithDuplicates);

3. Consider Alternatives for Small Arrays

dartCopy
// For small arrays (< 10 elements)
if (arr.length < 10) {
  arr.sort();  // Uses insertion sort
} else {
  QuickSort.sortRandomized(arr);
}

4. Know When NOT to Use

dartCopy
// ❌ Don't use basic quicksort on sorted data
List<int> sorted = [1, 2, 3, ...];
QuickSort.sort(sorted);  // O(n²) !!

// ✅ Use Dart's built-in or randomized
sorted.sort();  // TimSort - handles all cases well
QuickSort.sortRandomized(sorted);  // O(n log n) expected

Interview Tips

Common Interview Questions:

Q: "What's the time complexity?"

• Best/Average: O(n log n)
• Worst: O(n²) - when pivot is always min/max
• Space: O(log n) for recursion stack

Q: "What's the worst-case scenario?"

• Already sorted array with poor pivot choice (first/last)
• All elements equal (without 3-way partition)
• Solution: Randomized pivot or median-of-3

Q: "Why is quicksort faster than merge sort in practice?"

• Better cache locality (in-place)
• Fewer data movements
• Lower constant factors

Q: "Is quicksort stable?"

• No! Equal elements may swap positions
• Use merge sort if stability required

Q: "Lomuto vs Hoare partition?"

• Lomuto: Simpler, easier to understand
• Hoare: More efficient, ~3x fewer swaps

Follow-up Questions:

• "How to avoid O(n²)?" → Randomized pivot or median-of-3
• "Handle duplicates efficiently?" → 3-way partition
• "Find kth smallest element?" → QuickSelect algorithm
• "Why not always use merge sort?" → Space overhead, not in-place

What to Explain:

1. Divide-and-conquer strategy
2. Partition process (walk through example)
3. Why average case is O(n log n)
4. Pivot selection matters for performance
5. Recursion tree depth determines space

Red Flags to Avoid:

• Not mentioning worst case O(n²) ❌
• Claiming it's stable ❌
• Not knowing partition schemes ❌
• Forgetting base case in recursion ❌

Pro Tips:

• Draw the partition process
• Explain in-place advantage
• Mention real-world usage (C's qsort, Unix sort)
• Compare with other O(n log n) algorithms
• Discuss practical optimizations (hybrid with insertion sort)

Resources

• Quick Sort - Wikipedia
• Visualizing Quick Sort
• Dart Sorting Implementation