Sort an array of 0s, 1s & 2s. Implement an efficient algorithm

Arrays & Strings

Problem:-

                Sort an array of 0s, 1s & 2s, i.e element at each index of the array is either 0, 1 or 2 and we need to place all 0s first, then 1s and finally all 2s.  

 Solution: 

              After implementing an efficient algorithm to sort an array of 0s & 1s, a very common follow up question is to sort the array of 0s, 1s & 2s.

             Again, we won't consider the counting approach rather would go for a 1 pass approach in which the sorting would be done by traversing the array only once.
 

            We need to divide the array into 3 parts.
            

            Say 'i' points to index 0 & 'j' points to index n-1.
 

We will start traversing from the end of array & 'k' is the iterator starting at index n-1.
If arr(k) is 0, then swap arr(i) & arr(k) and increment 'i'.
If arr(k) is 2, then swap arr(j) & arr(k) and decrement 'j'.
If arr(k) is 1, then don't do anything, simple decrement the iterator 'k'.
 

In this way, the array will be divided into 3 portions.