CA 08 - Sort 0s, 1s, and 2s

Problem:
Given an array containing only 0s, 1s, and 2s, sort it without using any built-in sort function.

Solution: Dutch National Flag Algorithm
We divide the array into three regions:

• Left → all 0s
• Middle → all 1s
• Right → all 2s We maintain 3 pointers:
• low → next position for 0
• mid → current element
• high → next position for 2

💡 Algorithm:

• If current is 0 → swap with low, move both forward
• If current is 1 → move mid
• If current is 2 → swap with high, move high backward

Code:
python
class Solution:
def sort012(self, arr):
low, mid = 0, 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], arr[high] = arr[high], arr[mid]
            high -= 1