Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.
1) Create a BST and while creating BST maintain the count i,e frequency of each coming element in same BST. This step may take O(nLogn) time if a self balancing BST is used.
2) Do Inorder traversal of BST and store every element and count of each element in an auxiliary array. Let us call the auxiliary array as ‘count[]‘. Note that every element of this array is element and frequency pair. This step takes O(n) time.
3) Sort ‘count[]‘ according to frequency of the elements. This step takes O(nLohn) time if a O(nLogn) sorting algorithm is used.
4) Traverse through the sorted array ‘count[]‘. For each element x, print it ‘freq’ times where ‘freq’ is frequency of x. This step takes O(n) time.
1) Create a BST and while creating BST maintain the count i,e frequency of each coming element in same BST. This step may take O(nLogn) time if a self balancing BST is used.
2) Do Inorder traversal of BST and store every element and count of each element in an auxiliary array. Let us call the auxiliary array as ‘count[]‘. Note that every element of this array is element and frequency pair. This step takes O(n) time.
3) Sort ‘count[]‘ according to frequency of the elements. This step takes O(nLohn) time if a O(nLogn) sorting algorithm is used.
4) Traverse through the sorted array ‘count[]‘. For each element x, print it ‘freq’ times where ‘freq’ is frequency of x. This step takes O(n) time.
struct
BSTNode
{
struct
BSTNode *left;
int
data;
int
freq;
struct
BSTNode *right;
};
struct
dataFreq
{
int
data;
int
freq;
};
void
sortByFrequency(
int
arr[],
int
n)
{
// Create an empty BST and insert all array items in BST
struct
BSTNode *root = NULL;
for
(
int
i = 0; i < n; ++i)
root = insert(root, arr[i]);
// Create an auxiliary array 'count[]' to store data and
// frequency pairs. The maximum size of this array would
// be n when all elements are different
dataFreq count[n];
int
index = 0;
store(root, count, &index);
// Sort the count[] array according to frequency (or count)
qsort
(count, index,
sizeof
(count[0]), compare);
// Finally, traverse the sorted count[] array and copy the
// i'th item 'freq' times to original array 'arr[]'
int
j = 0;
for
(
int
i = 0; i < index; i++)
{
for
(
int
freq = count[i].freq; freq > 0; freq--)
arr[j++] = count[i].data;
}
}
// A utility function to insert a given key to BST. If element
// is already present, then increases frequency
BSTNode *insert(BSTNode *root,
int
data)
{
if
(root == NULL)
return
newNode(data);
if
(data == root->data)
// If already present
root->freq += 1;
else
if
(data < root->data)
root->left = insert(root->left, data);
else
root->right = insert(root->right, data);
return
root;
}
// Function to copy elements and their frequencies to count[].
void
store(BSTNode *root, dataFreq count[],
int
*index)
{
// Base Case
if
(root == NULL)
return
;
// Recur for left substree
store(root->left, count, index);
// Store item from root and increment index
count[(*index)].freq = root->freq;
count[(*index)].data = root->data;
(*index)++;
// Recur for right subtree
store(root->right, count, index);
}
The above implementation doesn’t guarantee original order of elements with same frequency (for example, 4 comes before 5 in input, but 4 comes after 5 in output). Extend the implementation to maintain original order. For example, if two elements have same frequency then print the one which came 1st in input array.
Read full article from Sort elements by frequency | Set 2 | GeeksforGeeks