|
This post is completed by 2 users
|
Add to List |
514. 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.
3-way 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--.
Walk-through:
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]