Quick Sort Partition Lomuto and Hoare in DSA Java - Build from Scratch

Quick Sort Partition: Lomuto and Hoare

📖 Scenario: You are working on sorting a list of numbers efficiently. Quick Sort is a popular sorting method that uses a step called partitioning to organize elements around a pivot.There are two common ways to partition: Lomuto and Hoare. Understanding both helps you see how Quick Sort works under the hood.

🎯 Goal: You will create an array of numbers, set up a pivot index, implement both Lomuto and Hoare partition methods, and then print the array after each partition to see how elements are rearranged.

📋 What You'll Learn

Create an integer array called arr with the exact values: 8, 3, 1, 7, 0, 10, 2

Create an integer variable called pivotIndex and set it to 6

Implement the Lomuto partition method named lomutoPartition that takes the array, start index, and end index, and returns the partition index

Implement the Hoare partition method named hoarePartition that takes the array, start index, and end index, and returns the partition index

Print the array after applying Lomuto partition and after applying Hoare partition

💡 Why This Matters

🌍 Real World

Quick Sort is widely used in software to sort data quickly, such as sorting names, numbers, or records in databases and applications.

💼 Career

Understanding partition methods helps in optimizing sorting algorithms, which is important for software engineers working on performance-critical applications.

1

Create the array arr

Create an integer array called arr with these exact values in order: 8, 3, 1, 7, 0, 10, 2

DSA Java

// Create the array arr with the given values
// Your code here

Hint

Use int[] arr = { ... }; to create the array with the exact numbers.

2

Create the pivot index variable pivotIndex

Create an integer variable called pivotIndex and set it to 6

DSA Java

int[] arr = {8, 3, 1, 7, 0, 10, 2};
// Create pivotIndex and set it to 6
// Your code here

Hint

Use int pivotIndex = 6; to create the pivot index variable.

3

Implement Lomuto and Hoare partition methods

Implement two methods: lomutoPartition and hoarePartition. Both take parameters int[] arr, int low, and int high. Lomuto partition returns the partition index after rearranging elements using the last element as pivot. Hoare partition returns the partition index after rearranging elements using the first element as pivot.

DSA Java

int[] arr = {8, 3, 1, 7, 0, 10, 2};
int pivotIndex = 6;

// Implement lomutoPartition method
// Your code here

// Implement hoarePartition method
// Your code here

Hint

Use the last element as pivot in Lomuto and the first element as pivot in Hoare. Swap elements to partition the array.

4

Print the array after Lomuto and Hoare partitions

Call lomutoPartition on arr with low = 0 and high = arr.length - 1. Then print the array elements separated by spaces. Reset arr to the original values. Call hoarePartition on arr with low = 0 and high = arr.length - 1. Then print the array elements separated by spaces.

DSA Java

int[] arr = {8, 3, 1, 7, 0, 10, 2};
int pivotIndex = 6;

public static int lomutoPartition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j  pivot);
        if (i >= j) {
            return j;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

// Call lomutoPartition and print array
// Reset arr
// Call hoarePartition and print array
// Your code here

Hint

Call the partition methods with low = 0 and high = arr.length - 1. Print the array elements separated by spaces after each 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