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