Dutch National Flag Three Way Partition in DSA C - 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

↓

mid++

↓

Swap arr[mid

↓

Repeat loop

We use three pointers low, mid, and high to rearrange the array in one pass by swapping elements based on their value compared to the pivot.

Execution Sample

DSA C

void dutch_flag_partition(int arr[], int n) {
  int low = 0, mid = 0, high = n - 1;
  while (mid <= high) {
    if (arr[mid] == 0) swap(arr[low++], arr[mid++]);
    else if (arr[mid] == 1) mid++;
    else swap(arr[mid], arr[high--]);
  }
}

This code partitions an array containing 0s, 1s, and 2s so that all 0s come first, then 1s, then 2s.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Start	0	0	8	[2, 0, 2, 1, 1, 0, 0, 2, 1]	Initial pointers set
2	Check arr[mid]=2, swap arr[mid] and arr[high]	0	0	7	[1, 0, 2, 1, 1, 0, 0, 2, 2]	Swap arr[0]<->arr[8], high=7
3	Check arr[mid]=0, swap arr[low] and arr[mid]	0	0	7	[1, 0, 2, 1, 1, 0, 0, 2, 2]	No swap, mid=1
4	Check arr[mid]=0, swap arr[low] and arr[mid]	0	1	7	[0, 1, 2, 1, 1, 0, 0, 2, 2]	Swap arr[0]<->arr[1], low=1, mid=2
5	Check arr[mid]=2, swap arr[mid] and arr[high]	1	2	7	[0, 1, 2, 1, 1, 0, 0, 2, 2]	Swap arr[2]<->arr[7], high=6
6	Check arr[mid]=2, swap arr[mid] and arr[high]	1	2	6	[0, 1, 2, 1, 1, 0, 0, 2, 2]	Swap arr[2]<->arr[6], high=5
7	Check arr[mid]=0, swap arr[low] and arr[mid]	1	2	5	[0, 0, 1, 1, 1, 0, 2, 2, 2]	Swap arr[1]<->arr[2], low=2, mid=3
8	Check arr[mid]=1, mid++	2	3	5	[0, 0, 1, 1, 1, 0, 2, 2, 2]	mid=3
9	Check arr[mid]=1, mid++	2	4	5	[0, 0, 1, 1, 1, 0, 2, 2, 2]	mid=4
10	Check arr[mid]=1, mid++	2	5	5	[0, 0, 1, 1, 1, 0, 2, 2, 2]	mid=5
11	Check arr[mid]=0, swap arr[low] and arr[mid]	2	5	5	[0, 0, 0, 1, 1, 1, 2, 2, 2]	Swap arr[2]<->arr[5], low=3, mid=6
12	mid=6 > high=5, exit loop	3	6	5	[0, 0, 0, 1, 1, 1, 2, 2, 2]	Loop ends as mid > high

💡 Loop ends when mid (6) becomes greater than high (5), meaning all elements are partitioned.

Variable Tracker

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

Key Moments - 3 Insights

Why do we not increment mid when swapping with high?

Because the element swapped from high to mid is unprocessed, we must check it again. This is shown in steps 5 and 6 where mid stays the same after swapping with high.

Why do we increment both low and mid when swapping with low?

Because the element swapped from low is already processed (0), so after swapping, both pointers move forward. See steps 4 and 7 where low and mid both increment.

What stops the loop from running forever?

The loop condition mid <= high ensures termination. Each step either increments mid or decrements high, moving pointers closer. Step 12 shows mid surpassing high, ending the loop.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the array state?

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

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

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

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

💡 Hint

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

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

A Step 10

B Step 12

C Step 11

D Step 9

💡 Hint

Look at the 'mid' and 'high' values in the execution_table rows; step 12 shows mid=6 and high=5.

If we swapped arr[mid] and arr[high] but incremented mid immediately, what would happen?

A Some 2s might remain unprocessed in the middle

B The algorithm would still work correctly

C The array would be sorted in reverse order

D Low pointer would move incorrectly

💡 Hint

Refer to key_moments about why mid is not incremented after swapping with high.

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- low and mid start at 0, high at end
- If arr[mid]==0: swap with arr[low], increment low and mid
- If arr[mid]==1: increment mid
- If arr[mid]==2: swap with arr[high], decrement high
- Loop ends when mid > high
- One pass, in-place partitioning

Full Transcript

The Dutch National Flag algorithm partitions an array of 0s, 1s, and 2s in one pass 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, because the swapped element needs to be checked. This continues until mid passes high, ensuring all 0s are at the start, 1s in the middle, and 2s at the end. The execution table shows each step with pointer positions and array state, clarifying how the array changes. Key moments explain why mid is not incremented after swapping with high and why both low and mid move after swapping with low. The quiz tests understanding of pointer movements and array states during execution.

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 quicksort

B. To rearrange an array into three parts: less than, equal to, and greater than a pivot

C. To find the maximum element in an array

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 value: elements less than pivot, equal to pivot, and greater than pivot.

2. Step 2: Compare with other options

   Options A, C, and D describe different operations: sorting, finding max, and reversing, which are not the main goal here.

3. Final Answer:

   To rearrange an array into three parts: less than, equal to, and greater than a pivot -> Option B

4. Quick Check:

   Partitioning = three parts [OK]

Hint: Remember: three parts based on pivot value [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare the pointers used in the Dutch National Flag algorithm in C?

easy

A. int low = 0, mid = 0, high = n - 1;

B. int low, mid, high = 0;

C. int low = n, mid = 0, high = n - 1;

D. int low = 0, mid = n - 1, high = 0;

Solution

1. Step 1: Understand pointer initialization

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

2. Step 2: Check each option

   int low = 0, mid = 0, high = n - 1; correctly initializes low and mid to 0, high to n-1. Others have incorrect initial values.

3. Final Answer:

   int low = 0, mid = 0, high = n - 1; -> Option A

4. Quick Check:

   Pointers start: low=0, mid=0, high=n-1 [OK]

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

Common Mistakes:

• Setting low or mid to n or n-1 incorrectly
• Not initializing all pointers
• Confusing variable assignments

3. What will be the output array after applying the Dutch National Flag algorithm on arr = {2, 0, 2, 1, 1, 0} with pivot = 1?

medium

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

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

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

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

Solution

1. Step 1: Partition array around pivot 1

   Elements less than 1: 0,0; equal to 1: 1,1; greater than 1: 2,2.

2. Step 2: Arrange in order less, equal, greater

   So the 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: Group less, equal, greater around pivot [OK]

Common Mistakes:

• Mixing order of groups
• Not grouping equal elements correctly
• Assuming full sorting instead of partitioning

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

void dnfPartition(int arr[], int n, int pivot) {
  int low = 0, mid = 0, high = n - 1;
  while (mid <= high) {
    if (arr[mid] < pivot) {
      swap(arr[low], arr[mid]);
      low++;
      mid++;
    } else if (arr[mid] == pivot) {
      mid++;
    } else {
      swap(arr[mid], arr[high]);
      high--;
    }
  }
}

medium

A. Pivot comparison should use > instead of <

B. The loop condition should be mid < high

C. Pointers low and mid should start at n-1

D. swap function is not defined for array elements

Solution

1. Step 1: Check swap usage

   The code uses swap(arr[low], arr[mid]) but swap is not a built-in function in C for array elements.

2. Step 2: Verify other parts

   Loop condition and pointer initialization are correct. Pivot comparisons are correct as per algorithm.

3. Final Answer:

   swap function is not defined for array elements -> Option D

4. Quick Check:

   Missing swap definition = error [OK]

Hint: Remember to define or implement swap for array elements [OK]

Common Mistakes:

• Assuming swap is built-in for arrays in C
• Changing loop condition incorrectly
• Wrong pointer initialization

5. Given an array arr = {3, 5, 2, 3, 8, 3, 1, 3} and pivot = 3, how many swaps will the Dutch National Flag algorithm perform to partition the array?

hard

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Trace swaps during partition

   Initial pointers: low=0, mid=0, high=7. - mid=0 (3 == pivot): mid++ (0 swaps) - mid=1 (5 > pivot): swap arr[mid] and arr[high] -> swap(5,3), high=6 (1 swap) - mid=1 (now 3 == pivot): mid++ (1 swap) - mid=2 (2 < pivot): swap arr[low] and arr[mid] -> swap(3,2), low=1, mid=3 (2 swaps) - mid=3 (3 == pivot): mid++ (2 swaps) - mid=4 (8 > pivot): swap arr[mid] and arr[high] -> swap(8,1), high=5 (3 swaps) - mid=4 (now 1 < pivot): swap arr[low] and arr[mid] -> swap(3,1), low=2, mid=5 (4 swaps) - mid=5 (3 == pivot): mid++ (4 swaps) Loop ends as mid=6 > high=5.

2. Step 2: Count total swaps

   Total swaps performed = 4

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Count swaps carefully = 4 [OK]

Hint: Count swaps during each pointer move carefully [OK]

Common Mistakes:

• Counting swaps only when mid moves
• Ignoring swaps after swapping with high
• Miscounting swaps when elements equal pivot