Quick Sort Partition Lomuto and Hoare in DSA Java

Mental Model

Partition divides an array into two parts around a pivot so smaller values go left and larger go right. Lomuto and Hoare are two ways to do this.

Analogy: Imagine sorting books on a shelf by height. You pick one book as a pivot and move shorter books to the left and taller books to the right, using two different ways to swap them.

Array before partition:
[7, 2, 1, 6, 8, 5, 3, 4]
Pivot chosen (last element for Lomuto): 4
Indexes:
Lomuto: i = -1, j = 0 -> 7, 2, 1, 6, 8, 5, 3, [4]
Hoare: left = 0 ↑, right = 7 ↓, pivot = 4

Dry Run Walkthrough

Input: array: [7, 2, 1, 6, 8, 5, 3, 4]

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

Step 1: Lomuto: start with i = -1, j = 0; compare arr[j] with pivot 4

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

Why: We scan from left to right to find elements smaller than pivot

Step 2: Lomuto: arr[j]=7 > 4, no swap, j++

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

Why: 7 is bigger than pivot, so we skip

Step 3: Lomuto: arr[j]=2 < 4, increment i to 0, swap arr[i] and arr[j]

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

Why: 2 is smaller than pivot, move it to left side

Step 4: Lomuto: arr[j]=1 < 4, increment i to 1, swap arr[i] and arr[j]

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

Why: 1 is smaller than pivot, move it left

Step 5: Lomuto: arr[j]=6 > 4, no swap, j++

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

Why: 6 is bigger than pivot, skip

Step 6: Lomuto: arr[j]=8 > 4, no swap, j++

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

Why: 8 is bigger than pivot, skip

Step 7: Lomuto: arr[j]=5 > 4, no swap, j++

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

Why: 5 is bigger than pivot, skip

Step 8: Lomuto: arr[j]=3 < 4, increment i to 2, swap arr[i] and arr[j]

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

Why: 3 is smaller than pivot, move it left

Step 9: Lomuto: swap pivot arr[7] with arr[i+1] arr[3]

[2, 1, 3, 4, 8, 5, 7, 6]

Why: Place pivot in correct position

Step 10: Hoare: left=0, right=7, pivot=4; move left until arr[left]>=pivot

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

Why: Find element on left side that should be on right

Step 11: Hoare: arr[left]=7 >= 4 stop; move right until arr[right]<=pivot

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

Why: Find element on right side that should be on left

Step 12: Hoare: arr[right]=4 <= 4 stop; swap arr[left] and arr[right]

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

Why: Swap misplaced elements

Step 13: Hoare: increment left to 1; decrement right to 6

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

Why: Continue scanning

Step 14: Hoare: arr[left]=2 < 4 increment left to 2

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

Why: 2 is on correct side

Step 15: Hoare: arr[left]=1 < 4 increment left to 3

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

Why: 1 is on correct side

Step 16: Hoare: arr[left]=6 >= 4 stop; arr[right]=3 <= 4 stop; swap arr[left] and arr[right]

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

Why: Swap misplaced elements

Step 17: Hoare: increment left to 4; decrement right to 5

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

Why: Continue scanning

Step 18: Hoare: arr[left]=8 >= 4 stop; arr[right]=5 >= 4 decrement right to 4

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

Why: Find element on right side smaller than pivot

Step 19: Hoare: left >= right stop partitioning

[4, 2, 1, 3, 8, 5, 6, 7]

Why: Partition complete

Result:

Lomuto partitioned array: [2, 1, 3, 4, 8, 5, 7, 6]
Hoare partitioned array: [4, 2, 1, 3, 8, 5, 6, 7]

Annotated Code

DSA Java

public class QuickSortPartition {

    // Lomuto partition scheme
    public static 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++;
                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
    public static int hoarePartition(int[] arr, int low, int high) {
        int pivot = arr[low];
        int left = low - 1;
        int right = high + 1;
        while (true) {
            do {
                left++;
            } while (arr[left] < pivot);
            do {
                right--;
            } while (arr[right] > pivot);
            if (left >= right) {
                return right;
            }
            int temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
        }
    }

    public static void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arrLomuto = {7, 2, 1, 6, 8, 5, 3, 4};
        int[] arrHoare = {7, 2, 1, 6, 8, 5, 3, 4};

        int lomutoIndex = lomutoPartition(arrLomuto, 0, arrLomuto.length - 1);
        System.out.print("Lomuto partitioned array: ");
        printArray(arrLomuto);
        System.out.println("Pivot index: " + lomutoIndex);

        int hoareIndex = hoarePartition(arrHoare, 0, arrHoare.length - 1);
        System.out.print("Hoare partitioned array: ");
        printArray(arrHoare);
        System.out.println("Partition index: " + hoareIndex);
    }
}

int pivot = arr[high];

select pivot as last element for Lomuto

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

scan array, move smaller elements left

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

place pivot after smaller elements

int pivot = arr[low];

select pivot as first element for Hoare

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

move left and right pointers to find misplaced elements

if (left >= right) return right;

stop when pointers cross

swap arr[left] and arr[right];

swap misplaced elements

Output

Lomuto partitioned array: 2 1 3 4 8 5 7 6 

Pivot index: 3

Hoare partitioned array: 4 2 1 3 8 5 6 7 

Partition index: 3

Complexity Analysis

Time: O(n) because each partition scans the array once with pointer moves

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

vs Alternative: Both Lomuto and Hoare partition run in linear time; Hoare usually does fewer swaps and can be faster in practice

Edge Cases

empty array

partition returns immediately without changes

DSA Java

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

array with one element

partition returns the single index, array unchanged

DSA Java

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

all elements equal

partition keeps array unchanged, pivot index returned correctly

DSA Java

if (arr[j] < pivot) condition in lomutoPartition

When to Use This Pattern

When you need to sort an array quickly and must split it around a pivot, recognize the partition step and choose Lomuto or Hoare scheme to rearrange elements efficiently.

Common Mistakes

Mistake: Using wrong pivot index or not swapping pivot correctly in Lomuto
Fix: Always swap pivot with element at i+1 after scanning

Mistake: In Hoare, stopping partition when left > right instead of left >= right
Fix: Use left >= right condition to stop partitioning

Summary

It rearranges an array so elements smaller than a pivot come before it and larger come after.

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

The key insight is how pointers move and swap elements differently in Lomuto and Hoare to achieve partition.

Practice

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

easy

A. Lomuto uses one 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 swaps only once, Hoare swaps multiple times

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 out of place.

3. Final Answer:

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

4. Quick Check:

   Pointer count difference [OK]

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

Common Mistakes:

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

2. Which of the following is the correct syntax to swap elements at indices i and j in Java array arr?

easy

A. int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

B. arr[i], arr[j] = arr[j], arr[i];

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

D. arr.swap(i, j);

Solution

1. Step 1: Identify Java swap syntax

   Java does not support tuple unpacking or built-in swap method for arrays, so manual swap using a temporary variable is needed.

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temporary variable to swap correctly; others are invalid Java syntax.

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option A

4. Quick Check:

   Manual swap with temp variable [OK]

Hint: Use temp variable to swap array elements in Java [OK]

Common Mistakes:

• Using Python-style tuple swap
• Calling non-existent swap method
• Trying to swap without temp variable

3. What is the output array after applying Lomuto partition on arr = [8, 3, 7, 6, 2] with pivot as last element?

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: Identify pivot and initialize pointers

   Pivot is last element 2. Initialize i = -1.

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

   Check elements: 8 > 2 no swap; 3 > 2 no swap; 7 > 2 no swap; 6 > 2 no swap. Then swap pivot with element at i+1 (index 0): swap arr[0] and arr[4].

3. Final Answer:

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

4. Quick Check:

   Lomuto partition output [OK]

Hint: Pivot last element, swap smaller left, pivot to i+1 [OK]

Common Mistakes:

• Not swapping pivot at end
• Confusing pivot position
• Swapping elements incorrectly

4. Find the error in this Hoare partition code snippet:

int hoarePartition(int[] arr, int low, int high) {
  int pivot = arr[low];
  int i = low + 1, j = high;
  while (true) {
    while (i <= high && arr[i] < pivot) i++;
    while (j >= low && arr[j] > pivot) j--;
    if (i >= j) break;
    int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
  }
  int temp = arr[low]; arr[low] = arr[j]; arr[j] = temp;
  return j;
}

medium

A. Pointers i and j initialization is incorrect

B. Pivot should be last element, not first

C. The inner while conditions should use <= and >= incorrectly

D. No error, code is correct

Solution

1. Step 1: Check pointer initialization

   In Hoare partition, i starts at low + 1 and j at high, which is a valid approach.

2. Step 2: Analyze pointer movement and swapping

   The code correctly moves pointers inward and swaps elements until i >= j, then swaps pivot with arr[j].

3. Final Answer:

   No error, code is correct -> Option D

4. Quick Check:

   Pointer start positions and loop logic [OK]

Hint: Hoare pointers start inside range: i=low+1, j=high [OK]

Common Mistakes:

• Starting pointers outside array incorrectly
• Using wrong pivot position
• Misplacing swap after loop

5. Given array arr = [5, 3, 8, 4, 2, 7, 1, 10], after applying Hoare partition with pivot as first element, what is the correct partitioned array?

hard

A. [1, 3, 2, 4, 5, 7, 8, 10]

B. [2, 3, 1, 4, 5, 7, 8, 10]

C. [1, 2, 3, 4, 5, 7, 8, 10]

D. [5, 3, 8, 4, 2, 7, 1, 10]

Solution

1. Step 1: Initialize pointers and pivot

   Pivot = 5 (first element), i = low - 1 = -1, j = high + 1 = 8.

2. Step 2: Move pointers and swap

   i moves right skipping elements < 5: i=0(5), stop; j moves left skipping elements > 5: j=7(10),6(1 stop at 1). Swap arr[i]=5 and arr[j]=1. Array becomes [1,3,8,4,2,7,5,10]. Continue until i >= j.

3. Step 3: Final partitioned array

   After all swaps, array is [2, 3, 1, 4, 5, 7, 8, 10] with pivot index at 4.

4. Final Answer:

   [2, 3, 1, 4, 5, 7, 8, 10] -> Option B

5. Quick Check:

   Hoare partition swaps around pivot [OK]

Hint: Hoare swaps elements crossing pointers around pivot [OK]

Common Mistakes:

• Confusing pivot position after partition
• Not swapping correctly when pointers cross
• Assuming sorted order after one partition