Sort elements by frequency | Set 1 | GeeksforGeeks

Print the elements of an array in the decreasing frequency if 2 numbers have same frequency then print the one which came 1st
E.g. 2 5 2 8 5 6 8 8 output: 8 8 8 2 2 5 5 6

METHOD 2(Use BST and Sorting)
1. Insert elements in BST one by one and if an element is already present then increment the count of the node. Node of the Binary Search Tree (used in this approach) will be as follows.

struct tree {   int element;   int first_index /*To handle ties in counts*/   int count; }BST;

2.Store the first indexes and corresponding counts of BST in a 2D array.
3 Sort the 2D array according to counts (and use indexes in case of tie).

Time Complexity: O(nlogn) 

http://www.geeksforgeeks.org/sort-elements-by-frequency-set-2/

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;

    }

}

BSTNode* newNode(int data)

{

    struct BSTNode* node = new BSTNode;

    node->data = data;

    node->left = NULL;

    node->right = NULL;

    node->freq = 1;

    return (node);

}

 

// 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);

}
METHOD 3(Use Hashing and Sorting)
Using a hashing mechanism, we can store the elements (also first index) and their counts in a hash. Finally, sort the hash elements according to their counts.

METHOD 1 (Use Sorting)

  1) Use a sorting algorithm to sort the elements O(nlogn)    
  2) Scan the sorted array and construct a 2D array of element and count O(n).
  3) Sort the 2D array according to count O(nlogn).

There is one issue with above approach (thanks to ankit for pointing this out). If we modify the input to 5 2 2 8 5 6 8 8, then we should get 8 8 8 5 5 2 2 6 and not 8 8 8 2 2 5 5 6 as will be the case.
To handle this, we should use indexes in step 3, if two counts are same then we should first process(or print) the element with lower index. In step 1, we should store the indexes instead of elements.

http://drhanson.s3.amazonaws.com/storage/documents/common.pdf

Read full article from Sort elements by frequency | Set 1 | GeeksforGeeks