|
This post is completed by 4 users
|
Add to List |
513. 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)
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 to read about - Sort 0's, the 1's and 2's in the given array - Dutch National Flag algorithm