CA 08 - Sort 0s 1s and 2s

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 and actually understand how to rearrange elements on my own, while keeping it efficient. I wanted to solve it in a single pass instead of looping multiple times, and also make sure I wasn’t using any extra space, so everything stays in-place and clean.

Solution

I used the Dutch National Flag Algorithm, which is perfect for this type of problem.

The idea is to use three pointers to manage the positions while traversing the array. One pointer keeps track of where the next 0 should go, another pointer is used to check the current element, and the third pointer marks where the next 2 should be placed. This way, we can rearrange elements as we move through the array without needing extra space.

While iterating, if the current element is 0, we swap it with the position meant for 0 and move both pointers forward. If it is 1, we just move ahead since it’s already in the correct place. If it is 2, we swap it with the position meant for 2 and move that pointer backward. By following this process, the array gets sorted in a single 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)

l keeps track of the position where the next 0 should be placed, and h keeps track of where the next 2 should go. The m pointer is used to scan through the array element by element. As m moves through the array, each element is checked and placed in its correct position using swaps, so by the end of a single traversal, the entire array gets sorted.