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

Problem Sort 0s, 1s and 2s You are given an array arr[] containing only 0s, 1s, and 2s. Your task is to sort the array in ascending order without using any built-in sort function. Input: [0, 1, 2, 0, 1, 2] → Output: [0, 0, 1, 1, 2, 2] Approach This problem can be efficiently solved using the Dutch National Flag algorithm. We divide the array into three regions: 0s on the left 1s in the middle 2s on the right Steps: Use three pointers: low, mid, and high Traverse the array once: If element is 0 → swap with low, move both pointers forward If element is 1 → move mid forward If element is 2 → swap with high, move high backward This ensures sorting in a single pass without extra space. Complexity: Time Complexity: O(n) Space Complexity: O(1) def sort012(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], arr[high] = arr[high], arr[mid] high -= 1 return arr arr