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

Concept Flow - Quick Sort Partition Lomuto and Hoare

Choose pivot = last element

↓

Initialize i = low - 1

↓

For j = low to high-1

↓

If arr[j

↓

i++, 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 forever

↓

i++ until arr[i

↓

If i >= j

↓

Return j as pivot index

↓

Else swap arr[i

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

Execution Sample

DSA Go

func lomutoPartition(arr []int, low, high int) int {
    pivot := arr[high]
    i := low - 1
    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            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, returning pivot's final index.

Execution Table

Step	Operation	i	j	Pivot	Array State	Pointer Changes	Action
1	Initialize i = low - 1	-1	-	5	[3, 8, 2, 5, 1, 4]	i = -1	Start loop j from 0
2	j=0, arr[j]=3 <= pivot=5?	-1	0	5	[3, 8, 2, 5, 1, 4]	-	Yes, i=0, swap arr[0], arr[0] (no change)
3	j=1, arr[j]=8 <= pivot=5?	0	1	5	[3, 8, 2, 5, 1, 4]	-	No, i stays 0
4	j=2, arr[j]=2 <= pivot=5?	0	2	5	[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=5?	1	3	5	[3, 2, 8, 5, 1, 4]	-	Yes, i=2, swap arr[2], arr[3] → [3, 2, 5, 8, 1, 4]
6	j=4, arr[j]=1 <= pivot=5?	2	4	5	[3, 2, 5, 8, 1, 4]	-	Yes, i=3, swap arr[3], arr[4] → [3, 2, 5, 1, 8, 4]
7	End loop, swap arr[i+1], arr[high]	3	-	5	[3, 2, 5, 1, 8, 4]	Swap arr[4], arr[5]	Swap arr[4], arr[5] → [3, 2, 5, 1, 4, 8]
8	Return pivot index i+1	4	-	5	[3, 2, 5, 1, 4, 8]	-	Pivot index = 4
9	Hoare init i=low-1, j=high+1	-1	6	3	[3, 2, 5, 1, 4, 8]	i=-1, j=6	Start loop
10	i++ until arr[i]>=pivot	0	6	3	[3, 2, 5, 1, 4, 8]	i=0	arr[0]=3 >=3 stop
11	j-- until arr[j]<=pivot	0	5	3	[3, 2, 5, 1, 4, 8]	j=5	arr[5]=8 >3 continue j=4
12	j-- until arr[j]<=pivot	0	4	3	[3, 2, 5, 1, 4, 8]	j=4	arr[4]=4 >3 continue j=3
13	j-- until arr[j]<=pivot	0	3	3	[3, 2, 5, 1, 4, 8]	j=3	arr[3]=1 <=3 stop
14	i < j? i=0, j=3	0	3	3	[3, 2, 5, 1, 4, 8]	-	Yes, swap arr[0], arr[3] → [1, 2, 5, 3, 4, 8]
15	i++ until arr[i]>=pivot	1	3	3	[1, 2, 5, 3, 4, 8]	i=1	arr[1]=2 <3 continue i=2
16	i++ until arr[i]>=pivot	2	3	3	[1, 2, 5, 3, 4, 8]	i=2	arr[2]=5 >=3 stop
17	j-- until arr[j]<=pivot	2	2	3	[1, 2, 5, 3, 4, 8]	j=2	arr[2]=5 >3 continue j=1
18	i < j? i=2, j=1	2	1	3	[1, 2, 5, 3, 4, 8]	-	No, return j=1
19	Partition done, pivot index = 1	2	1	3	[1, 2, 5, 3, 4, 8]	-	Hoare partition returns 1

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

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	After Step 8	After Step 9	After Step 14	After Step 18
i (Lomuto)	-1	0	1	3	3	4	-	-	-
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,5,1,8,4]	[3,2,5,1,4,8]	[3,2,5,1,4,8]	-	-	-
i (Hoare)	-	-	-	-	-	-	-1	0	2
j (Hoare)	-	-	-	-	-	-	6	3	1
Array (Hoare)	-	-	-	-	-	-	[3,2,5,1,4,8]	[1,2,5,3,4,8]	[1,2,5,3,4,8]

Key Moments - 3 Insights

Why does Lomuto use i = low - 1 instead of starting at low?

Because i tracks the last position where elements <= pivot are placed. Starting at low - 1 means no elements are placed yet. See execution_table step 2 where i increments before swapping.

In Hoare partition, why do we increment i and decrement j until conditions fail?

To find elements on wrong sides of pivot to swap. i moves right to find element >= pivot, j moves left to find element <= pivot. See execution_table steps 10-13 and 15-17.

Why does Hoare return j instead of i as pivot index?

Because when i >= j, j marks the boundary where left side <= pivot and right side >= pivot. Returning j ensures partitioning is correct. See execution_table step 18.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after Lomuto step 6?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 6 in execution_table.

At which step in Hoare partition does the first swap occur?

A Step 10

B Step 18

C Step 14

D Step 12

💡 Hint

Look for 'swap' action in execution_table rows for Hoare partition.

If in Lomuto partition the pivot was the first element instead of last, how would the initial i value change?

A i would start at low

B i would start at low - 1

C i would start at high

D i would start at 0

💡 Hint

Recall i tracks last element <= pivot; pivot position affects i initialization (see variable_tracker).

Concept Snapshot

Quick Sort Partition:
- Lomuto: pivot = last element
- i starts at low-1, j scans low to high-1
- Swap elements <= pivot forward
- Swap pivot to i+1, return i+1

- Hoare: pivot = first element
- i=low-1, j=high+1
- Move i right until >= pivot, j left until <= pivot
- Swap arr[i], arr[j] if i<j else return j

Both rearrange array around pivot for recursive quicksort.

Full Transcript

This visualization shows how Lomuto and Hoare partition methods work in quicksort. Lomuto chooses the last element as pivot, initializes i to low-1, and moves j from low to high-1. When arr[j] is less or equal to pivot, i increments and swaps arr[i] and arr[j]. After the loop, pivot is swapped to position i+1, which is returned as the pivot index. Hoare chooses the first element as pivot, sets i to low-1 and j to high+1, then moves i right until arr[i] >= pivot and j left until arr[j] <= pivot. If i < j, arr[i] and arr[j] are swapped; otherwise, j is returned as the pivot index. The execution table traces each step, showing pointer movements, swaps, and array states. Key moments clarify why pointers start at certain positions and why Hoare returns j. The quiz tests understanding of array states and pointer logic. This helps learners see how partitioning rearranges elements for quicksort.