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

Practice - 5 Tasks

1fill in blank

easy

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

DSA Python

def lomuto_partition(arr, low, high):
    pivot = arr[[1]]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

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

Ahigh

B0

Clow + 1

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Choosing the first element as pivot instead of the last.

Using an index outside the current sub-array.

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

2fill in blank

medium

Complete the code to move the pointers correctly in Hoare partition.

DSA Python

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return [1]
        arr[i], arr[j] = arr[j], arr[i]

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

Aj

Bi

Clow

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 'i' instead of 'j'.

Returning the pivot index instead of the crossing point.

In Hoare partition, the partition index returned is 'j', which is the crossing point of pointers.

3fill in blank

hard

Fix the error in the Lomuto partition loop condition to avoid index error.

DSA Python

def lomuto_partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, [1]):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

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

Alow

Bhigh + 1

Chigh

Dhigh - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'high + 1' causing index error.

Using 'high - 1' which misses the last element before pivot.

The loop should run from low to high-1, so range(low, high) is correct because 'high' is excluded.

4fill in blank

hard

Fill both blanks to correctly implement the pointer movement in Hoare partition.

DSA Python

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = [1]
    j = [2]
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

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

Alow

Blow - 1

Chigh

Dhigh + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting pointers at low and high instead of outside the bounds.

Mixing up the start positions causing infinite loops.

In Hoare partition, 'i' starts at low - 1 and 'j' starts at high + 1 to move inward correctly.

5fill in blank

hard

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

DSA Python

def lomuto_partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i [1] 1], arr[[2]] = arr[[3]], arr[i + 1]
    return i + 1

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

A+

B-

Chigh

Dlow

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-' instead of '+' causing wrong index.

Swapping with low instead of high.

Returning wrong partition index.

We swap arr[i + 1] with arr[high] (pivot) and then return i + 1 as the partition index.

Practice

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

easy

A. Lomuto sorts the array, Hoare only partitions without sorting

B. Lomuto uses a single pointer to partition, Hoare uses two pointers moving inward

C. Hoare uses recursion, Lomuto does not

D. Lomuto always picks the last element as pivot, Hoare picks the first element

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 to partition, Hoare uses two pointers moving inward -> Option B

4. Quick Check:

   Partition schemes differ by pointer usage = A [OK]

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

Common Mistakes:

• Confusing pivot selection with partition method
• Thinking Hoare does not partition
• Assuming Lomuto uses two pointers

2. Which of the following is the correct syntax for Lomuto partition function header in Python?

easy

A. def lomuto_partition(arr):

B. def lomuto_partition(arr, start, end):

C. def lomuto_partition(arr, low, high):

D. def lomuto_partition(low, high, arr):

Solution

1. Step 1: Check parameter order and names

   Lomuto partition typically takes array, low index, and high index as parameters in that order.

2. Step 2: Validate function header syntax

   def lomuto_partition(arr, low, high): matches the common and correct syntax: def lomuto_partition(arr, low, high):

3. Final Answer:

   def lomuto_partition(arr, low, high): -> Option C

4. Quick Check:

   Correct function header = C [OK]

Hint: Remember parameter order: array, low, high [OK]

Common Mistakes:

• Swapping parameter order
• Missing parameters
• Using incorrect parameter names

3. What is the output of the following code using Lomuto partition?

def lomuto_partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i+1

arr = [8, 3, 7, 6, 2]
index = lomuto_partition(arr, 0, 4)
print(arr)

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: Identify pivot and initial pointers

   Pivot is arr[4] = 2. i starts at -1.

2. Step 2: Iterate and swap elements <= pivot

   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 No i increment, i stays -1.

3. Step 3: Swap pivot with arr[i+1]

   Swap arr[0] and arr[4]: arr becomes [2, 3, 7, 6, 8]

4. Final Answer:

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

5. Quick Check:

   Pivot 2 placed at start, smaller elements left = A [OK]

Hint: Pivot swaps at i+1 after loop ends [OK]

Common Mistakes:

• Swapping pivot too early
• Incrementing i incorrectly
• Confusing pivot index

4. Find the error in this Hoare partition implementation:

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low + 1
    j = high
    while True:
        while i <= high and arr[i] < pivot:
            i += 1
        while j >= low and arr[j] > pivot:
            j -= 1
        if i >= j:
            break
        arr[i], arr[j] = arr[j], arr[i]
    arr[low], arr[j] = arr[j], arr[low]
    return j

arr = [5, 2, 9, 1, 5, 6]
index = hoare_partition(arr, 0, 5)
print(arr)

medium

A. The swap of pivot with arr[j] is incorrect in Hoare partition

B. i should start at low, not low + 1

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

D. The inner while loops should use <= and >= incorrectly

Solution

1. Step 1: Review Hoare partition pivot swap

   Hoare partition does NOT swap pivot with arr[j] at the end; it returns j as partition index.

2. Step 2: Check code's final swap

   This code swaps arr[low] and arr[j], which is incorrect and can misplace pivot.

3. Final Answer:

   The swap of pivot with arr[j] is incorrect in Hoare partition -> Option A

4. Quick Check:

   Hoare returns index without swapping pivot at end = B [OK]

Hint: Hoare returns index, no pivot swap at end [OK]

Common Mistakes:

• Swapping pivot at end in Hoare
• Starting pointers incorrectly
• Misusing loop conditions

5. Given the array [10, 80, 30, 90, 40, 50, 70], what is the array state after applying Hoare partition with pivot as first element?

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

arr = [10, 80, 30, 90, 40, 50, 70]
index = hoare_partition(arr, 0, 6)
print(arr)

hard

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

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

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

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

Solution

1. Step 1: Initialize pointers and pivot

   Pivot = 10, i = -1, j = 7 initially.

2. Step 2: Move pointers and swap

   Loop 1: - i increments to 0, arr[i]=10 not < pivot, stop - j decrements to 6, arr[6]=70 > 10, j=5 arr[5]=50 > 10, j=4 arr[4]=40 > 10, j=3 arr[3]=90 > 10, j=2 arr[2]=30 > 10, j=1 arr[1]=80 > 10, j=0 arr[0]=10 not > 10, stop - i=0, j=0, i >= j so return j=0 No swaps done, array unchanged.

3. Step 3: Check if any swaps occurred

   Since i >= j immediately, no swaps happened, array remains same.

4. Final Answer:

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

5. Quick Check:

   Pivot 10 smallest, no swaps = D [OK]

Hint: Hoare stops when pointers cross, may do no swaps [OK]

Common Mistakes:

• Assuming pivot moves at end
• Misunderstanding pointer increments
• Expecting sorted array after partition