Design a way to sort the list of positive integers in the descending order according to frequency of elements. The elements with integers with higher frequency come before with lower frequency elements with same frequency come in the same order as they appear the values.

    

  

Consider the following I/O samples.

SAMPLE INPUT:      6

                                  2 2 4 9 9 9

SAMPLE OUTPUT:  9 9 9 2 2 4  

C PROGRAM:  

#include <stdio.h>
#include<limits.h>

#include<malloc.h>
int * frequencySortArray( int *arr,int size)
{
    int** occurence = NULL;
    int maxpos, count = 0, count_flag, o_row, index,max;
    int newindex = 0, num, ctr;
    occurence = (int**)calloc(1,sizeof(int*));
    occurence[0] = (int*)calloc(2,sizeof(int));
    occurence[0][0] = arr[0];
    occurence[0][1]++;
    count++;
    for(index = 1 ; index < size ; index++)
    {
            //search in occurence array
            for(o_row = 0, count_flag = 0 ; o_row < count ; o_row++)
            {
                    if(occurence[o_row][0] == arr[index])
                    {
                            occurence[o_row][1]++;
                            count_flag = 1;
                    }
            } //search completed
            if(count_flag == 0)
            {
                occurence = (int**)realloc(occurence,(count+1)*sizeof(int*));
                occurence[count] = (int*)calloc(2,sizeof(int));
                occurence[count][0] = arr[index];
                occurence[count][1]++;
                count++;
            }
    }
    for(index = 0 ; index < count ; index++)
    {
        //find maximum in occurence
        for(o_row = 0, max = INT_MIN ; o_row < count ; o_row++)
        {
            if(occurence[o_row][1] > max)
            {
                max = occurence[o_row][1];
                maxpos = o_row;
            }
        }
    num = occurence[maxpos][0];
    for(ctr = 1 ; ctr <= max ; ctr++)
        arr[newindex++] = num;
    occurence[maxpos][1] = -1;
    }
    // for(index=0 ; index < count ; index++)
    // free(occurence[index]);
    // free(occurence);
    return arr;

}

 

int main()
{
    int arr[1000];
    int size,index;
    scanf("%d",&size);
    for(index =0 ;index < size; index++)
            scanf("%d",&arr[index]);
    frequencySortArray(arr,size);
    for(index = 0 ; index < size ; index++)
            printf("%d ",arr[index]);
    return 0;
}

OUTPUT:

 

 

The given source code in C program is short and simple to understand. The source code is well tested in DEV-C++ and is completely error free. 

If you have any feedback about this article and want to improve this, please comment in the comment section.