# Sorting Array Elements By Frequency (Using STL)

Hello Everyone,

Given an array of integers, sort the array according to frequency of elements. If frequencies of two elements are same, print them in increasing order.

Examples:

Input : arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}
Output : 3 3 3 3 2 2 2 12 12 4 5
Explanation :
No. Freq
2 : 3
3 : 4
4 : 1
5 : 1
12 : 2

Initially we create a map such that map[element] = freq. Once we are done building the map, we create an array of pairs. A pair which stores elements and their corresponding frequency will be used for the purpose of sorting. We write a custom compare function which compares two pairs firstly on the basis of frequency and if there is a tie on the basis of values.

Below is its c++ implementation :

`// C++ program to sort elements by frequency using`

`// STL`

`#include <bits/stdc++.h>`

`using` `namespace` `std;`

` `

`// function to compare two pairs for inbuilt sort`

`bool` `compare(pair<` `int` `,` `int` `> &p1,`

` ` `pair<` `int` `, ` `int` `> &p2)`

`{`

` ` `// If frequencies are same, compare`

` ` `// values`

` ` `if` `(p1.second == p2.second)`

` ` `return` `p1.first < p2.first;`

` ` `return` `p1.second > p2.second;`

`}`

` `

`// function to print elements sorted by freq`

`void` `printSorted(` `int` `arr[], ` `int` `n)`

`{`

` ` `// Store items and their frequencies`

` ` `map<` `int` `, ` `int` `> m;`

` ` `for` `(` `int` `i = 0; i < n; i++)`

` ` `m[arr[i]]++;`

` `

` ` `// no of distinct values in the array`

` ` `// is equal to size of map.`

` ` `int` `s = m.size();`

` `

` ` `// an array of pairs`

` ` `pair<` `int` `, ` `int` `> p[s];`

` `

` ` `// Fill (val, freq) pairs in an array`

` ` `// of pairs.`

` ` `int` `i = 0;`

` ` `for` `(` `auto` `it = m.begin(); it != m.end(); ++it)`

` ` `p[i++] = make_pair(it->first, it->second);`

` `

` ` `// sort the array of pairs using above`

` ` `// compare function.`

` ` `sort(p, p + s, compare);`

` `

` ` `cout << ` `"Elements sorted by frequency are: "` `;`

` ` `for` `(` `int` `i = 0; i < s; i++)`

` ` `{`

` ` `int` `freq = p[i].second;`

` ` `while` `(freq--)`

` ` `cout << p[i].first << ` `" "` `;`

` ` `}`

`}`

` `

`// driver program`

`int` `main()`

`{`

` ` `int` `arr[] = {2, 3, 2, 4, 5, 12, 2, 3,`

` ` `3, 3, 12};`

` ` `int` `n = ` `sizeof` `(arr)/ ` `sizeof` `(arr);`

` ` `printSorted(arr, n);`

` ` `return` `0;`

`}`

Output:

Elements sorted by frequency are: 3 3 3 3 2 2 2 12 12 4 5

Time Complexity : O(n Log n)