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

Quick Sort Partition: Lomuto and Hoare

📖 Scenario: You are helping a friend understand how the Quick Sort algorithm divides an array into parts using two popular methods: Lomuto and Hoare partition schemes. This is like organizing a deck of cards by picking a card (pivot) and arranging others around it.

🎯 Goal: Build two functions to partition a list of numbers using Lomuto and Hoare methods, then see how the list looks after each partition.

📋 What You'll Learn

Create a list called numbers with exact values [8, 3, 7, 6, 2, 5, 4, 1]

Create a variable called pivot_index set to the last index of numbers

Write a function lomuto_partition(numbers, low, high) implementing Lomuto partition scheme

Write a function hoare_partition(numbers, low, high) implementing Hoare partition scheme

Print the list after applying Lomuto partition

Print the list after applying Hoare partition

💡 Why This Matters

🌍 Real World

Quick Sort is used in many software systems to sort data efficiently, such as organizing files, searching databases, and preparing data for analysis.

💼 Career

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

1

Create the list of numbers

Create a list called numbers with these exact values: [8, 3, 7, 6, 2, 5, 4, 1]

DSA Python

# Create the list called numbers with the given values
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Set the pivot index

Create a variable called pivot_index and set it to the last index of the numbers list using len(numbers) - 1

DSA Python

numbers = [8, 3, 7, 6, 2, 5, 4, 1]
# Set pivot_index to the last index of numbers
# Your code here

Hint

Use len(numbers) - 1 to get the last index.

3

Write Lomuto and Hoare partition functions

Write two functions: lomuto_partition(numbers, low, high) and hoare_partition(numbers, low, high) implementing Lomuto and Hoare partition schemes respectively. Use numbers list and low, high indices as parameters. Follow these rules:

Lomuto:
- Choose pivot as numbers[high]
- Initialize i = low - 1
- Loop j from low to high - 1
- If numbers[j] <= pivot, increment i and swap numbers[i] and numbers[j]
- Swap numbers[i + 1] and numbers[high]
- Return i + 1

Hoare:
- Choose pivot as numbers[low]
- Initialize i = low - 1 and j = high + 1
- Loop forever:
- Increment i until numbers[i] >= pivot
- Decrement j until numbers[j] <= pivot
- If i >= j, return j
- Swap numbers[i] and numbers[j]

DSA Python

numbers = [8, 3, 7, 6, 2, 5, 4, 1]
pivot_index = len(numbers) - 1
# Write lomuto_partition function
# Write hoare_partition function
# Your code here

Hint

Follow the step-by-step rules for each partition method carefully. Use swaps to rearrange elements.

4

Print the list after Lomuto and Hoare partitions

Call lomuto_partition(numbers, 0, pivot_index) and print the numbers list. Then reset numbers to [8, 3, 7, 6, 2, 5, 4, 1], call hoare_partition(numbers, 0, pivot_index) and print the numbers list again.

DSA Python

numbers = [8, 3, 7, 6, 2, 5, 4, 1]
pivot_index = len(numbers) - 1

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

# Call lomuto_partition and print numbers
# Reset numbers
# Call hoare_partition and print numbers
# Your code here

Hint

Remember to reset the numbers list before calling the second partition function. Use print(numbers) to show the list after each partition.

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