Efficiently Sort an Array with many Duplicated Values

Given an array with many duplicated elements, write an algorithm to efficiently sort it in linear time where the order of equal elements doesn’t matter.

 

For example,


Input:  { 4, 2, 40, 10, 10, 1, 4, 2, 1, 10, 40 }

Output: { 1, 1, 2, 2, 4, 4, 10, 10, 10, 40, 40 }

 
 

Simple solution would to use efficient sorting algorithms like Merge Sort, QuickSort, Heap Sort, etc that can solve this problem in O(nlog(n)) time, but those will not take advantage of the fact that there are many duplicated values in the array.

 
A better approach is to use Counting sort. This will bring down the time complexity to O(n + k) where k is the range of the input. Below is implementation in C –

 

Download   Run Code

Output:

1 1 2 2 4 4 10 10 10 40 40

 
The problem with the counting sort is its high space complexity O(k) when k >> n i.e. variation in keys is significantly greater than the number of items. Here is another implementation that calculates the exact range of array elements instead of making any assumption by calculating the difference between the maximum and minimum key values.

 
We can also use hash table to effictively solve this problem. The idea is to iterate through the array once and use a hash table the count the number of occurrences of the individual elements. Then we sort the unique elements present in the hash table according to the natural ordering. Finally, we overwrite the input array with sorted elements depending on frequencies stored in the hash table.

The time complexity of this solution would be O(nlog(k)) where k is the number of unique elements present in an array of size n, which can be much less than O(nlog(n)) if range of input elements is small. Auxiliary space used by the program is O(k). Below is implementation in C++ –

 

Download   Run Code

Output:

1 1 2 2 4 4 10 10 10 40 40

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz