Why Quick Sort Partition Lomuto and Hoare in DSA Python?

The Big Idea

Discover how Quick Sort's smart splitting tricks turn a huge mess into order lightning fast!

The Scenario

Imagine you have a messy pile of books and you want to arrange them by size. Doing it by hand means picking one book, comparing it with all others, and placing it in the right spot. This takes a lot of time and effort, especially if the pile is huge.

The Problem

Sorting by checking every book against every other book is slow and tiring. You might lose track, make mistakes, or take forever to finish. This manual way does not scale well when the pile grows.

The Solution

Quick Sort uses smart ways called Lomuto and Hoare partitions to split the pile into smaller parts quickly. These methods pick a 'pivot' book and arrange others around it efficiently, making sorting much faster and easier.

Before vs After

✗ Before

books = [5, 3, 8, 4]
for i in range(len(books)):
    for j in range(i+1, len(books)):
        if books[i] > books[j]:
            books[i], books[j] = books[j], books[i]

✓ After

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

What It Enables

It enables sorting large lists quickly by breaking the problem into smaller, manageable parts using clever pivot choices.

Real Life Example

When you sort your music playlist by song length or your photo gallery by date, Quick Sort helps apps do this fast without freezing or slowing down.

Key Takeaways

Manual sorting is slow and error-prone for big lists.

Lomuto and Hoare partitions split data efficiently around a pivot.

This makes Quick Sort a fast and powerful sorting method.

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