Introduction:

In the realm of algorithmic problem-solving, efficient sorting techniques hold great significance. In this article, we delve into a fascinating problem that involves sorting an array containing only 0s, 1s, and 2s. The task at hand is to rearrange the elements in ascending order, with all the 0s appearing first, followed by the 1s, and finally the 2s. We will explore an optimized algorithm that accomplishes this in linear time complexity.

Problem Statement:

Given an array of size N, where each element can take on the values 0, 1, or 2, the objective is to sort the array in ascending order. The task is to rearrange the elements such that all the 0s appear before the 1s, and all the 1s appear before the 2s.

Example Scenarios:

Let's consider a few examples to illustrate the problem and its expected output:

Example 1:

Input: N = 5 arr[] = [0, 2, 1, 2, 0]

Output: 0 0 1 2 2

Explanation: The array contains two 0s, one 1, and two 2s. After sorting the array in ascending order, the resulting sequence is [0, 0, 1, 2, 2].

Example 2:

Input: N = 3 arr[] = [0, 1, 0]

Output: 0 0 1

Explanation: In this scenario, the array consists of two 0s and one 1. After sorting, the elements are rearranged to form the sequence [0, 0, 1].

Bruteforce Approach :

arr.sort()

Thats it not much more code. . . But this approach is not convinced by the recruiters and it may lead to questions like implement your own sort function without using any Builtin-sort method.

So I came up with an Optimal Solution Approach using a popular Algorithm named

👉 "Dutch National Flag Algorithm" 👈

Optimal Approach:

The Dutch National Flag Algorithm To solve this problem efficiently, we will employ the Dutch National Flag Algorithm. This algorithm partitions the array into three sections, representing the 0s, 1s, and 2s, and rearranges the elements accordingly.

Algorithm Steps:

Initialize three pointers: low, mid, and high. Set low and mid to the starting index of the array (0), and high to the ending index (n - 1).
Iterate through the array using the mid pointer, until it reaches the high pointer.
- If the element at arr[mid] is 0, swap it with the element at arr[low] and increment both low and mid pointers.
- If the element at arr[mid] is 1, simply increment the mid pointer.
- If the element at arr[mid] is 2, swap it with the element at arr[high] and decrement the high pointer.
Repeat step 2 until the mid pointer crosses the high pointer.

Pseudocode:

The following is the implementation of the sort012() function that sorts the array in place:

def sort012(arr, n):
    low = 0
    mid = 0
    high = n - 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

Time and Space Complexity Analysis:

The time complexity of the algorithm is O(N), where N is the size of the input array. The algorithm performs a single pass through the array, resulting in linear time complexity. The auxiliary space complexity is O(1)

as the sorting is done in place without requiring any additional data structures.

Conclusion:

In this article, we explored an interesting problem of sorting an array of 0s, 1s, and 2s in ascending order. We discussed an optimized algorithm, known as the Dutch National Flag Algorithm, which efficiently partitions the array and rearranges the elements. By implementing this algorithm, we can achieve the desired sorting in linear time complexity. Understanding and implementing such algorithms expands our problem-solving skills and equips us with efficient techniques for tackling similar challenges.

I hope you found this article enlightening and enjoyable. If you have any questions or would like to explore more exciting topics related to algorithms and data structures, stay tuned for our daily articles.

Happy coding! ✨

Balaji.dev