Quick Sort Partition Lomuto and Hoare in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Lomuto Partition on a sample array

What is the output array after applying Lomuto partition on the array [8, 3, 7, 6, 2, 5, 4] with pivot as the last element?

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], arr[high] = arr[high], arr[i+1]
    return arr

arr = [8, 3, 7, 6, 2, 5, 4]
lomuto_partition(arr, 0, len(arr)-1)
print(arr)

A [3, 2, 4, 6, 8, 5, 7]

B [3, 2, 4, 5, 6, 8, 7]

C [2, 3, 4, 5, 6, 7, 8]

D [8, 3, 7, 6, 2, 5, 4]

💡 Hint

Remember Lomuto partition places elements smaller or equal to pivot on left side and swaps pivot to correct position.

Lomuto partition uses the last element as pivot. It moves all elements smaller or equal to pivot to the left, then places pivot after them. The resulting array is [3, 2, 4, 6, 8, 5, 7].

❓ Predict Output

intermediate

Output of Hoare Partition on a sample array

What is the output array after applying Hoare partition on the array [9, 4, 8, 3, 1, 2, 5] with pivot as the first element?

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 j
        arr[i], arr[j] = arr[j], arr[i]

arr = [9, 4, 8, 3, 1, 2, 5]
hoare_partition(arr, 0, len(arr)-1)
print(arr)

A [2, 4, 3, 1, 5, 8, 9]

B [5, 4, 8, 3, 1, 2, 9]

C [1, 2, 3, 4, 5, 8, 9]

D [9, 4, 8, 3, 1, 2, 5]

💡 Hint

Hoare partition uses the first element as pivot and swaps elements to ensure left side smaller and right side larger than pivot.

Hoare partition swaps elements from left and right until pointers cross. The pivot 9 ends up on the right side. The array becomes [5, 4, 8, 3, 1, 2, 9].

🧠 Conceptual

advanced

Difference in pivot placement between Lomuto and Hoare partitions

Which statement correctly describes the difference in pivot placement after Lomuto and Hoare partition schemes?

A Both Lomuto and Hoare always place the pivot at its final sorted position.

B Hoare places the pivot at its final sorted position; Lomuto does not guarantee pivot at final position.

C Lomuto places the pivot at its final sorted position; Hoare does not guarantee pivot at final position.

D Neither Lomuto nor Hoare place the pivot at its final sorted position.

💡 Hint

Think about where the pivot ends after partitioning in each scheme.

Lomuto partition always places the pivot at its correct sorted position after partitioning. Hoare partition only ensures elements are partitioned but pivot may not be at final position.

🔧 Debug

advanced

Identify the error in Lomuto partition implementation

What error will occur when running this Lomuto partition code on array [4, 5, 3, 7, 2]? def lomuto_partition(arr, low, high): pivot = arr[high] i = low for j in range(low, high): if arr[j] < pivot: arr[i], arr[j] = arr[j], arr[i] i += 1 arr[i], arr[high] = arr[high], arr[i] return i lomuto_partition([4, 5, 3, 7, 2], 0, 4)

A No error; returns correct pivot index 0

B IndexError due to i starting at low instead of low - 1

C Incorrect partitioning because of using '<' instead of '<='

D TypeError due to swapping elements incorrectly

💡 Hint

Check the initialization of i and the comparison operator in the loop.

Starting i at low is valid; using '<' excludes pivot duplicates on left but no error occurs. The code runs correctly and returns pivot index 0.

🚀 Application

expert

Number of swaps in Hoare partition

Given the array [10, 7, 8, 9, 1, 5] and using Hoare partition with pivot as first element, how many swaps occur during partitioning?

DSA Python

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

arr = [10, 7, 8, 9, 1, 5]
hoare_partition(arr, 0, len(arr)-1)

A 2

B 5

C 4

D 1

💡 Hint

Trace the pointers i and j and count each swap carefully.

Swaps occur when elements on wrong sides are exchanged. For this array, 1 swap happens before pointers cross.

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