Quick Sort Partition Lomuto and Hoare in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind the Lomuto partition scheme in Quick Sort?

Lomuto partition picks the last element as pivot and rearranges the array so that elements smaller than pivot come before it, and larger come after. It uses one index to track the boundary of smaller elements.

intermediate

How does the Hoare partition scheme differ from Lomuto's in Quick Sort?

Hoare partition uses two indices starting from both ends of the array, moving towards each other, swapping elements that are on the wrong side of the pivot. It usually picks the first element as pivot and is more efficient with fewer swaps.

beginner

In Lomuto partition, what happens after the partitioning loop finishes?

After the loop, the pivot element is swapped with the element at the boundary index + 1, placing the pivot in its correct sorted position.

intermediate

Why is Hoare partition considered more efficient than Lomuto partition?

Hoare partition generally performs fewer swaps and comparisons because it stops scanning as soon as it finds elements to swap, making it faster especially on large arrays.

advanced

Show the final array state after Lomuto partition on [3, 8, 2, 5, 1, 4, 7, 6] with pivot as last element.

After partition, the array becomes [3, 2, 5, 1, 4, 6, 7, 8] with pivot 6 placed correctly at index 5.

Which element does Lomuto partition typically choose as pivot?

A First element

B Last element

C Middle element

D Random element

Lomuto partition usually picks the last element as the pivot.

In Hoare partition, what happens when the two indices cross?

A Indices reset to start

B Pivot is swapped with first element

C Partitioning ends and the crossing index is returned

D Array is fully sorted

When the two indices cross, partitioning ends and the crossing index is returned to split the array.

Which partition scheme generally uses fewer swaps?

A Hoare

B Both use equal swaps

C Lomuto

D Depends on array size

Hoare partition usually uses fewer swaps than Lomuto.

What is the main purpose of partitioning in Quick Sort?

A To sort the entire array immediately

B To merge two sorted arrays

C To find the maximum element

D To divide the array into parts around a pivot

Partitioning divides the array into parts where elements are less or greater than the pivot.

After Lomuto partition, where is the pivot placed?

A At its correct sorted position

B At the end of the array

C At the start of the array

D Random position

The pivot is placed at its correct sorted position after partitioning.

Explain step-by-step how Lomuto partition rearranges an array around the pivot.

Think about how the boundary index moves and how swaps happen.

Describe how Hoare partition uses two pointers to partition the array.

Visualize two people scanning from both ends and swapping misplaced items.

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