Dutch National Flag Three Way Partition in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the low pointer to the start of the array.

DSA C#

int low = [1];

Drag options to blanks, or click blank then click option'

A0

B1

C-1

Darray.Length

Attempts:

3 left

💡 Hint

Common Mistakes

Starting low at 1 skips the first element.

Using -1 causes index errors.

Setting low to array.Length is out of bounds.

The low pointer should start at index 0 to begin partitioning from the start.

2fill in blank

medium

Complete the code to swap elements at indices i and low.

DSA C#

int temp = arr[i]; arr[i] = arr[[1]]; arr[low] = temp;

Drag options to blanks, or click blank then click option'

Apivot

Blow

Ci

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with high moves wrong elements.

Swapping with i does nothing.

Swapping with pivot is incorrect here.

We swap arr[i] with arr[low] to move the smaller element to the front.

3fill in blank

hard

Fix the error in the loop condition to iterate through the array correctly.

DSA C#

while (i [1] high) { /* partition logic */ }

Drag options to blanks, or click blank then click option'

A>=

B>

C<

D<=

Attempts:

3 left

💡 Hint

Common Mistakes

Using < misses the last element.

Using > or >= causes infinite loops or no iteration.

The loop should run while i is less than or equal to high to cover all elements.

4fill in blank

hard

Fill both blanks to correctly update pointers after swapping with high.

DSA C#

int temp = arr[i]; arr[i] = arr[[1]]; arr[[2]] = temp; high--;

Drag options to blanks, or click blank then click option'

Ahigh

Blow

Ci

Dpivot

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping with low instead of high.

Assigning temp to wrong index causes data loss.

Swap arr[i] with arr[high] and assign temp to arr[i], then decrement high.

5fill in blank

hard

Fill all three blanks to complete the partition loop with correct pointer updates.

DSA C#

while (i [1] high) { if (arr[i] < pivot) { Swap(arr, i, [2]); [3]++; i++; } else if (arr[i] > pivot) { Swap(arr, i, high); high--; } else { i++; } }

Drag options to blanks, or click blank then click option'

A<=

Blow

Dhigh

Attempts:

3 left

💡 Hint

Common Mistakes

Using < excludes last element.

Incrementing wrong pointers causes infinite loops.

Loop while i <= high; swap with low pointer; increment low and i after swap.

Practice

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

easy

A. To rearrange an array into three parts based on a pivot value

B. To sort an array in ascending order

C. To find the maximum element in an array

D. To reverse the elements of an array

Solution

1. Step 1: Understand the algorithm's purpose

   The Dutch National Flag algorithm partitions an array into three parts: less than, equal to, and greater than a pivot.

2. Step 2: Compare with other options

   Sorting or finding max are different tasks; reversing is unrelated.

3. Final Answer:

   To rearrange an array into three parts based on a pivot value -> Option A

4. Quick Check:

   Partitioning = Rearranging into three parts [OK]

Hint: Remember: It splits array into three groups around a pivot [OK]

Common Mistakes:

• Confusing partitioning with sorting
• Thinking it finds max or min values
• Assuming it reverses the array

2. Which of the following is the correct C# syntax to swap two elements arr[i] and arr[j] in an array?

easy

A. arr[i] = arr[j]; arr[j] = arr[i];

B. int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

C. swap(arr[i], arr[j]);

D. arr.Swap(i, j);

Solution

1. Step 1: Understand swapping in C# arrays

   Swapping requires a temporary variable to hold one value while assigning the other.

2. Step 2: Check each option

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; uses a temp variable correctly; B overwrites values; C and D are invalid syntax in C#.

3. Final Answer:

   int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; -> Option B

4. Quick Check:

   Swap needs temp variable [OK]

Hint: Use a temp variable to swap two array elements [OK]

Common Mistakes:

• Overwriting values without temp variable
• Using non-existent swap functions
• Confusing syntax from other languages

3. What will be the output array after applying the Dutch National Flag partition on arr = [2, 0, 2, 1, 1, 0] with pivot = 1?

medium

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

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

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

   Resulting array is [0, 0, 1, 1, 2, 2].

3. Final Answer:

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

4. Quick Check:

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

Hint: Group elements less, equal, then greater than pivot [OK]

Common Mistakes:

• Not grouping equal elements in the middle
• Mixing order of groups
• Ignoring pivot value placement

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

int low = 0, mid = 0, high = arr.Length - 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. Variables low, mid, high are not declared

B. Loop condition should be mid < high, not mid <= high

C. Pivot value is not initialized

D. Swap method is called incorrectly; should swap array elements by index

Solution

1. Step 1: Check Swap usage

   Swap(arr[low], arr[mid]) passes values, not indices; swapping values won't affect array elements.

2. Step 2: Correct swap call

   Swap should be a method swapping elements by indices or use a temp variable to swap arr[low] and arr[mid].

3. Final Answer:

   Swap method is called incorrectly; should swap array elements by index -> Option D

4. Quick Check:

   Swap must affect array elements, not just values [OK]

Hint: Swap array elements by index, not by passing values [OK]

Common Mistakes:

• Passing values instead of indices to swap
• Incorrect loop boundary conditions
• Forgetting to initialize pivot

5. Given an array arr = [3, 5, 2, 3, 8, 3, 1] and pivot = 3, how would you modify the Dutch National Flag algorithm to partition the array so that all elements less than 3 come first, then all elements equal to 3, and finally all elements greater than 3? What is the final array?

hard

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

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

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

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

Solution

1. Step 1: Apply Dutch National Flag partition with pivot 3

   Group elements less than 3: 1,2; equal to 3: 3,3,3; greater than 3: 5,8.

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

   Final array is [2, 1, 3, 3, 3, 5, 8].

3. Final Answer:

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

4. Quick Check:

   Partitioned array = [2,1,3,3,3,5,8] [OK]

Hint: Place less, equal, then greater elements around pivot [OK]

Common Mistakes:

• Mixing order of groups
• Not grouping all equal elements together
• Ignoring elements equal to pivot