Examples:

Input:

arr[ ] = {7, 1, 9, 9, 7, 1, 3, 9, 1, 9}

Output:

arr[ ] = {9, 9, 9, 9, 1, 1, 1, 7, 7, 3}


#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++)
    {
   
        cin >> array[i];
    }

    sortByFrequency(array, length);

    return 0;
}

Output:

Enter Number of elements : 10
9 9 3 5 9 1 3 9 2 3

9 9 9 9 3 3 3 5 1 2