I want to sort the elements in an array by their frequency.
Input: 2 5 2 8 5 6 8 8
Output: 8 8 8 2 2 5 5 6
Now one solution to this would be:
- Sort the elements using Quick sort or Merge sort. O(nlogn)
- Construct a 2D array of element and count by scanning the sorted array. O(n)
- Sort the constructed 2D array according to count. O(nlogn)
Among the other probable methods that I have read, one uses a Binary Search Tree and the other uses Hashing.
Could anyone suggest me a better algorithm? I know the complexity can't be reduced. But I want to avoid so many traversals.