How to Sort an Array of 0s, 1s and 2s

How to Sort an Array of 0s, 1s and 2s

Given an array A[] of 0s, 1s, and 2s of size N, the task is to write a function that can sort an array of 0s, 1s, and 2s in ascending order such that 0s are in the beginning followed by all 1s and then 2s at the end, and without using any internal or inbuilt sorting function or library.

Examples Input: {0, 1, 2, 0, 1, 2} Output: {0, 0, 1, 1, 2, 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} Well, there is no denying that that might be many approaches through which we can sort an array of 0s, 1s, and 2s, but in this blog, we will only see 3 approaches that we think were the best and the easiest among all other approaches.

Let’s start…

Index The Brute Force Approach The Counting Approach The Three Pointer Approach — Dutch National Flag Approach The Brute Force Approach In this approach, we are going to compare each number of the array with the one next to it while traversing the array from left to right. We can do this by using a nested loop system in which the outer loop will keep a track of the number and the inner loop will compare it with the rest of the elements of the array.

Algorithm Use two loops for i and j=i+1 elements Compare them to see if the ith element is bigger than the jth element If yes, swap their position so that the smaller element comes first as we have to arrange the elements in ascending order. Print the array Psuedo Code for(i=0 -> N) { for(j=i+1 -> N) { if(A[i] > A[j]) { Swap(A[i], A[j]) } } } Print A

Output A[] = [0, 0, 1, 1, 2, 2]

Time Complexity — O(N²) Space Complexity — O(1)

We all know the time complexity of a sorting algorithm in N log N, but the above approach is taking the time complexity of N² which is even higher. Let’s see how we can optimize it to O)N).


Did you find this article valuable?

Support Ateev Duggal by becoming a sponsor. Any amount is appreciated!