This is a basic problem within understanding of array as a data structure and operations of sort as an algorithm upon the data structure.
Here we will start with the basics and crawl our way up with finding multiple constraints, hurdles or bottlenecks within our algorithm.
Approach 1
Simple sort
One obvious way is to use the known sorting techniques as section sort, or merge sort or quick sort.
The code goes here Simple Sorting Solution Or shown below
Simplest, but, no one want's it. As in such case we have making no use of the fact that we are having only 3 elements ie, 0, 1, and 2. Instade, we treated every number as a plain integer and sort it.
Approach 2
Hasing Solution
This one is slightly better, here we are taking into account how many times we have encountered, 0's 1's and 2's. Once that is known. By basic number system, we know all 0's occur before 1's and all 1's before 2's. In such a way, we fill up the array, as per the number of 0's then 1's and then 2's.
The code goes here Hashing Solution Or shown below
This too, have few problems
What if the count which we are taking into consideration is out of bound from the integer limit. One can argue that in such cases we can take long value into consideration but still the limit hit's then? BigInteger? But this does not solve our problem. This in fact slows the system and makes it more prone to errors as the size of the array increases.
What if the input is not a static data but a stream of data. In such cases, the input values will continue to come and not stop. In such case, our algorithm would halt upon the counting of 0's 1's and 2's step only, and not move forward. Hence, not making the in place streaming content sorted.
Approach 3
Poniters and Insertion
Upon seeing above hurdles, we come to know that the approach can be improved and adapted to new circumstances.
Here we can have the insertion point's within the array. These points will indicate where the incoming data could be inserted, for 0's 1's and 2's. For any such new upcoming streaming data, we need to look for the apt pointer within the 0, 1, and 2, then insert the upcoming data.
The code goes here Pointer and Insertion Solution Or shown below
In such a way we have, removed the hurdles from the approach for now.
This still seems to have a minor issue within scalability, like what if we have 0 1 2 and 3 within the digits.
In such cases we need to have multiple pointers for insertion and handling would be complex although if that would take place then the problem itself would be changed and would not be Sort Arrays of Zero's One's and Two's
Top comments (0)