Sort 0’s, the 1’s, and 2’s in the given array. | Set – 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

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.