Dutch National Flag Three Way Partition in DSA Python - Execution Trace

Concept Flow - Dutch National Flag Three Way Partition

Initialize pointers: low=0, mid=0, high=n-1

↓

Check mid <= high?

No→Done

Yes↓

Inspect arr[mid

↓

Swap arr[low

↩Back to Check

We use three pointers low, mid, and high to partition the array into three parts: 0s, 1s, and 2s by swapping elements and moving pointers until mid passes high.

Execution Sample

DSA Python

arr = [2,0,2,1,1,0]
low = 0
mid = 0
high = len(arr) - 1
while mid <= high:
    if arr[mid] == 0:
        arr[low], arr[mid] = arr[mid], arr[low]
        low += 1
        mid += 1
    elif arr[mid] == 1:
        mid += 1
    else:
        arr[mid], arr[high] = arr[high], arr[mid]
        high -= 1

This code sorts the array so that all 0s come first, then 1s, then 2s using three pointers and swaps.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Start	0	0	5	[2,0,2,1,1,0]	Initial pointers
2	arr[mid]=2, swap arr[mid] and arr[high]	0	0	5	[0,0,2,1,1,2]	Swap arr[0]<->arr[5], high=4
3	arr[mid]=0, swap arr[low] and arr[mid]	0	0	4	[0,0,2,1,1,2]	Swap arr[0]<->arr[0], low=1, mid=1
4	arr[mid]=0, swap arr[low] and arr[mid]	1	1	4	[0,0,2,1,1,2]	Swap arr[1]<->arr[1], low=2, mid=2
5	arr[mid]=2, swap arr[mid] and arr[high]	2	2	4	[0,0,1,1,2,2]	Swap arr[2]<->arr[4], high=3
6	arr[mid]=1, mid += 1	2	2	3	[0,0,1,1,2,2]	mid=3
7	arr[mid]=1, mid += 1	2	3	3	[0,0,1,1,2,2]	mid=4
8	mid=4 > high=3, done	2	4	3	[0,0,1,1,2,2]	Loop ends

💡 mid pointer crossed high pointer, partition complete

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
low	0	0	1	2	2	2	2	2
mid	0	0	1	2	2	3	4	4
high	5	4	4	4	3	3	3	3
arr	[2,0,2,1,1,0]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]

Key Moments - 3 Insights

Why do we swap arr[mid] with arr[high] when arr[mid] is 2 and not move mid forward?

Because after swapping with arr[high], the new element at arr[mid] is unknown and must be checked again. This is shown in Step 2 and Step 5 where mid stays the same after swapping.

Why do we increment both low and mid when arr[mid] is 0?

Because swapping arr[mid] with arr[low] places a 0 in the correct position, so we can safely move both pointers forward. This is shown in Steps 3 and 4.

When does the loop stop and why?

The loop stops when mid > high, meaning all elements have been partitioned. This is shown in Step 8.

Visual Quiz - 3 Questions

Look at the execution table, what is the array state after Step 5?

A [0,0,1,1,2,2]

B [0,0,2,1,1,2]

C [2,0,2,1,1,0]

D [0,0,1,1,1,2]

💡 Hint

Check the 'Array State' column in Step 5 of the execution_table.

At which step does the mid pointer first move past the high pointer?

A Step 6

B Step 7

C Step 8

D Step 5

💡 Hint

Look at the 'mid' and 'high' values in the execution_table rows.

If we did not decrement high after swapping with arr[mid] when arr[mid] is 2, what would happen?

A The algorithm would still work correctly.

B The algorithm might enter an infinite loop.

C The low pointer would move incorrectly.

D The array would be sorted faster.

💡 Hint

Refer to the key moment about why high is decremented after swapping with arr[high].

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- low and mid start at 0, high at end
- While mid <= high:
  - If arr[mid]==0: swap with arr[low], low++, mid++
  - If arr[mid]==1: mid++
  - If arr[mid]==2: swap with arr[high], high--
- Stops when mid > high
- Result: all 0s, then 1s, then 2s in order

Full Transcript

The Dutch National Flag algorithm partitions an array with elements 0,1,2 into three parts using three pointers: low, mid, and high. Initially, low and mid start at the beginning and high at the end. We check the element at mid: if it is 0, we swap it with the element at low and move both pointers forward; if it is 1, we just move mid forward; if it is 2, we swap it with the element at high and move high backward without moving mid. This process continues until mid passes high, ensuring the array is sorted with all 0s first, then 1s, then 2s. The execution table shows each step with pointer positions and array state, clarifying why mid sometimes does not move after swapping with high. Key moments address common confusions about pointer movements and loop termination.