Quick Sort Partition Lomuto and Hoare in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA C++

int lomutoPartition(int arr[], int low, int high) {
    int pivot = arr[[1]];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

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

Ahigh

Bhigh - 1

Clow + 1

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing the pivot as the first element instead of the last.

Using an index outside the array bounds.

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

2fill in blank

medium

Complete the code to initialize the pointer for Hoare partition.

DSA C++

int hoarePartition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = [1];
    int j = high + 1;
    while (true) {
        do {
            i++;
        } while (arr[i] < pivot);
        do {
            j--;
        } while (arr[j] > pivot);
        if (i >= j) return j;
        std::swap(arr[i], arr[j]);
    }
}

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

Alow - 1

Bhigh

Chigh - 1

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing 'i' at low instead of low - 1.

Confusing the start positions of 'i' and 'j'.

In Hoare partition, 'i' starts just before the low index, so it is initialized to low - 1.

3fill in blank

hard

Fix the error in the Lomuto partition swap condition.

DSA C++

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] [1] pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

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

A>

B>=

C==

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<=' causing wrong partitioning.

Using '==' which only moves elements equal to pivot.

The condition arr[j] <= pivot ensures elements less than or equal to pivot are moved left.

4fill in blank

hard

Fill both blanks to complete the Hoare partition loop conditions.

DSA C++

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] [1] pivot);
        do {
            j--;
        } while (arr[j] [2] pivot);
        if (i >= j) return j;
        std::swap(arr[i], arr[j]);
    }
}

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

A<=

B>=

C<

D>

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong comparison operators causing infinite loops.

Mixing up the directions of 'i' and 'j' pointers.

In Hoare partition, 'i' moves forward while arr[i] < pivot, and 'j' moves backward while arr[j] > pivot.

5fill in blank

hard

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

DSA C++

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[1];
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i [2] 1], arr[[3]]);
    return i + 1;
}

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

A++

B+

Chigh

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'i+' instead of 'i++' causing syntax errors.

Swapping with wrong indices causing incorrect partition.

We increment 'i' with '++', swap arr[i + 1] with arr[high], and return i + 1 as the pivot index.

Practice

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

easy

A. Lomuto uses a single 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 chooses the last element as pivot, Hoare chooses the first element always

Solution

1. Step 1: Understand Lomuto partition

   Lomuto partition uses one 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 around the pivot.

3. Final Answer:

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

4. Quick Check:

   Lomuto single pointer, Hoare two pointers inward [OK]

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

Common Mistakes:

• Confusing pivot selection with partition method
• Thinking both use same pointer approach
• Assuming Hoare always picks first element as pivot

2. Which of the following is the correct Lomuto partition function header in C++?

easy

A. int partition(int arr[], int low, int high)

B. void partition(int arr[], int low, int high)

C. int partition(int arr[], int start, int end, int pivot)

D. bool partition(int arr[], int low, int high)

Solution

1. Step 1: Check return type

   Lomuto partition returns the pivot index as int after partitioning.

2. Step 2: Check parameters

   It takes array, low index, and high index as parameters to partition the subarray.

3. Final Answer:

   int partition(int arr[], int low, int high) -> Option A

4. Quick Check:

   Returns int pivot index, low high params [OK]

Hint: Partition returns pivot index as int with low and high params [OK]

Common Mistakes:

• Using void return type instead of int
• Adding extra pivot parameter unnecessarily
• Returning bool instead of pivot index

3. What is the output array after applying Lomuto partition on arr = [8, 3, 7, 6, 2] with low=0 and high=4?

medium

A. [2, 3, 6, 7, 8]

B. [3, 2, 7, 6, 8]

C. [8, 3, 7, 6, 2]

D. [2, 3, 7, 6, 8]

Solution

1. Step 1: Choose pivot and initialize pointers

   Pivot = arr[4] = 2, i = -1 initially.

2. Step 2: Iterate and swap smaller elements

   Check elements from index 0 to 3:
   - arr[0]=8 > 2 no swap
   - arr[1]=3 > 2 no swap
   - arr[2]=7 > 2 no swap
   - arr[3]=6 > 2 no swap
   After loop, swap arr[i+1]=arr[0] and pivot arr[4].

3. Final Answer:

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

4. Quick Check:

   Pivot swapped to front since no smaller elements [OK]

Hint: Pivot last element, swap smaller left, pivot final swap [OK]

Common Mistakes:

• Swapping elements incorrectly during iteration
• Confusing pivot position after partition
• Assuming pivot is first element

4. Identify the bug in this Hoare partition code snippet:

int hoarePartition(int arr[], int low, int high) {
  int pivot = arr[low];
  int i = low - 1, j = high + 1;
  while (true) {
    do { i++; } while (arr[i] < pivot);
    do { j--; } while (arr[j] > pivot);
    if (i >= j) return j;
    std::swap(arr[i], arr[j]);
  }
}

medium

A. Initialization of i and j is incorrect

B. No bug, code is correct

C. The loop condition should be i > j instead of i >= j

D. Pivot should be arr[high], not arr[low]

Solution

1. Step 1: Verify pointer initialization

   In standard Hoare partition, i starts at low-1 and j at high+1 to work with the do-while loops correctly.

2. Step 2: Check other parts

   Pivot selection arr[low], movement conditions arr[i] < pivot and arr[j] > pivot, i >= j return, and swap are all correct.

3. Final Answer:

   No bug, code is correct -> Option B

4. Quick Check:

   Standard Hoare uses i=low-1, j=high+1 [OK]

Hint: i starts at low, j at high in Hoare partition [OK]

Common Mistakes:

• Setting i and j outside array bounds
• Confusing pivot position with pointer initialization
• Misusing loop exit condition

5. Given the array [10, 80, 30, 90, 40, 50, 70], after applying Hoare partition with low=0 and high=6, what is the resulting array?

hard

A. [10, 30, 40, 50, 70, 90, 80]

B. [10, 30, 40, 50, 90, 80, 70]

C. [10, 80, 30, 90, 40, 50, 70]

D. [10, 30, 40, 50, 80, 70, 90]

Solution

1. Step 1: Set pivot and pointers

   Pivot = arr[0] = 10, i = low - 1 = -1, j = high + 1 = 7.

2. Step 2: Move pointers and check swaps

   do {i++;} while (arr[i] < 10): i=0, arr[0]=10 not <10, stop i=0.
   do {j--;} while (arr[j] > 10): j=6(70>10),5(50>10),4(40>10),3(90>10),2(30>10),1(80>10),0(10 not >10), stop j=0.
   i=0 < j=0 is false, so i >= j, return j=0, no swap.
   But since i == j, partition ends with pivot index 0.
   However, this means no swaps, so array remains same.

3. Step 3: Re-examine pointer movement

   Actually, the do-while loops stop at i=0 and j=0, so no swaps occur.
   Therefore, the array remains unchanged.

4. Final Answer:

   [10, 80, 30, 90, 40, 50, 70] -> Option C

5. Quick Check:

   All elements ≥ pivot, array unchanged [OK]

Hint: Track i and j moving inward, swap when i < j [OK]

Common Mistakes:

• Swapping after pointers cross
• Misplacing pivot after partition
• Confusing Hoare with Lomuto output