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.