Sorting an Array of 0s, 1s and 2s - CA08

Introduction

Sorting is a fundamental concept in programming. In this problem, we are given an array that contains only three distinct values: 0s, 1s, and 2s. The goal is to sort the array in ascending order without using any built-in sorting functions.

This problem is important because it introduces an efficient technique known as the Dutch National Flag Algorithm.

Problem Statement

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

Constraints:

• Do not use built-in sorting functions
• Aim for an efficient solution

Example 1

Input:

arr = [0, 1, 2, 0, 1, 2]

Output:

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

Example 2

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]

Approach 1: Counting Method

Python Implementation (Counting)

def sort_array(arr):
    count0 = arr.count(0)
    count1 = arr.count(1)
    count2 = arr.count(2)

    i = 0

    # Fill 0s
    for _ in range(count0):
        arr[i] = 0
        i += 1

    # Fill 1s
    for _ in range(count1):
        arr[i] = 1
        i += 1

    # Fill 2s
    for _ in range(count2):
        arr[i] = 2
        i += 1

    return arr

# Example usage
arr = [0, 1, 2, 0, 1, 2]
print(sort_array(arr))

Conclusion

Sorting an array of 0s, 1s, and 2s is a classic problem that demonstrates how understanding patterns in data can lead to highly efficient solutions. The Dutch National Flag Algorithm is the most optimal approach and is widely used in coding interviews.

Mastering this problem helps in building strong problem-solving skills and understanding in-place algorithms.