Home » Data Structure » Array Data Structure

Sort elements by frequency (Solution 2)

C++ implementation to sort elements by frequency.
Submitted by Vikneshwar GK, on January 27, 2022

Solution 1: Sort elements by frequency

Consider an array of size n. The task at hand is to sort the array considering the frequency of the elements such that the most repeated element comes first. In other words, sort them in the decreasing order of the frequency.

Note: When two elements have the same frequency, print them in the same order as it was in the original array.

Example:

Input:
test1[] = {7, 1, 8, 8, 7, 1, 4, 8, 1, 8}

Output:
test1[] = {8, 8, 8, 8, 1, 1, 1, 7, 7, 4}

Input:
test1[] = {8, 8, 4, 5, 8, 1, 4, 8, 2, 8}

Output:
test1[] = {8, 8, 8, 8, 8, 4, 4, 5, 1, 2}

Solution 1: Using Sort

This is a straightforward approach that involves sorting. Although this approach gives an accurate solution for most of the test cases it, however, fails to maintain the order if the array elements have the same frequency. To overcome that, we need to process store the first index in the 2D array as well, so whenever frequency is the same, we can use the index to main the order. It involves the following steps:

• Sort the array using a O(nlog(n)) algorithm
• Iterate through the sorted array and construct a N x 2 2D array such that the first column in the row contains the array element and the second column contains the frequency of that element.
• Now sort this 2D array based on the frequency, such that most repeated elements come first
• Print the array based on the frequency

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

// structure to maintain 2d array
struct ele {
    int count, index, val;
};

// using structure for forming
// 2D array
bool compareValues(struct ele a, struct ele b)
{
    return (a.val < b.val);
}

// Used for sorting by frequency. And if frequency is same,
// then by appearance
bool compareFrequency(struct ele a, struct ele b)
{
    if (a.count != b.count)
        return (a.count < b.count);
    else
        return a.index > b.index;
}

void sortByFrequency(int arr[], int n)
{
    struct ele element[n];
    for (int i = 0; i < n; i++) {

        // Fill Indexes
        element[i].index = i;

        // Initialize counts as 0
        element[i].count = 0;

        // Fill values in structure
        // elements
        element[i].val = arr[i];
    }

    /* Sort the structure elements according to value,
	we used stable sort so relative order is maintained.
	*/
    stable_sort(element, element + n, compareValues);

    /* initialize count of first element as 1 */
    element[0].count = 1;

    /* Count occurrences of remaining elements */
    for (int i = 1; i < n; i++) {

        if (element[i].val == element[i - 1].val) {
            element[i].count += element[i - 1].count + 1;
            element[i - 1].count = -1;
            element[i].index = element[i - 1].index;
        }

        /* Else If previous element is not equal to current
		so set the count to 1 */
        else
            element[i].count = 1;
    }

    /* Now we have counts and first index for each element
	so now sort on the basis of count and in case of tie
	use index to sort.*/
    stable_sort(element, element + n, compareFrequency);
    for (int i = n - 1, index = 0; i >= 0; i--)
        if (element[i].count != -1)
            for (int j = 0; j < element[i].count; j++)
                arr[index++] = element[i].val;
}

// Function is to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
        cout << array[i] << " ";
    cout << endl;
}

// Main function
int main()
{
    int array[100], length;
    cout << "Enter Number of elements: ";
    cin >> length;

    for (int i = 0; i < length; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }

    sortByFrequency(array, length);

    printArray(array, length);

    return 0;
}

Output:

Enter Number of elements: 10
Enter element 1:7
Enter element 2:1
Enter element 3:8
Enter element 4:8
Enter element 5:7
Enter element 6:1
Enter element 7:4
Enter element 8:8
Enter element 9:1
Enter element 10:8
8 8 8 8 1 1 1 7 7 4

Time Complexity

• Sorting the array initially: O(nlog(n))
• Traversing through the array and framing 2D array: O(n)
• Sort according to frequency: O(nlog(n))

Solution 2: Hashing

This is a simple yet optimum approach. It involves hashing mechanism where the elements and their counts are stored in a hash. Sort the hash based on the count and print them.

C++ Implementation:

#include <bits/stdc++.h>

using namespace std;

// Compare function
bool compare(pair<int, pair<int, int> > h1,
    pair<int, pair<int, int> > h2)
{
    if (h1.second.second != h2.second.second)
        return (h1.second.second > h2.second.second);
    else
        return (h1.second.first < h2.second.first);
}

// Function to sort by frequency
void sortByFrequency(int arr[], int n)
{
    unordered_map<int, pair<int, int> > hash; // hash map
    for (int i = 0; i < n; i++) {
        if (hash.find(arr[i]) != hash.end())
            hash[arr[i]].second++;
        else
            hash[arr[i]] = make_pair(i, 1);
    } // store the count of all the elements in the hashmap

    // Iterator to Traverse the Hashmap
    auto it = hash.begin();

    // Vector to store the Final Sortted order
    vector<pair<int, pair<int, int> > > b;
    for (it; it != hash.end(); ++it)
        b.push_back(make_pair(it->first, it->second));

    sort(b.begin(), b.end(), compare);

    // Printing the Sorted sequence
    for (int i = 0; i < b.size(); i++) {
        int count = b[i].second.second;
        while (count--)
            cout << b[i].first << " ";
    }
}

// Main function
int main()
{
    int array[100], length;
    
    cout << "Enter Number of elements: ";
    cin >> length;

    for (int i = 0; i < length; i++) {
        cout << "Enter element " << i + 1 << ":";
        cin >> array[i];
    }
    
    sortByFrequency(array, length);
    
    return 0;
}

Output:

Enter Number of elements: 10
Enter element 1:8
Enter element 2:8
Enter element 3:4
Enter element 4:5
Enter element 5:8
Enter element 6:1
Enter element 7:4
Enter element 8:8
Enter element 9:2
Enter element 10:8
8 8 8 8 8 4 4 5 1 2