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.

Practice

1. What is the main goal of the Dutch National Flag Three Way Partition algorithm?

easy

A. To sort an array in ascending order using bubble sort.

B. To find the maximum element in an array.

C. To rearrange an array so that all elements less than a pivot come first, followed by elements equal to the pivot, then elements greater than the pivot.

D. To reverse the elements of an array.

Solution

1. Step 1: Understand the partitioning goal

   The algorithm divides the array into three parts based on a pivot: less than, equal to, and greater than the pivot.

2. Step 2: Recognize the rearrangement process

   The array is rearranged so that all smaller elements come first, then equal, then larger elements.

3. Final Answer:

   To rearrange an array so that all elements less than a pivot come first, followed by elements equal to the pivot, then elements greater than the pivot. -> Option C

4. Quick Check:

   Partitioning = Rearranging by pivot [OK]

Hint: Remember: three parts - less, equal, greater [OK]

Common Mistakes:

• Confusing it with full sorting algorithms
• Thinking it only separates two groups
• Assuming it finds max or min values

2. Which of the following is the correct way to initialize pointers for the Dutch National Flag algorithm in Python?

easy

A. low = 0; mid = len(arr) - 1; high = 0

B. low = 1; mid = 1; high = len(arr)

C. low = len(arr); mid = 0; high = 0

D. low = 0; mid = 0; high = len(arr) - 1

Solution

1. Step 1: Identify correct pointer initialization

   In the algorithm, low and mid start at 0, and high starts at the last index (length - 1).

2. Step 2: Check each option

   low = 0; mid = 0; high = len(arr) - 1 correctly sets low=0, mid=0, high=len(arr)-1; others have invalid or reversed values.

3. Final Answer:

   low = 0; mid = 0; high = len(arr) - 1 -> Option D

4. Quick Check:

   Pointers start at array ends and middle [OK]

Hint: Start low and mid at 0, high at last index [OK]

Common Mistakes:

• Setting pointers outside array bounds
• Starting mid or low at wrong index
• Confusing high pointer initialization

3. What will be the output of the following code snippet?

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

arr = [2, 0, 2, 1, 1, 0]
dnf_partition(arr, 1)
print(arr)

medium

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

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

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

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

Solution

1. Step 1: Trace the partitioning process

   Initial array: [2, 0, 2, 1, 1, 0], pivot=1. The algorithm moves elements less than 1 to front, equal to middle, greater to end.

2. Step 2: Final array after partition

   After processing, array becomes [0, 0, 1, 1, 2, 2].

3. Final Answer:

   [0, 0, 1, 1, 2, 2] -> Option A

4. Quick Check:

   Partitioned array = [0, 0, 1, 1, 2, 2] [OK]

Hint: Swap less than pivot left, greater right [OK]

Common Mistakes:

• Not swapping correctly when arr[mid] > pivot
• Incrementing mid incorrectly after swap
• Confusing pivot equality handling

4. Identify the error in this Dutch National Flag partition code:

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

medium

A. The while loop condition should be 'mid <= high' instead of 'mid < high'.

B. Pointers low and mid are initialized incorrectly.

C. The swap operation for elements less than pivot is missing.

D. The pivot value is not used in comparisons.

Solution

1. Step 1: Analyze the loop condition

   The loop uses 'mid < high', which misses processing when mid equals high, leaving last element unchecked.

2. Step 2: Correct loop condition

   Changing to 'mid <= high' ensures all elements are processed including the last one.

3. Final Answer:

   The while loop condition should be 'mid <= high' instead of 'mid < high'. -> Option A

4. Quick Check:

   Loop must cover all elements [OK]

Hint: Use 'mid <= high' to cover all elements [OK]

Common Mistakes:

• Using '<' instead of '<=' in loop condition
• Forgetting to increment mid after swaps
• Incorrect pointer initialization

5. Given an array with elements 0, 1, and 2 representing colors red, white, and blue respectively, how would you modify the Dutch National Flag algorithm to sort the array in-place so that all reds come first, whites second, and blues last? Choose the best approach.

hard

A. Sort the array using built-in sort function for simplicity.

B. Use three pointers low, mid, high; swap elements less than 1 to front, equal to 1 stay in middle, greater than 1 to end.

C. Use two pointers only, swapping elements randomly until sorted.

D. Count the number of 0s, 1s, and 2s, then overwrite the array with counted values.

Solution

1. Step 1: Understand the problem context

   We want to sort colors represented by 0,1,2 in order red(0), white(1), blue(2) using Dutch National Flag algorithm.

2. Step 2: Apply three-pointer partitioning

   Using low, mid, high pointers and pivot=1, swap elements less than 1 to front, equal stay middle, greater to end achieves in-place sorting efficiently.

3. Final Answer:

   Use three pointers low, mid, high; swap elements less than 1 to front, equal to 1 stay in middle, greater than 1 to end. -> Option B

4. Quick Check:

   Three-pointer partition sorts colors in one pass [OK]

Hint: Use pivot=1 and three pointers for one-pass sorting [OK]

Common Mistakes:

• Using built-in sort instead of in-place partition
• Trying two pointers only, which is insufficient
• Counting and overwriting instead of partitioning