CA 08 - Sort 0s 1s and 2s

Problem Statement

Given an array arr[] containing only 0s, 1s, and 2s. Sort the array in ascending order.

Note: You need to solve this problem without utilizing the built-in sort function.

Examples:

Input: arr[] = [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]
Explanation: 0s, 1s and 2s are segregated into ascending order.

Input: arr[] = [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]
Explanation: 0s, 1s and 2s are segregated into ascending order.

My Goal

For this problem, my goal was to:

Avoid using built-in sorting methods
Understand how to rearrange elements efficiently
Solve the problem in a single pass
Use constant extra space

Solution

I used the Dutch National Flag Algorithm, which is perfect for this type of problem.

Idea:

We maintain three pointers:

l → position for next 0
m → current element
h → position for next 2

Steps:
If element is 0 → swap with l, move both l and m
If element is 1 → just move m
If element is 2 → swap with h, move h

This ensures all elements are sorted in one pass.

Solution Code (Python)

a = [0, 1, 2, 0, 1, 2]

l = 0
m = 0
h = len(a) - 1

while m <= h:
    if a[m] == 0:
        a[l], a[m] = a[m], a[l]
        l += 1
        m += 1
    elif a[m] == 1:
        m += 1
    else:
        a[m], a[h] = a[h], a[m]
        h -= 1

print(a)

Explanation:
l keeps track of where next 0 should go
h keeps track of where next 2 should go
m scans the array
Each element is placed in correct position in one traversal