Quick Sort Partition Lomuto and Hoare in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to swap two elements in the array.

DSA Java

int temp = arr[[1]];
arr[[1]] = arr[j];
arr[j] = temp;

Drag options to blanks, or click blank then click option'

Ai

Bj

Cpivot

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Using j instead of i causes swapping the wrong elements.

Using pivot or low as index causes errors.

We swap the element at index i with the element at index j to move smaller elements before the pivot.

2fill in blank

medium

Complete the code to choose the pivot element in Lomuto partition.

DSA Java

int pivot = arr[[1]];

Drag options to blanks, or click blank then click option'

Amid

Bhigh

Clow

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing low or mid as pivot changes partition behavior.

Using 0 as pivot index ignores current subarray boundaries.

In Lomuto partition, the pivot is chosen as the last element at index high.

3fill in blank

hard

Fix the error in the Hoare partition loop condition to avoid infinite loop.

DSA Java

while (arr[i] [1] pivot) i++;
while (arr[j] [2] pivot) j--;

Drag options to blanks, or click blank then click option'

A<=

B<

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= or >= in conditions causes infinite loops.

Reversing signs breaks partition logic.

In Hoare partition, i moves forward while arr[i] is less than pivot, and j moves backward while arr[j] is greater than pivot.

4fill in blank

hard

Fill in the blank to complete the Lomuto partition loop that moves smaller elements before pivot.

DSA Java

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

Drag options to blanks, or click blank then click option'

A>=

B>

C<=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' or '>=' reverses the logic and breaks partition.

Using '<=' may cause different partition behavior but is not the standard Lomuto.

In Lomuto partition, elements less than or equal to pivot are moved before it. Using '<' ensures strict less than comparison.

5fill in blank

hard

Fill all three blanks to complete the Hoare partition swap and return statement.

DSA Java

if (i >= j) return [1];
int temp = arr[[2]];
arr[[2]] = arr[[3]];
arr[[3]] = temp;

Drag options to blanks, or click blank then click option'

Aj

Bi

Attempts:

3 left

💡 Hint

Common Mistakes

Returning i instead of j causes incorrect partition index.

Swapping wrong indices breaks partition correctness.

When pointers cross, return j as partition index. Swap arr[i] and arr[j] to place elements correctly.

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