ASSIGNMENT 8

📌 Problem Statement

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

⚠️ Constraint:
You cannot use built-in sorting functions.

---

🧪 Examples

Example 1

Input:  [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]

Example 2

Input:  [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]

---

💡 Optimal Approach: Dutch National Flag Algorithm

This problem can be solved efficiently using the Dutch National Flag Algorithm, which works in:

• ⏱ Time Complexity: O(n) (single pass)
• 📦 Space Complexity: O(1) (no extra space)

---

🧠 Idea Behind the Algorithm

We divide the array into three regions:

• 0s region → beginning
• 1s region → middle
• 2s region → end

We use three pointers:

• low → position for next 0
• mid → current element
• high → position for next 2

---

🔄 Algorithm Steps

1. Initialize:

   low = 0, mid = 0, high = n - 1

1. Traverse while mid <= high:

• If arr[mid] == 0: → Swap arr[low] and arr[mid], increment both low and mid
• If arr[mid] == 1: → Just move mid
• If arr[mid] == 2: → Swap arr[mid] and arr[high], decrement high

---

💻 Python Implementation

def sort_array(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 usage
arr = [0, 1, 2, 0, 1, 2]
print(sort_array(arr))

---

🧾 Output

[0, 0, 1, 1, 2, 2]

---

🔍 Dry Run (Quick Insight)

For input:

[0, 1, 2, 0, 1, 2]

• 0 → moved to front
• 2 → moved to end
• 1 → stays in middle

---

• No need for sorting functions ❌
• Solved in one pass ✅
• Uses constant space ✅
• Very common in coding interviews 🔥

---