Quick Sort Partition Lomuto and Hoare in DSA Python - 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 returns the pivot's final position.

intermediate

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

Hoare partition uses two pointers starting from both ends moving towards each other, swapping elements to ensure left side is smaller and right side is larger than pivot. It returns an index near the pivot but not necessarily the pivot's final position.

beginner

In Lomuto partition, what happens when an element is smaller than the pivot during iteration?

When an element is smaller than the pivot, it is swapped with the element at the 'store index', and the store index is incremented. This keeps smaller elements to the left.

intermediate

Why can Hoare partition be more efficient than Lomuto partition?

Hoare partition generally does fewer swaps and comparisons because it moves pointers inward and swaps only when necessary, making it faster especially on large arrays.

intermediate

What is the return value of Hoare partition and how is it used in Quick Sort?

Hoare partition returns an index where the left side elements are less than or equal to pivot and right side elements are greater than or equal. Quick Sort then recursively sorts the two subarrays divided by this index.

Which element does Lomuto partition scheme choose as pivot?

A First element

B Last element

C Middle element

D Random element

Lomuto partition always picks the last element as the pivot.

In Hoare partition, pointers start from:

A Both ends moving inward

B Only from the left

C Only from the right

D Middle moving outward

Hoare partition uses two pointers starting from both ends and moving towards each other.

What does Lomuto partition return after partitioning?

A Number of swaps

B Left pointer index

C Right pointer index

D Final pivot index

Lomuto partition returns the final position of the pivot element.

Which partition scheme generally performs fewer swaps?

A Lomuto

B Both equal

C Hoare

D Depends on pivot

Hoare partition usually performs fewer swaps than Lomuto.

After Hoare partition, Quick Sort recursively sorts:

A Two subarrays divided by returned index

B Only left subarray

C Only right subarray

D Entire array again

Quick Sort recursively sorts the two parts divided by the index returned by Hoare partition.

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

Think about how smaller elements are moved before the pivot.

Describe how Hoare partition uses two pointers to partition the array and what it returns.

Focus on pointer movements and swapping.

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