Sort 0s, 1s, 2s

Introduction

Sorting an array containing only 0s, 1s, and 2s is a common problem in data structures. It is also known as the Dutch National Flag problem.

---

Problem Statement

Given an array containing only 0s, 1s, and 2s, sort the array in ascending order without using extra space.

---

Approach (Dutch National Flag Algorithm)

We use three pointers:

1. low → for 0s
2. mid → for traversal
3. high → for 2s

Steps:

• If element is 0 → swap with low and move both low and mid
• If element is 1 → move mid
• If element is 2 → swap with high and move high

---

Python Code

python
def sort_colors(arr):
    low = 0
    mid = 0
    high = len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1

        elif arr[mid] == 1:
            mid += 1

        else:  # arr[mid] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

    return arr

# Example
arr = [2, 0, 2, 1, 1, 0]
print("Sorted Array:", sort_colors(arr))


## Input
 [2, 0, 2, 1, 1, 0]

## output
 [0, 0, 1, 1, 2, 2]