This post is completed by 2 users

Add to List 
Sort 0, 1, 2 in an array  Part 2
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:
Earlier we have seen the counting logic to solve this problem. In this article we will solve it using Dutch National Flag Algorithm  Given `N' objects coloured red, white or blue, sort them so that objects of the same colour are adjacent, with the colours in the order red, white and blue. We will consider red as 0's, white as 1's and blue as 2's.
3way Partitioning  Pseudo Code:
Given: input[] low = 0, mid = 0 and high = N while(mid<=high) case input[mid] 0: input[mid] = input[low], input[low]=0, low++, mid++; 1: mid++ 2: input[mid] = input[high], input[high]=2, high.
Walkthrough:
Time Complexity: O(N)
Output:
Given array: [0, 0, 2, 0, 2, 0, 0, 1, 2] Sorted array: [0, 0, 0, 0, 0, 1, 2, 2, 2]
Also Read: