Dutch National Flag Three Way Partition in DSA C++ - Execution Trace

Concept Flow - Dutch National Flag Three Way Partition

Start: low=0, mid=0, high=n-1

↓

Check mid <= high?

No→Done

Yes↓

Check arr[mid

↓

Swap arr[low

↓

mid++

↓

Swap arr[mid

↓

Check mid <= high?

The algorithm uses three pointers low, mid, and high to partition the array into three parts: less than pivot, equal to pivot, and greater than pivot, by swapping elements and moving pointers until mid passes high.

Execution Sample

DSA C++

void dutchFlagPartition(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++]);
    else if (arr[mid] == pivot) mid++;
    else swap(arr[mid], arr[high--]);
  }
}

This code partitions the array around the pivot value using three pointers and swaps.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes	Visual State
1	Start	0	0	6	[2, 5, 1, 2, 4, 3, 5]	low=0, mid=0, high=6	2(0) 5(1) 1(2) 2(3) 4(4) 3(5) 5(6)
2	arr[mid]=2 < pivot=3, swap arr[low] and arr[mid]	1	1	6	[2, 5, 1, 2, 4, 3, 5]	low=1, mid=1	2(0) 5(1) 1(2) 2(3) 4(4) 3(5) 5(6)
3	arr[mid]=5 > pivot=3, swap arr[mid] and arr[high]	1	1	5	[2, 5, 1, 2, 4, 3, 5]	high=5	2(0) 5(1) 1(2) 2(3) 4(4) 3(5) 5(6)
4	arr[mid]=3 == pivot=3, mid++	1	2	5	[2, 3, 1, 2, 4, 5, 5]	mid=2	2(0) 3(1) 1(2) 2(3) 4(4) 5(5) 5(6)
5	arr[mid]=1 < pivot=3, swap arr[low] and arr[mid]	2	3	5	[2, 1, 3, 2, 4, 5, 5]	low=2, mid=3	2(0) 1(1) 3(2) 2(3) 4(4) 5(5) 5(6)
6	arr[mid]=2 < pivot=3, swap arr[low] and arr[mid]	3	4	5	[2, 1, 2, 3, 4, 5, 5]	low=3, mid=4	2(0) 1(1) 2(2) 3(3) 4(4) 5(5) 5(6)
7	arr[mid]=4 > pivot=3, swap arr[mid] and arr[high]	3	4	4	[2, 1, 2, 3, 4, 5, 5]	high=4	2(0) 1(1) 2(2) 3(3) 4(4) 5(5) 5(6)
8	arr[mid]=4 > pivot=3, swap arr[mid] and arr[high]	3	4	3	[2, 1, 2, 3, 4, 5, 5]	high=3	2(0) 1(1) 2(2) 3(3) 4(4) 5(5) 5(6)
9	mid > high, stop	3	4	3	[2, 1, 2, 3, 4, 5, 5]	Stop	2(0) 1(1) 2(2) 3(3) 4(4) 5(5) 5(6)

💡 mid (4) > high (3), partition complete

Variable Tracker

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

Key Moments - 3 Insights

Why do we swap arr[mid] with arr[high] when arr[mid] > pivot instead of incrementing mid?

Because the element at arr[high] is unprocessed, swapping brings a new element to mid for checking. This is shown in steps 3, 7, and 8 where mid stays at the same position after swapping.

Why do we increment both low and mid when arr[mid] < pivot?

Because after swapping arr[low] and arr[mid], the element at mid is guaranteed to be less than pivot, so we can safely move both pointers forward. This is seen in steps 2, 5, and 6.

Why does the loop stop when mid > high?

Because all elements beyond high are greater than pivot and processed, so no need to check further. This is the exit condition shown in step 9.

Visual Quiz - 3 Questions

Look at the execution table at step 4, what is the value of 'high' after the operation?

A 6

B 4

C 5

D 3

💡 Hint

Check the 'high' column in the execution_table row for step 4.

At which step does the pointer 'low' first increment to 2?

A Step 6

B Step 5

C Step 7

D Step 3

💡 Hint

Look at the variable_tracker row for 'low' and see when it changes from 1 to 2.

If the pivot was changed to 4, how would the operation at step 8 change?

A It would increment mid instead of swapping

B It would swap arr[low] and arr[mid]

C It would swap arr[mid] and arr[high] again

D It would stop the loop

💡 Hint

Check the condition for arr[mid] == pivot or < pivot in the code and how it affects pointer movement.

Concept Snapshot

Dutch National Flag Partition:
- Use three pointers: low, mid, high
- low to track < pivot, mid current, high > pivot
- Swap arr[low] and arr[mid] if arr[mid]<pivot, increment low and mid
- If arr[mid]==pivot, increment mid
- If arr[mid]>pivot, swap arr[mid] and arr[high], decrement high
- Stop when mid > high
- Result: array partitioned into <pivot | =pivot | >pivot

Full Transcript

The Dutch National Flag algorithm partitions an array into three parts around a pivot value. It uses three pointers: low, mid, and high. Initially, low and mid start at 0, and high at the last index. While mid is less than or equal to high, the element at mid is checked. If it is less than the pivot, it is swapped with the element at low, and both low and mid are incremented. If it equals the pivot, only mid is incremented. If it is greater than the pivot, it is swapped with the element at high, and high is decremented. This process continues until mid passes high, ensuring the array is partitioned into three sections: less than, equal to, and greater than the pivot.

Practice

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

easy

A. To rearrange an array so that all elements less than a pivot come first, then equal, then greater

B. To sort an array in ascending order using quicksort

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

2. Step 2: Recognize the rearrangement purpose

   This helps in sorting or grouping elements efficiently without full sorting.

3. Final Answer:

   To rearrange an array so that all elements less than a pivot come first, then equal, then greater -> Option A

4. Quick Check:

   Partitioning = Rearranging by pivot [OK]

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

Common Mistakes:

• Confusing partition with full sorting
• Thinking it only finds max or min
• Assuming it reverses the array

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 = n - 1, mid = 0, high = 0;

B. int low, mid, high = 0;

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

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

Solution

1. Step 1: Identify pointer initialization

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

2. Step 2: Match correct initialization

   int low = 0, mid = 0, high = n - 1; correctly initializes low and mid to 0, high to n-1.

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Initializing pointers incorrectly
• Setting high to 0 instead of n-1
• Not initializing mid at 0

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. [2, 2, 1, 1, 0, 0]

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

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

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

Solution

1. Step 1: Partition array by pivot 1

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

2. Step 2: Rearrange array accordingly

   Place all 0s first, then 1s, then 2s resulting in [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

   Less, equal, greater order = [0,0,1,1,2,2] [OK]

Hint: Group by less, equal, greater around pivot [OK]

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of groups
• Assuming full sort instead of partition

4. Given the following code snippet for Dutch National Flag partition, what is the error?

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

medium

A. Pivot value is not defined

B. Incorrect swap function usage

C. Loop condition should be mid < high

D. Missing increment of mid when arr[mid] < pivot

Solution

1. Step 1: Analyze pointer increments

   When arr[mid] < pivot, low is incremented but mid is not incremented, causing infinite loop.

2. Step 2: Identify missing mid increment

   Mid must also increment after swapping to move forward.

3. Final Answer:

   Missing increment of mid when arr[mid] < pivot -> Option D

4. Quick Check:

   Increment mid after swap for less than pivot [OK]

Hint: Always increment mid except when swapping with high [OK]

Common Mistakes:

• Forgetting to increment mid after swap with low
• Changing loop condition incorrectly
• Ignoring pivot initialization

5. You have an array arr = [3, 5, 2, 3, 8, 3, 1] and want to partition it using the Dutch National Flag algorithm with pivot = 3. Which of the following is the correct final partitioned array?

hard

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

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

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

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

Solution

1. Step 1: Group elements by pivot 3

   Less than 3: 1, 2; equal to 3: 3, 3, 3; greater than 3: 5, 8.

2. Step 2: Arrange groups in order

   Place less first, then equal, then greater: [1, 2, 3, 3, 3, 5, 8].

3. Step 3: Check options for exact order

   [1, 2, 3, 3, 3, 5, 8] matches the correct partition with greater elements 5 and 8 in any order, which is valid partitioning.

4. Final Answer:

   [1, 2, 3, 3, 3, 5, 8] -> Option A

5. Quick Check:

   Partition order less, equal, greater = [1,2,3,3,3,5,8] [OK]

Hint: Partition keeps groups, order inside groups can vary [OK]

Common Mistakes:

• Assuming full sort instead of partition
• Mixing order of greater elements
• Placing equal elements incorrectly