if I am having an array where nearly 90% of its values are equal and i want to sort it. what would be the best sorting method should I use ?
5
-
3Counting sort should be effective.Elliott Frisch– Elliott Frisch2018-05-12 16:05:44 +00:00Commented May 12, 2018 at 16:05
-
1When you say "values", which type are they?Mike 'Pomax' Kamermans– Mike 'Pomax' Kamermans2018-05-12 16:08:21 +00:00Commented May 12, 2018 at 16:08
-
1well it is a big class that have some integer to compare with in itA.khaled– A.khaled2018-05-12 16:13:25 +00:00Commented May 12, 2018 at 16:13
-
1have a map with key:list to store all the duplicated values and store the unique values in a set then sort the set..Surely– Surely2018-05-12 16:23:51 +00:00Commented May 12, 2018 at 16:23
-
2thank you all, that was so helpfulA.khaled– A.khaled2018-05-12 16:27:42 +00:00Commented May 12, 2018 at 16:27
Add a comment
|
1 Answer
If you have many repetitions in the array, then you can use a different approach to sort it. For this IMO, self balancing binary tree like AVL or Red black tree would be better approach than any other sorting algorithms.
The idea is to extend tree node to have count of keys also.
class Node {
int key;
Node left, right;
int count; // Added to handle duplicates
// Other tree node info for balancing like height in AVL
}
Below is complete algorithm using AVL tree.
1) Create an empty AVL Tree with count as an additional field.
2) Traverse input array and do following for every element ‘arr[i]’
a) If arr[i] is not present in tree, then insert it and initialize count as 1 b) Else increment its count in tree.3) Do Inorder Traversal of tree. While doing inorder put every key its count times in arr[].
The 2nd step takes O(n Log m) time and 3rd step takes O(n) time. So overall time complexity is O(n Log m), where m is number of distinct elements.
The detailed explanation and implementation are given here: Geeks for Geeks
