Quick Sort Partition Lomuto and Hoare in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Lomuto Partition on Array

What is the output array after applying Lomuto partition on the given array with pivot as last element?

DSA Java

int[] arr = {8, 3, 7, 6, 2};
int pivotIndex = lomutoPartition(arr, 0, arr.length - 1);
System.out.print(java.util.Arrays.toString(arr));
System.out.print(", pivotIndex=" + pivotIndex);

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

A [2, 3, 7, 6, 8], pivotIndex=0

B [2, 3, 6, 8, 7], pivotIndex=3

C [3, 2, 6, 7, 8], pivotIndex=1

D [2, 3, 6, 7, 8], pivotIndex=2

💡 Hint

Remember Lomuto places pivot at correct position with smaller elements to left.

Lomuto partition moves all elements smaller or equal to pivot to left, then places pivot after them. Here pivot=2, so after partition, 2 is at index 0 with smaller or equal elements before it.

❓ Predict Output

intermediate

Output of Hoare Partition on Array

What is the output array and returned pivot index after applying Hoare partition on the array?

DSA Java

int[] arr = {9, 4, 8, 3, 7};
int pivotIndex = hoarePartition(arr, 0, arr.length - 1);
System.out.print(java.util.Arrays.toString(arr));
System.out.print(", pivotIndex=" + pivotIndex);

public static int hoarePartition(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;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

A [4, 3, 7, 8, 9], pivotIndex=1

B [3, 4, 8, 7, 9], pivotIndex=3

C [3, 4, 7, 9, 8], pivotIndex=2

D [7, 4, 3, 8, 9], pivotIndex=2

💡 Hint

Hoare partition uses first element as pivot and swaps elements crossing pointers.

Hoare partition swaps elements to ensure left side less than pivot and right side greater. The pivot is arr[0]=9, after partition smaller elements move left. The returned index is where pointers cross.

🔧 Debug

advanced

Identify the error in Lomuto partition code snippet

Which option correctly identifies the error in this Lomuto partition code snippet?

DSA Java

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

A Pivot should be arr[low], not arr[high]

B Initialization of i should be low - 1, not low

C The for loop should run until j <= high, not j < high

D Swap after the loop should be between arr[i+1] and arr[high]

💡 Hint

Check how i is initialized and incremented in Lomuto partition.

In Lomuto partition, i starts at low - 1 to track last smaller element index. Starting at low causes incorrect partitioning.

❓ Predict Output

advanced

Result of Hoare Partition on Sorted Array

What is the output array and pivot index after applying Hoare partition on a sorted array?

DSA Java

int[] arr = {1, 2, 3, 4, 5};
int pivotIndex = hoarePartition(arr, 0, arr.length - 1);
System.out.print(java.util.Arrays.toString(arr));
System.out.print(", pivotIndex=" + pivotIndex);

public static int hoarePartition(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;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

A [1, 2, 3, 4, 5], pivotIndex=0

B [1, 2, 3, 4, 5], pivotIndex=4

C [5, 2, 3, 4, 1], pivotIndex=0

D [1, 2, 3, 5, 4], pivotIndex=3

💡 Hint

Hoare partition returns index where pointers cross, pivot is first element.

Since array is sorted and pivot is smallest element, pointers cross immediately at low index 0, no swaps occur.

🧠 Conceptual

expert

Difference in Pivot Placement Between Lomuto and Hoare Partition

Which statement correctly describes the difference in pivot placement between Lomuto and Hoare partition schemes?

A Hoare places pivot at its final sorted position; Lomuto does not guarantee pivot final position

B Both Lomuto and Hoare always place pivot at final sorted position

C Lomuto places pivot at its final sorted position; Hoare does not guarantee pivot final position

D Neither Lomuto nor Hoare place pivot at final sorted position

💡 Hint

Think about where the pivot ends after partition in each scheme.

Lomuto partition always places pivot at its correct sorted position. Hoare partition only ensures elements are partitioned but pivot may not be at final position.

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