Quick Sort Partition Lomuto and Hoare in DSA Go - 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 Lomuto and Hoare partition methods to see how their operations scale.

Scenario Under Consideration

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

// Lomuto partition
func lomutoPartition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

// Hoare partition
func hoarePartition(arr []int, low, high int) int {
    pivot := arr[low]
    i := low - 1
    j := high + 1
    for {
        for {
            i++
            if arr[i] >= pivot {
                break
            }
        }
        for {
            j--
            if arr[j] <= pivot {
                break
            }
        }
        if i >= j {
            return j
        }
        arr[i], arr[j] = arr[j], arr[i]
    }
}
    

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

Identify Repeating Operations

Both partitions use loops to compare and swap elements.

• Primary operation: Comparing elements to the pivot and swapping if needed.
• How many times: Each element between low and high is checked once in Lomuto; in Hoare, pointers move inward checking elements until they cross.

How Execution Grows With Input

As the number of elements (n) increases, the number of comparisons and swaps grows roughly in proportion to n.

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

Pattern observation: The operations increase linearly as input size grows.

Final Time Complexity

Time Complexity: O(n)

This means the partition step takes time proportional to the number of elements it processes.

Common Mistake

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

[OK] Correct: Partitioning compares and swaps many elements, so its time grows with input size, not constant.

Interview Connect

Understanding partition time helps you explain Quick Sort's efficiency and why pivot choice matters.

Self-Check

"What if we used a random pivot instead of fixed ends? How would the partition time complexity change?"