Quick Sort Partition Lomuto and Hoare in DSA C++ - Time & Space Complexity

Time Complexity: Quick Sort Partition Lomuto and Hoare

O(n)

Understanding Time Complexity

We want to understand how the time taken by Quick Sort's partition steps grows as the input size increases.

Specifically, we compare two partition methods: Lomuto and Hoare.

Scenario Under Consideration

Analyze the time complexity of these two partition functions used in Quick Sort.

// Lomuto Partition
int lomutoPartition(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++;
      std::swap(arr[i], arr[j]);
    }
  }
  std::swap(arr[i + 1], arr[high]);
  return i + 1;
}

// Hoare Partition
int hoarePartition(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;
    std::swap(arr[i], arr[j]);
  }
}
    

These functions rearrange elements around a pivot to help Quick Sort divide the array.

Identify Repeating Operations

Both partitions scan parts of the array repeatedly:

• Primary operation: Comparing elements to the pivot and swapping.
• How many times: Each element in the current segment is checked once or twice.

How Execution Grows With Input

As the segment size n grows, the number of comparisons and swaps grows roughly in proportion.

Input Size (n)	Approx. Operations
10	About 10 comparisons and a few swaps
100	About 100 comparisons and swaps
1000	About 1000 comparisons and swaps

Pattern observation: Operations grow linearly with input size for each partition call.

Final Time Complexity

Time Complexity: O(n) per partition call

This means the partition step looks at each element once or twice, so time grows directly with the number of elements.

Common Mistake

[X] Wrong: "Partitioning takes constant time because it just picks a pivot."

[OK] Correct: Partitioning must compare and possibly swap many elements, so it takes time proportional to the segment size, not a fixed small time.

Interview Connect

Understanding partition time helps you explain Quick Sort's efficiency and why pivot choice matters, a key skill in interviews.

Self-Check

"What if the pivot is always the smallest or largest element? How would that affect the time complexity of partition and overall Quick Sort?"