Quick Sort Partition Lomuto and Hoare in DSA C

Mental Model

Partition splits an array into parts so smaller values go left and bigger go right around a pivot.

Analogy: Imagine sorting books on a shelf by height: pick one book as a reference, then move shorter books to the left side and taller books to the right side.

Array: [5, 3, 8, 4, 2]
Pivot chosen -> 2 (Lomuto) or 5 (Hoare)
Indices:
Lomuto: i and j pointers moving through array
Hoare: left and right pointers moving inward

Initial:
[5, 3, 8, 4, 2]
 ↑           ↑
 left       right

Dry Run Walkthrough

Input: array: [5, 3, 8, 4, 2], partition using Lomuto and Hoare

Goal: Rearrange array so elements less than pivot are left, greater are right, and find pivot final position

Step 1: Lomuto: choose last element 2 as pivot, start i at -1, j at 0

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

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

Step 2: Lomuto: j=0 (5) > pivot(2), no swap, j moves to 1

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

Why: 5 is bigger than pivot, so it stays right

Step 3: Lomuto: j=1 (3) > pivot(2), no swap, j moves to 2

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

Why: 3 is bigger than pivot, stays right

Step 4: Lomuto: j=2 (8) > pivot(2), no swap, j moves to 3

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

Why: 8 bigger than pivot, stays right

Step 5: Lomuto: j=3 (4) > pivot(2), no swap, j moves to 4

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

Why: 4 bigger than pivot, stays right

Step 6: Lomuto: j reached end, swap pivot(2) with element at i+1 (index 0)

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

Why: Place pivot in correct position after smaller elements

Step 7: Hoare: choose pivot as first element 5, left=0, right=4

[5, 3, 8, 4, 2]
left=0, right=4, pivot=5

Why: Pivot chosen at start; pointers move inward

Step 8: Hoare: move right pointer left while arr[right] > pivot: arr[4]=2 <=5 stop

[5, 3, 8, 4, 2]
left=0, right=4

Why: Find element smaller or equal to pivot from right

Step 9: Hoare: move left pointer right while arr[left] < pivot: arr[0]=5 not <5 stop

[5, 3, 8, 4, 2]
left=0, right=4

Why: Find element bigger or equal to pivot from left

Step 10: Hoare: left(0) < right(4), swap arr[left] and arr[right]

[2, 3, 8, 4, 5]
left=0, right=4

Why: Swap to put smaller on left and bigger on right

Step 11: Hoare: increment left to 1, decrement right to 3

[2, 3, 8, 4, 5]
left=1, right=3

Why: Move pointers inward to continue partition

Step 12: Hoare: move right pointer left while arr[right] > pivot: arr[3]=4 <5 stop

[2, 3, 8, 4, 5]
left=1, right=3

Why: Find element smaller or equal to pivot from right

Step 13: Hoare: move left pointer right while arr[left] < pivot: arr[1]=3 <5 left=2; arr[2]=8 >5 stop

[2, 3, 8, 4, 5]
left=2, right=3

Why: Find element bigger or equal to pivot from left

Step 14: Hoare: left(2) < right(3), swap arr[left] and arr[right]

[2, 3, 4, 8, 5]
left=2, right=3

Why: Swap to put smaller on left and bigger on right

Step 15: Hoare: increment left to 3, decrement right to 2

[2, 3, 4, 8, 5]
left=3, right=2

Why: Pointers crossed, partition done

Result:

Lomuto partition result: [2, 3, 8, 4, 5], pivot index = 0
Hoare partition result: [2, 3, 4, 8, 5], partition index between 2 and 3

Annotated Code

DSA C

#include <stdio.h>

// Lomuto partition scheme
int lomuto_partition(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++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

// Hoare partition scheme
int hoare_partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int left = low - 1;
    int right = high + 1;
    while (1) {
        do {
            right--;
        } while (arr[right] > pivot);
        do {
            left++;
        } while (arr[left] < pivot);
        if (left < right) {
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        } else {
            return right;
        }
    }
}

void print_array(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", arr[i]);
        if (i < size - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int arr1[] = {5, 3, 8, 4, 2};
    int size1 = sizeof(arr1) / sizeof(arr1[0]);
    int pivot_index = lomuto_partition(arr1, 0, size1 - 1);
    printf("Lomuto partition result: ");
    print_array(arr1, size1);
    printf("Pivot index: %d\n", pivot_index);

    int arr2[] = {5, 3, 8, 4, 2};
    int size2 = sizeof(arr2) / sizeof(arr2[0]);
    int partition_index = hoare_partition(arr2, 0, size2 - 1);
    printf("Hoare partition result: ");
    print_array(arr2, size2);
    printf("Partition index: %d\n", partition_index);

    return 0;
}

int pivot = arr[high];

choose pivot as last element (Lomuto)

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

move elements smaller or equal to pivot to left side

swap arr[i+1] and arr[high]; return i+1;

place pivot after smaller elements and return pivot index

int pivot = arr[low];

choose pivot as first element (Hoare)

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

move right pointer left to find element <= pivot

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

move left pointer right to find element >= pivot

if (left < right) swap arr[left] and arr[right]; else return right;

swap elements or return partition index when pointers cross

Output

Lomuto partition result: 2 -> 3 -> 8 -> 4 -> 5 -> null

Pivot index: 0

Hoare partition result: 2 -> 3 -> 4 -> 8 -> 5 -> null

Partition index: 2

Complexity Analysis

Time: O(n) because each partition scans the array segment once

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

vs Alternative: Compared to naive sorting, partitioning is faster as it rearranges elements in one pass without full sorting

Edge Cases

empty array

partition returns immediately without changes

DSA C

for (int j = low; j < high; j++) { ... } handles no iterations if low >= high

array with all equal elements

all elements stay in place, pivot ends up at last (Lomuto) or middle (Hoare)

DSA C

if (arr[j] <= pivot) condition includes equality to handle duplicates

array with one element

partition returns the single element index without swaps

DSA C

for loop does not run if low == high

When to Use This Pattern

When you need to sort or rearrange an array quickly by dividing it around a pivot, use quicksort partition patterns like Lomuto or Hoare to efficiently split the array.

Common Mistakes

Mistake: Using wrong pivot index or swapping pivot too early in Lomuto
Fix: Always swap pivot after scanning all elements to place it correctly

Mistake: In Hoare, not moving pointers correctly causing infinite loop
Fix: Ensure pointers move inside do-while loops and swap only when left < right

Summary

It rearranges an array segment so elements less than pivot come before it and greater come after.

Use it when implementing quicksort to efficiently split arrays for recursive sorting.

The key insight is choosing a pivot and moving pointers to swap elements around it in one pass.

Practice

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

easy

A. Lomuto uses recursion, Hoare uses iteration

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

C. Lomuto uses one pointer, Hoare uses two pointers moving inward

D. Lomuto swaps only equal elements, Hoare swaps all elements

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses a single 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 that are on the wrong side.

3. Final Answer:

   Lomuto uses one pointer, Hoare uses two pointers moving inward -> Option C

4. Quick Check:

   Pointer count difference = A [OK]

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

Common Mistakes:

• Confusing sorting order difference
• Thinking both use same pointer method
• Assuming Hoare uses recursion only

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

easy

A. int lomutoPartition(int arr[], int low, int high);

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

C. int lomutoPartition(int arr, int low, int high);

D. int lomutoPartition(int arr[], int high, int low);

Solution

1. Step 1: Check parameter types

   Array must be passed as int arr[], and low and high as int indices.

2. Step 2: Check return type

   Lomuto partition returns an int index, so return type must be int.

3. Final Answer:

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

4. Quick Check:

   Correct signature = A [OK]

Hint: Partition returns index, so return type is int [OK]

Common Mistakes:

• Using void return type instead of int
• Passing array as int arr instead of int arr[]
• Swapping low and high parameters

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. [8, 3, 7, 6, 2]

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

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

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

Solution

1. Step 1: Choose pivot and initialize pointers

   Pivot is arr[high] = 2. Initialize i = low - 1 = -1.

2. Step 2: Iterate and swap elements smaller than pivot

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

3. Final Answer:

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

4. Quick Check:

   Pivot 2 placed at start = A [OK]

Hint: Pivot is last element in Lomuto [OK]

Common Mistakes:

• Swapping elements incorrectly with pivot
• Using wrong pivot index
• Confusing i and j pointers

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 (1) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);
    if (i >= j) return j;
    swap(&arr[i], &arr[j]);
  }
}

medium

A. Return statement should be i, not j

B. Swap function is missing

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

D. Pointers i and j are initialized incorrectly

Solution

1. Step 1: Examine the swap call

   The code calls swap(&arr[i], &arr[j]); but the swap function is not defined in the snippet, causing a compilation error.

2. Step 2: Verify other components

   Pointer initialization i=low-1, j=high+1 is correct for do-while structure; pivot at low ok; return j standard.

3. Final Answer:

   Swap function is missing -> Option B

4. Quick Check:

   Undefined swap function = C [OK]

Hint: Swap must be defined before calling [OK]

Common Mistakes:

• Missing swap function definition
• Confusing Hoare pointer initialization
• Returning wrong index after partition

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

hard

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

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

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

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

Solution

1. Step 1: Initialize pointers and pivot

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

2. Step 2: Move pointers

   do { i++; } while (arr[i] < 10); i++ to 0, arr[0]=10 not < 10, i=0.
   do { j--; } while (arr[j] > 10); j-- from 7: 6(70>10),5(50>10),4(40>10),3(90>10),2(30>10),1(80>10),0(10 not >10), j=0.
   i=0 >= j=0, return 0. No swap.

3. Final Answer:

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

4. Quick Check:

   Array unchanged (all ≥ pivot) = D [OK]

Hint: Hoare partition swaps inward until pointers cross [OK]

Common Mistakes:

• Assuming full sort after one partition
• Confusing pivot position after partition
• Mis-tracing pointer movements