Quick Sort Partition Lomuto and Hoare in DSA C++

Mental Model

Partition rearranges elements around a pivot so smaller go left and bigger go right. Lomuto uses one pointer scanning forward, Hoare uses two pointers scanning inward.

Analogy: Imagine sorting books on a shelf by height. Lomuto picks a book and moves through the shelf placing shorter books to the left and taller to the right. Hoare uses two people starting at each end swapping books that are out of place until they meet in the middle.

Array: [5, 3, 8, 4, 2]
Pivot chosen (Lomuto): 2 (last element)
Pointers:
Lomuto: i and j scanning right
Hoare: i from left, j from right

Initial:
[5, 3, 8, 4, 2]
 i,j -> start

After partition:
[2, 3, 8, 4, 5]
Pivot at correct place

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2]

Goal: Partition the array around a pivot using Lomuto and Hoare methods

Step 1: Lomuto: choose pivot=2 (last element), set i=-1

[5, 3, 8, 4, 2]
i=-1, j=0

Why: Pivot chosen at end; i tracks smaller elements boundary

Step 2: Lomuto: j=0, 5 > 2 no swap, i stays -1

[5, 3, 8, 4, 2]
i=-1, j=0

Why: 5 is bigger than pivot, no change

Step 3: Lomuto: j=1, 3 > 2 no swap, i stays -1

[5, 3, 8, 4, 2]
i=-1, j=1

Why: 3 is bigger than pivot, no change

Step 4: Lomuto: j=2, 8 > 2 no swap, i stays -1

[5, 3, 8, 4, 2]
i=-1, j=2

Why: 8 is bigger than pivot, no change

Step 5: Lomuto: j=3, 4 > 2 no swap, i stays -1

[5, 3, 8, 4, 2]
i=-1, j=3

Why: 4 is bigger than pivot, no change

Step 6: Lomuto: swap pivot with element at i+1 (index 0)

[2, 3, 8, 4, 5]
i=0, pivot index=0

Why: Place pivot in correct position

Step 7: Hoare: choose pivot=5 (first element), i=0, j=4

[5, 3, 8, 4, 2]
i=0, j=4

Why: Pivot chosen at start; i and j scan inward

Step 8: Hoare: i moves right while arr[i]<pivot: i=1 (3<5), i=2 (8>5 stop)

[5, 3, 8, 4, 2]
i=2, j=4

Why: Find element on left bigger than pivot

Step 9: Hoare: j moves left while arr[j]>pivot: j=4 (2<5 stop)

[5, 3, 8, 4, 2]
i=2, j=4

Why: Find element on right smaller than pivot

Step 10: Hoare: swap arr[i] and arr[j]: swap 8 and 2

[5, 3, 2, 4, 8]
i=2, j=4

Why: Put smaller element left, bigger right

Step 11: Hoare: i moves right: i=3 (4<5), i=4 (8>5 stop)

[5, 3, 2, 4, 8]
i=4, j=4

Why: Find next bigger element on left

Step 12: Hoare: j moves left: j=3 (4<5 stop)

[5, 3, 2, 4, 8]
i=4, j=3

Why: Find next smaller element on right

Step 13: Hoare: i >= j stop, partition index = j=3

[5, 3, 2, 4, 8]
i=4, j=3

Why: Pointers crossed, partition done

Result:

Lomuto partitioned array: [2, 3, 8, 4, 5]
Pivot index: 0
Hoare partitioned array: [5, 3, 2, 4, 8]
Partition index: 3

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

// Lomuto partition scheme
int lomuto_partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1; // boundary for smaller elements
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1; // pivot index
}

// Hoare partition scheme
int hoare_partition(vector<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], arr[j]);
    }
}

void print_array(const vector<int>& arr) {
    for (int v : arr) cout << v << " ";
    cout << endl;
}

int main() {
    vector<int> arr1 = {5, 3, 8, 4, 2};
    vector<int> arr2 = arr1; // copy for hoare

    int lomuto_pivot = lomuto_partition(arr1, 0, arr1.size() - 1);
    cout << "Lomuto partitioned array: ";
    print_array(arr1);
    cout << "Pivot index: " << lomuto_pivot << endl;

    int hoare_pivot = hoare_partition(arr2, 0, arr2.size() - 1);
    cout << "Hoare partitioned array: ";
    print_array(arr2);
    cout << "Partition index: " << hoare_pivot << endl;

    return 0;
}

int pivot = arr[high];

select pivot as last element for Lomuto

int i = low - 1;

initialize boundary for smaller elements

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

scan and swap elements smaller or equal to pivot to left

swap(arr[i + 1], arr[high]);

place pivot after smaller elements

int pivot = arr[low];

select pivot as first element for Hoare

int i = low - 1; int j = high + 1;

initialize two pointers outside array bounds

do { i++; } while (arr[i] < pivot);

move i right until element >= pivot

do { j--; } while (arr[j] > pivot);

move j left until element <= pivot

if (i >= j) return j;

stop when pointers cross

swap(arr[i], arr[j]);

swap out-of-place elements

Output

Lomuto partitioned array: 2 3 8 4 5 

Pivot index: 0

Hoare partitioned array: 5 3 2 4 8 

Partition index: 3

Complexity Analysis

Time: O(n) because partition scans the array once comparing and swapping elements

Space: O(1) because partitioning is done in-place without extra arrays

vs Alternative: Both Lomuto and Hoare partition run in linear time, but Hoare often does fewer swaps and can be faster in practice

Edge Cases

empty array

partition returns immediately without changes

DSA C++

for (int j = low; j < high; j++) { ... } in lomuto_partition

array with one element

partition returns the single index as pivot position

DSA C++

int pivot = arr[high]; in lomuto_partition

all elements equal

Lomuto places pivot at end; Hoare pointers cross quickly with minimal swaps

DSA C++

if (arr[j] <= pivot) in lomuto_partition and do-while loops in hoare_partition

When to Use This Pattern

When you see a problem asking to sort or rearrange elements efficiently, recognize the partition step of quicksort and choose Lomuto or Hoare partition schemes to split the array around a pivot.

Common Mistakes

Mistake: Using Lomuto partition but forgetting to swap the pivot at the end
Fix: Always swap the pivot with element at i+1 after scanning to place it correctly

Mistake: In Hoare partition, returning i instead of j when pointers cross
Fix: Return j because it marks the correct partition boundary

Summary

Partitions an array around a pivot so smaller elements go left and larger go right.

Use when implementing quicksort to efficiently divide the array for recursive sorting.

Lomuto uses one pointer scanning forward; Hoare uses two pointers scanning inward and often swaps fewer times.

Practice

1. What is the main difference between Lomuto and Hoare partition schemes in Quick Sort?

easy

A. Lomuto uses a single pointer, Hoare uses two pointers moving inward

B. Lomuto sorts in descending order, Hoare sorts in ascending order

C. Lomuto uses recursion, Hoare uses iteration

D. Lomuto chooses the last element as pivot, Hoare chooses the first element always

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses one pointer to track the boundary of smaller elements and swaps elements accordingly.

2. Step 2: Understand Hoare partition

   Hoare partition uses two pointers starting from both ends moving inward to swap elements around the pivot.

3. Final Answer:

   Lomuto uses a single pointer, Hoare uses two pointers moving inward -> Option A

4. Quick Check:

   Lomuto single pointer, Hoare two pointers inward [OK]

Hint: Remember: Lomuto single pointer, Hoare two pointers inward [OK]

Common Mistakes:

• Confusing pivot selection with partition method
• Thinking both use same pointer approach
• Assuming Hoare always picks first element as pivot

2. Which of the following is the correct Lomuto partition function header in C++?

easy

A. int partition(int arr[], int low, int high)

B. void partition(int arr[], int low, int high)

C. int partition(int arr[], int start, int end, int pivot)

D. bool partition(int arr[], int low, int high)

Solution

1. Step 1: Check return type

   Lomuto partition returns the pivot index as int after partitioning.

2. Step 2: Check parameters

   It takes array, low index, and high index as parameters to partition the subarray.

3. Final Answer:

   int partition(int arr[], int low, int high) -> Option A

4. Quick Check:

   Returns int pivot index, low high params [OK]

Hint: Partition returns pivot index as int with low and high params [OK]

Common Mistakes:

• Using void return type instead of int
• Adding extra pivot parameter unnecessarily
• Returning bool instead of pivot index

3. What is the output array after applying Lomuto partition on arr = [8, 3, 7, 6, 2] with low=0 and high=4?

medium

A. [2, 3, 6, 7, 8]

B. [3, 2, 7, 6, 8]

C. [8, 3, 7, 6, 2]

D. [2, 3, 7, 6, 8]

Solution

1. Step 1: Choose pivot and initialize pointers

   Pivot = arr[4] = 2, i = -1 initially.

2. Step 2: Iterate and swap smaller elements

   Check elements from index 0 to 3:
   - arr[0]=8 > 2 no swap
   - arr[1]=3 > 2 no swap
   - arr[2]=7 > 2 no swap
   - arr[3]=6 > 2 no swap
   After loop, swap arr[i+1]=arr[0] and pivot arr[4].

3. Final Answer:

   [2, 3, 7, 6, 8] -> Option D

4. Quick Check:

   Pivot swapped to front since no smaller elements [OK]

Hint: Pivot last element, swap smaller left, pivot final swap [OK]

Common Mistakes:

• Swapping elements incorrectly during iteration
• Confusing pivot position after partition
• Assuming pivot is first element

4. Identify the bug in this Hoare partition code snippet:

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]);
  }
}

medium

A. Initialization of i and j is incorrect

B. No bug, code is correct

C. The loop condition should be i > j instead of i >= j

D. Pivot should be arr[high], not arr[low]

Solution

1. Step 1: Verify pointer initialization

   In standard Hoare partition, i starts at low-1 and j at high+1 to work with the do-while loops correctly.

2. Step 2: Check other parts

   Pivot selection arr[low], movement conditions arr[i] < pivot and arr[j] > pivot, i >= j return, and swap are all correct.

3. Final Answer:

   No bug, code is correct -> Option B

4. Quick Check:

   Standard Hoare uses i=low-1, j=high+1 [OK]

Hint: i starts at low, j at high in Hoare partition [OK]

Common Mistakes:

• Setting i and j outside array bounds
• Confusing pivot position with pointer initialization
• Misusing loop exit condition

5. Given the array [10, 80, 30, 90, 40, 50, 70], after applying Hoare partition with low=0 and high=6, what is the resulting array?

hard

A. [10, 30, 40, 50, 70, 90, 80]

B. [10, 30, 40, 50, 90, 80, 70]

C. [10, 80, 30, 90, 40, 50, 70]

D. [10, 30, 40, 50, 80, 70, 90]

Solution

1. Step 1: Set pivot and pointers

   Pivot = arr[0] = 10, i = low - 1 = -1, j = high + 1 = 7.

2. Step 2: Move pointers and check swaps

   do {i++;} while (arr[i] < 10): i=0, arr[0]=10 not <10, stop i=0.
   do {j--;} while (arr[j] > 10): j=6(70>10),5(50>10),4(40>10),3(90>10),2(30>10),1(80>10),0(10 not >10), stop j=0.
   i=0 < j=0 is false, so i >= j, return j=0, no swap.
   But since i == j, partition ends with pivot index 0.
   However, this means no swaps, so array remains same.

3. Step 3: Re-examine pointer movement

   Actually, the do-while loops stop at i=0 and j=0, so no swaps occur.
   Therefore, the array remains unchanged.

4. Final Answer:

   [10, 80, 30, 90, 40, 50, 70] -> Option C

5. Quick Check:

   All elements ≥ pivot, array unchanged [OK]

Hint: Track i and j moving inward, swap when i < j [OK]

Common Mistakes:

• Swapping after pointers cross
• Misplacing pivot after partition
• Confusing Hoare with Lomuto output