Sorting an array of numbers by descending frequency

Question

Somebody asked me to create a code that orders unique numbers of an array according to their frequency, ie:

{1,3,3,4,4,4,4,4,2,2,5,5,5,5}

to

{4,5,3,2,1}

I'm a beginner and only started learning C last week so my code probably isn't optimal. I managed to get it in just over 100 lines without worrying too much about space. I haven't messed with memory allocation yet but I should start looking into it.

Any tips or feedback?

#include <stdio.h>
#include <string.h>


void CalculateFrequency(int numbers[], int frequency[]) //Populates an array with the frequency of numbers in another
{
    int hasSorted = 0;
    do
    {
        hasSorted = 0;
        for(int currentInt=0; currentInt<10; currentInt++)
        {
            for(int i=0; i<10; i++)
            {
                if(numbers[i] == currentInt)
                {
                    frequency[currentInt]++;
                    hasSorted = 1;
                }
            }
        }
        if(hasSorted == 0)
        {
            break;
        }
    }while(hasSorted == 0);
}
void SortByFrequency(int numbers[], int frequency[])    //Sorts an array according to the frequency of the numbers
{
    int hasSorted = 0;
    int temp = 0;
    do
    {
        hasSorted = 0;
        for(int i=0; i<10; i++)
        {
            for(int i=0; i<10; i++)
            {
                if(frequency[numbers[i]] < frequency[numbers[i+1]])
                {
                    temp = numbers[i+1];
                    numbers[i+1] = numbers[i];
                    numbers[i] = temp;
                    hasSorted = 1;
                }
            }
        }
        if(hasSorted == 0)
        {
            break;
        }
    }while(hasSorted == 0);
}
int CountUniqueNumbers(int array[], int arrayLength)    //Counts unique numbers in an array
{
    int count = 1; //At least 1 number
    for(int i=0; i<arrayLength-1; i++)
    {
        if(array[i] != array[i+1])
        {
            count++;
        }
    }
    return count;
}
int PopulateArrayByFrequencyAndReturnLength(int numbers[], int sortedByFrequency[])
{
    int k = 0;
    sortedByFrequency[0] = numbers[0];
    for(int i=0; i<10; i++)
    {
        if(numbers[i] != numbers[i+1])
        {
            sortedByFrequency[k] = numbers[i];
            k++;
        }
    }
    return k;
}
int counter;

int main(void)
{
    int numbers[10] = {1,2,2,2,5,7,8,8,8,8};
    int frequency[10] = {0,0,0,0,0,0,0,0,0,0};
    int sortedByFrequency[10] = {0,0,0,0,0,0,0,0,0,0};
    int sortedByFrequencyTrueLength = 0;
    int differentNumbers = 1;   /*The array must have at least 1 number*/
    int sizeofNumbersArray = 10;
    int uniqueNumbersInArray = 0;
    int i = 0;
    /*print the numbers*/
    printf("Numbers:\t");
    for(int i=0; i<10; i++)
    {
        printf("%d ", numbers[i]);
    }
    puts("");
    /*Perform functions*/
    CalculateFrequency(numbers, frequency);
    SortByFrequency(numbers, frequency);
    /*Get amount of unique numbers in the array*/
    uniqueNumbersInArray = CountUniqueNumbers(numbers, sizeofNumbersArray);
    /*Poupulate the unique number frequency array and get the true length*/
    sortedByFrequencyTrueLength = PopulateArrayByFrequencyAndReturnLength(numbers, sortedByFrequency);
    //Print unique number frequency array
    printf("Numbers sorted by frequency:\t");
    for(i=0; i<sortedByFrequencyTrueLength; i++)
    {
        printf("%d ", sortedByFrequency[i]);
    }
    puts("");

    return 0;
}

Answer 1

I see a couple occurrences of:

do
{
    hasSorted = 0;
    ...other things...
    if(hasSorted == 0)
    {
        break;
    }
}while(hasSorted == 0);

Did you mean if(hasSorted == 1) in those? If not, then you might want to just get rid of the whole if statement and replace the while condition with while(hasSorted != 0).

---

Also, comments that describe the whole function could look better on a separate line right before the function, so that the line doesn't get too long.

Answer 2

A few things I noticed:

Unused variables
The variables

• differentNumbers
• sizeofNumbersArray
• uniqueNumbersInArray

are never used. That is particularly interesting because uniqueNumbersInArray is the return value of the function CountUniqueNumbers. Which means, that function is called for naught. As a matter of fact, the function PopulateArrayByFrequencyAndReturnLength returns the very same value!

Exceeding array bounds
On several occasions you access the arrays beyond their limits. As a first example, the function PopulateArrayByFrequencyAndReturnLength.

for(int i = 0; i < 10; i++)
{
    if(numbers[i] != numbers[i+1])
    {
        sortedByFrequency[k] = numbers[i];
        k++;
    }
}

The index i runs all the way up to the last index, but the if accesses numbers[i+1], the element to the right. At the very last iteration you access numbers[10], the 11th element, but numbers is only 10 in length.

The same thing (for the same reasons) happens in SortByFrequency.

Logical errors
Running off the end of the array is the reason the function PopulateArrayByFrequencyAndReturnLength operates correctly. The counter k reacts to changes in the array. That means it wouldn't detect the last number in the array, since there is actually no change until the end. It does, however, detect a change, but accidentally because of the comparison with the element after the array.

You could account for the last number by manually incrementing k at the end. Or you can account manually for the first number in the array:

int PopulateArrayByFrequencyAndReturnLength(int numbers[], int sortedByFrequency[])
{
    int k = 1;
    sortedByFrequency[0] = numbers[0];
    for(int i = 1; i < 10; i++)
    {
        if(numbers[i-1] != numbers[i])
        {
            sortedByFrequency[k++] = numbers[i];
        }
    }
    return k;
}

Reducing Iterations

1. CalculateFrequency
The function CalculateFrequency runs in O(N^2) but can be done in linear time. If you notice, the number in the array is used as index into the frequency table - only in a complicated fashion. You can used those numbers directly and need to go through numbers only once:

void CalculateFrequency(int numbers[], int frequency[])
{
    for(int i = 0; i < 10; i++)
        frequency[numbers[i]]++;
}

2. SortByFrequency
That is a bubble sort algorithm. I noticed, that you use i for both the outer and the inner loop. The inner loop falls off the end of the array and in later iterations, the i numbers with lowest frequency are already sorted at the end. It is unnecessary to compare those again and again. That means, the inner loop can stop short by i:

void SortByFrequency(int numbers[], int frequency[])
{
    int hasSorted = 0;
    int temp = 0;
    do
    {
        hasSorted = 0;
        for(int i = 0; i < 9; i++)
        {
            for(int j = 0; j < 9-i; j++)
            {
                if(frequency[numbers[j]] < frequency[numbers[j+1]])
                {
                    temp = numbers[j+1];
                    numbers[j+1] = numbers[j];
                    numbers[j] = temp;
                    hasSorted = 1;
                }
            }
        }
    } while (hasSorted);
}

Miscellaneous

• As is, your algorithm doesn't scale well to large arrays with only few different numbers. And using the numbers as index into a frequency table will cause problems if the numbers themselves are very large. But optimisation here depends on the data that is to be expected.
• The length of the array, hard coded inside your functions, should really be an additional parameter.
• Array initialisation can be done shorter:

This sets all entries to zero:

int frequency[10] = {0};
int sortedByFrequency[10] = {0};

Or you could opt to use static arrays, they are initialised to zero:

static int frequency[10];
static int sortedByFrequency[10];