Sort Colors Two Pointer Dutch Flag in DSA Python - Build from Scratch

Sort Colors Using Two Pointer Dutch Flag Algorithm

📖 Scenario: You are organizing colored balls in a line. The balls can be red, white, or blue, represented by numbers 0, 1, and 2 respectively. Your task is to sort them so that all reds come first, then whites, and finally blues.

🎯 Goal: Build a program that sorts a list of colors represented by 0s, 1s, and 2s using the two-pointer Dutch Flag algorithm.

📋 What You'll Learn

Create a list called colors with the exact values [2, 0, 2, 1, 1, 0].

Create two pointer variables called low and high initialized to 0 and len(colors) - 1 respectively.

Use a while loop with a pointer current to sort the list in-place using the Dutch Flag algorithm.

Print the sorted colors list at the end.

💡 Why This Matters

🌍 Real World

Sorting colored objects or items quickly without extra space is useful in manufacturing and organizing tasks.

💼 Career

Understanding in-place sorting algorithms like Dutch Flag helps in software roles involving data processing and optimization.

1

Create the initial list of colors

Create a list called colors with these exact values: [2, 0, 2, 1, 1, 0].

DSA Python

# Create the list colors with the given values
# Your code here

Hint

Use square brackets to create the list and include the numbers exactly as shown.

2

Initialize two pointers for sorting

Create two variables called low and high. Set low = 0 and high = len(colors) - 1.

DSA Python

colors = [2, 0, 2, 1, 1, 0]
# Initialize low and high pointers
# Your code here

Hint

Remember, len(colors) gives the number of items in the list.

3

Sort the colors using the Dutch Flag algorithm

Create a variable current and set it to 0. Use a while loop with the condition current <= high. Inside the loop, do the following:
- If colors[current] == 0, swap colors[current] and colors[low], then increment low and current.
- Else if colors[current] == 2, swap colors[current] and colors[high], then decrement high.
- Else, increment current.

DSA Python

colors = [2, 0, 2, 1, 1, 0]
low = 0
high = len(colors) - 1
# Implement the Dutch Flag sorting algorithm
# Your code here

Hint

Use swapping to move 0s to the front and 2s to the end. Increase or decrease pointers accordingly.

4

Print the sorted colors list

Print the colors list to show the sorted order.

DSA Python

colors = [2, 0, 2, 1, 1, 0]
low = 0
high = len(colors) - 1
current = 0
while current <= high:
    if colors[current] == 0:
        colors[current], colors[low] = colors[low], colors[current]
        low += 1
        current += 1
    elif colors[current] == 2:
        colors[current], colors[high] = colors[high], colors[current]
        high -= 1
    else:
        current += 1
# Print the sorted colors list
# Your code here

Hint

Use print(colors) to display the sorted list.

Practice

1. What is the main goal of the Sort Colors Two Pointer Dutch Flag algorithm?

easy

A. To reverse the elements of an array

B. To sort any array of integers in ascending order

C. To find the maximum element in an array

D. To sort an array containing only 0s, 1s, and 2s in a single pass

Solution

1. Step 1: Understand the problem context

   The algorithm is designed specifically for arrays with only three distinct values: 0, 1, and 2.

2. Step 2: Identify the algorithm's purpose

   It sorts these values in one pass using two pointers, placing all 0s first, then 1s, then 2s.

3. Final Answer:

   To sort an array containing only 0s, 1s, and 2s in a single pass -> Option D

4. Quick Check:

   Sort colors = sort 0,1,2 in one pass [OK]

Hint: Remember: Dutch Flag sorts 0,1,2 in one pass [OK]

Common Mistakes:

• Thinking it sorts any array, not just 0,1,2
• Confusing it with general sorting algorithms
• Assuming it requires multiple passes

2. Which of the following is the correct initialization of pointers in the Dutch Flag algorithm in Python?

easy

A. low, mid, high = 0, len(nums) - 1, 0

B. low, mid, high = 0, 0, len(nums) - 1

C. low, mid, high = len(nums) - 1, 0, 0

D. low, mid, high = len(nums) - 1, len(nums) - 1, 0

Solution

1. Step 1: Recall pointer roles

   Low and mid start at the beginning (index 0), high starts at the end (last index).

2. Step 2: Match initialization

   So, low = 0, mid = 0, high = len(nums) - 1 is correct.

3. Final Answer:

   low, mid, high = 0, 0, len(nums) - 1 -> Option B

4. Quick Check:

   Pointers start low=0, mid=0, high=end [OK]

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

Common Mistakes:

• Swapping high and mid initialization
• Starting pointers at wrong indices
• Using length instead of length-1 for high

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

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

medium

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

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

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

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

Solution

1. Step 1: Trace the algorithm on input

   Initially nums = [2,0,2,1,1,0]. The algorithm swaps 0s to front, 2s to end, 1s stay in middle.

2. Step 2: Final sorted array

   After the loop, nums becomes [0,0,1,1,2,2], sorted by color.

3. Final Answer:

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

4. Quick Check:

   Sorted colors = [0,0,1,1,2,2] [OK]

Hint: Remember: 0s front, 1s middle, 2s end [OK]

Common Mistakes:

• Not swapping correctly when nums[mid] == 2
• Incrementing mid after swapping with high
• Confusing order of pointers

4. Identify the bug in the following Dutch Flag algorithm code:

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

medium

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

B. Pointers low and mid are initialized incorrectly

C. Swapping logic for nums[mid] == 0 is wrong

D. The decrement of high should be after incrementing mid

Solution

1. Step 1: Analyze loop condition

   The loop runs while mid < high, so it stops when mid == high, missing last element check.

2. Step 2: Correct loop condition

   It should be mid <= high to process all elements including when mid equals high.

3. Final Answer:

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

4. Quick Check:

   Loop must cover mid == high [OK]

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

Common Mistakes:

• Using 'mid < high' misses last element
• Changing pointer initialization unnecessarily
• Incorrect swap logic for 0 or 2

5. Given an array nums = [1, 2, 0, 1, 2, 0, 1], how many swaps will the Dutch Flag algorithm perform to sort it?

hard

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Trace swaps during sorting

   Initial: [1,2,0,1,2,0,1] low=0, mid=0, high=6
   - mid=0 (1): mid=1 (no swap)
   - mid=1 (2): swap(1,6) -> [1,1,0,1,2,0,2] high=5 (swap 1)
   - mid=1 (1): mid=2
   - mid=2 (0): swap(0,2) -> [0,1,1,1,2,0,2] low=1 mid=3 (swap 2)
   - mid=3 (1): mid=4
   - mid=4 (2): swap(4,5) -> [0,1,1,1,0,2,2] high=4 (swap 3)
   - mid=4 (0): swap(1,4) -> [0,0,1,1,1,2,2] low=2 mid=5 (swap 4)

2. Step 2: Total swaps counted

   There are 4 swaps in total during the process.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Count swaps carefully during pointer moves [OK]

Hint: Count swaps when 0 or 2 moves happen [OK]

Common Mistakes:

• Counting pointer moves as swaps
• Missing swaps when swapping with same element
• Not tracing all pointer changes