Quick Sort Partition Lomuto and Hoare in DSA Python - Execution Trace

Concept Flow - Quick Sort Partition Lomuto and Hoare

Choose pivot = last element

↓

Initialize i = low - 1

↓

For j from low to high-1

↓

If arr[j

↓

i += 1

↓

Swap arr[i

↓

After loop, swap arr[i+1

↓

Return i+1 as pivot index

↓

Choose pivot = arr[low

↓

i = low - 1, j = high + 1

↓

Repeat

↓

Increment i until arr[i

↓

Decrement j until arr[j

↓

If i >= j, return j

↓

Else swap arr[i

↓

Repeat loop

Shows step-by-step how Lomuto and Hoare partition methods rearrange array elements around a pivot for quicksort.

Execution Sample

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 i+1

Lomuto partition rearranges elements so those <= pivot come before it, then returns pivot index.

Execution Table

Step	Operation	i	j	Pivot	Array State	Pointer Changes
1	Initialize i = low - 1	-1	-	4	[3, 8, 2, 5, 1, 4]	i = -1
2	j=0, arr[j]=3 <= pivot(4)?	-1	0	4	[3, 8, 2, 5, 1, 4]	Yes: i=0, swap arr[0], arr[0] (no change)
3	j=1, arr[j]=8 <= pivot(4)?	0	1	4	[3, 8, 2, 5, 1, 4]	No: i=0, no swap
4	j=2, arr[j]=2 <= pivot(4)?	0	2	4	[3, 8, 2, 5, 1, 4]	Yes: i=1, swap arr[1], arr[2] -> [3, 2, 8, 5, 1, 4]
5	j=3, arr[j]=5 <= pivot(4)?	1	3	4	[3, 2, 8, 5, 1, 4]	No: i=1, no swap
6	j=4, arr[j]=1 <= pivot(4)?	1	4	4	[3, 2, 8, 5, 1, 4]	Yes: i=2, swap arr[2], arr[4] -> [3, 2, 1, 5, 8, 4]
7	After loop, swap arr[i+1], pivot	2	-	4	[3, 2, 1, 5, 8, 4]	Swap arr[3], arr[5] -> [3, 2, 1, 4, 8, 5]
8	Return pivot index i+1	3	-	4	[3, 2, 1, 4, 8, 5]	Pivot index = 3
9	Hoare init i=low-1, j=high+1	-1	6	3	[3, 2, 1, 4, 8, 5]	i=-1, j=6, pivot=3
10	Increment i until arr[i]>=pivot	0	6	3	[3, 2, 1, 4, 8, 5]	i=0 (arr[0]=3 >=3)
11	Decrement j until arr[j]<=pivot	0	5	3	[3, 2, 1, 4, 8, 5]	j=5 (arr[5]=5 >3), j=4 (arr[4]=8 >3), j=3 (arr[3]=4 >3), j=2 (arr[2]=1 <=3)
12	i < j? 0 < 2	0	2	3	[3, 2, 1, 4, 8, 5]	Yes: swap arr[0], arr[2] -> [1, 2, 3, 4, 8, 5]
13	Increment i until arr[i]>=pivot	1	2	3	[1, 2, 3, 4, 8, 5]	i=1 (arr[1]=2 <3), i=2 (arr[2]=3 >=3)
14	Decrement j until arr[j]<=pivot	2	2	3	[1, 2, 3, 4, 8, 5]	j=2 (arr[2]=3 <=3)
15	i < j? 2 < 2	2	2	3	[1, 2, 3, 4, 8, 5]	No: i >= j
16	Partition done, pivot index = 2	2	2	3	[1, 2, 3, 4, 8, 5]	Hoare partition index = 2

💡 Lomuto ends after swapping pivot to correct place; Hoare ends when i >= j.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	After Step 8	After Step 10	After Step 12	After Step 15	After Step 16
i (Lomuto)	-1	0	1	2	2	3	-	-	-	-
j (Lomuto)	-	0	2	4	-	-	-	-	-	-
Array (Lomuto)	[3,8,2,5,1,4]	[3,8,2,5,1,4]	[3,2,8,5,1,4]	[3,2,1,5,8,4]	[3,2,1,5,8,4]	[3,2,1,4,8,5]	-	-	-	-
i (Hoare)	-	-	-	-	-	-	-1	0	2	2
j (Hoare)	-	-	-	-	-	-	6	2	2	2
Array (Hoare)	-	-	-	-	-	-	[3,2,1,4,8,5]	[1,2,3,4,8,5]	[1,2,3,4,8,5]	[1,2,3,4,8,5]

Key Moments - 3 Insights

Why does Lomuto partition use i = low - 1 at start?

Because i tracks the last position where element <= pivot was placed. Starting at low - 1 means no elements placed yet. See execution_table row 1 and 2 where i moves from -1 to 0 when first <= pivot found.

Why does Hoare partition return j, not i?

Hoare returns j because at the end i >= j, and j marks the boundary where left side <= pivot and right side >= pivot. See execution_table rows 15 and 16 where i=2, j=2 and partition returns j=2.

Why does Lomuto swap pivot at the end, but Hoare swaps during the loop?

Lomuto places pivot at the end after all smaller elements are moved left. Hoare swaps elements on wrong sides during the loop to partition early. See execution_table rows 7 (Lomuto final swap) and 12 (Hoare swap inside loop).

Visual Quiz - 3 Questions

Look at the execution_table row 4 for Lomuto partition. What is the value of i after processing j=2?

A 1

B 2

C 0

D -1

💡 Hint

Check the 'i' column in row 4 where j=2 is processed.

At which step does Hoare partition swap arr[0] and arr[2]?

A Step 10

B Step 15

C Step 12

D Step 16

💡 Hint

Look at the 'Operation' and 'Pointer Changes' columns in execution_table rows 10-15.

If in Lomuto partition the pivot was chosen as arr[low] instead of arr[high], how would the execution_table change?

A The i pointer would start at high instead of low - 1

B The pivot value and final swap step would change

C The loop would run backwards from high to low

D No changes, algorithm stays the same

💡 Hint

Pivot choice affects pivot value and where final swap happens, see execution_table pivot column.

Concept Snapshot

Quick Sort Partition Methods:
- Lomuto: pivot = last element
  i starts at low-1
  j scans low to high-1
  swap arr[i] and arr[j] if arr[j]<=pivot
  final swap pivot to arr[i+1]
- Hoare: pivot = arr[low]
  i=low-1, j=high+1
  increment i until arr[i]>=pivot
  decrement j until arr[j]<=pivot
  if i<j swap arr[i], arr[j]
  else return j
Both rearrange array around pivot for quicksort.

Full Transcript

This visual execution trace shows how Lomuto and Hoare partition methods work in quicksort. Lomuto chooses the last element as pivot, uses i to track last smaller element, and swaps elements <= pivot to front, then places pivot after them. Hoare chooses first element as pivot, uses two pointers i and j moving inward, swapping elements on wrong sides until pointers cross, then returns partition index. The execution table traces each step with array states and pointer changes. Key moments clarify why pointers start at certain values and why swaps happen at different times. The quiz tests understanding of pointer values and swap steps. The snapshot summarizes the key steps and differences between Lomuto and Hoare partitions.

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