Be the first user to complete this post

Add to List 
Sort 0, 1, 2 in an array  Part 1
Given an array of numbers that consists only of three types of integers, which are 0, 1 and 2. Write an algorithm to sort the given array.
Example:
Input: {2, 1, 2, 0, 1, 0} Output: {0, 0, 1, 1, 2, 2} Input: [0, 0, 2, 0, 2, 1, 0, 1, 2] Output: [0, 0, 0, 0, 1, 1, 2, 2, 2]
Approach:
Naive approach would be to sort the array using a best sorting algorithm like merge sort with the time complexity of O(nlogn). Since we have additional information that it contains only 0's, the 1's and 2's.
Use Counting: Idea is simple, iterate the array and count the number of 0's, 1's and 2's. Now fill the fill array, first with 0's then with 1's and at last with 2's.
Time Complexity: O(N)
Complete Code:
Output:
Given array: [0, 0, 2, 0, 2, 1, 0, 1, 2] Sorted Array: [0, 0, 0, 0, 1, 1, 2, 2, 2]
Click here tp read about  Sort 0's, the 1's and 2's in the given array  Dutch National Flag algorithm
Also Read: