Count number of occurrences of each unique number: algorithm almost works

Question

I am trying to work my way up from the beginning in C and making sure I understand every little thing before moving on. Today, my goal was to write a program that would take in a list of integers (assume less than 50 integers) and would print a table with the list of unique integers in one side and the number of times it appeared in the other. I have a copy of my function which takes care of counting the number of times it appears.

Quick summary of my function: takes in 2 pointers to arrays, and one integer of how many integers to iterate over. Assumption: we are checking for repeats of some number x. Somewhere in the array, we hit another x. It increments the count for x and turns x into 0 for later purposes.

Sample trials input: 1 2 1 2 2 1 2 output: 1 appears 3 times. 2 appears 4 times.

input: 1 2 3 1 2 3 1 2 3 output: 1 appears 3 times. 2 appears 3 times. 3 appears 3 times.

input: 1 2 1 3 1 2 3 output: 1 appears 3 times. 2 appears 2 times. 3 appears 1 times.

Although the program is working for the most part, I want to make sure it works completely. Thus, my issue is that last trial. Why is 3 being read only once when it works for other 2 input sets?

    void countOccurrences(int *list, int size, int *uniques){
for (int i = 0, t = 0; i < size; i++){
    int temp = list[i];
    if (temp == 0){                     //If the number was a repeat of another previous number
        continue;                       //skip over it and go to the next element in list
    }
    uniques[t] = 1;

    for (int j = i+1; j <= size; j++){      //this iterates through list for any repeats of temp
        if (temp == list[j]){           //All repeats of temp turn to 0
            uniques[i]++;
            list[j] = 0;
        }
    }
    t++;
}

}

Answer 1

There are several problems with this code that we can illustrate with some more complete testing. Here's a short, self-contained, compilable (in C99) example (see SSCCE) with some tests and some additional diagnostic results:

#include <stdio.h>

void printArray(char *name, int *list, int size) {
    printf ("%s = {",name);
    for (int i = 0; i < size; i++) {
        printf ("%d ",list[i]);
    }
    printf ("}\n");
}

void countOccurrences(int *list, int size, int *uniques, int *values) {
    for (int i = 0, t = 0; i < size; i++) {
        int temp = list[i];
        if (temp == 0) {                     
            //If the number was a repeat of another previous number
            continue;                       
            //skip over it and go to the next element in list
        }
        uniques[t] = 1;
        values[t] = temp;

        for (int j = i+1; j <= size; j++) {      
            //this iterates through list for any repeats of temp
            if (temp == list[j]) {           
                //All repeats of temp turn to 0
                uniques[i]++;
                list[j] = 0;
            }
        }
    t++;
    }
}

void test(int *x, int size) {
    const int n = 10;
    int uniques[n],values[n];
    for (int i = 0; i < n; i++) {uniques[i] = 0; values[i] = -1; }
    countOccurrences (x,size,uniques,values);
    printArray ("uniques",uniques,sizeof(uniques)/sizeof(*uniques));
    printArray ("values ",values,sizeof(values)/sizeof(*uniques));
}

int main (int argc, char* argv[]) {
    int x1[] = {1, 2, 1, 2, 2, 1, 2};
    int x2[] = {1, 2, 3, 1, 2, 3, 1, 2, 3};
    int x3[] = {1, 2, 1, 3, 1, 2, 3};
    int x4[] = {3, 2, 1, 3, 1, 2, 3};

    test(x1,sizeof(x1)/sizeof(*x1));
    test(x2,sizeof(x2)/sizeof(*x2));
    test(x3,sizeof(x3)/sizeof(*x3));
    test(x4,sizeof(x4)/sizeof(*x4));
    return 0;
}

(EDITED thanks to @Matt McNabb's advice, by refactoring common code into the test() function)

... for which the output is:

uniques = {3 4 0 0 0 0 0 0 0 0 }
values  = {1 2 -1 -1 -1 -1 -1 -1 -1 -1 }
uniques = {4 3 3 0 0 0 0 0 0 0 }
values  = {1 2 3 -1 -1 -1 -1 -1 -1 -1 }
uniques = {4 2 1 1 0 0 0 0 0 0 }
values  = {1 2 3 -1 -1 -1 -1 -1 -1 -1 }
uniques = {3 2 3 0 0 0 0 0 0 0 }
values  = {3 2 1 -1 -1 -1 -1 -1 -1 -1 }

The first test gives you the expected output. The second test shows that there is an extra count for the first item in the list. This can be fixed by changing:

for (int j = i+1; j <= size; j++){

to

for (int j = i+1; j < size; j++){

... because the code is counting one space beyond the end of the data. The output with this bug fixed is:

uniques = {3 4 0 0 0 0 0 0 0 0 }
values  = {1 2 -1 -1 -1 -1 -1 -1 -1 -1 }
uniques = {3 3 3 0 0 0 0 0 0 0 }
values  = {1 2 3 -1 -1 -1 -1 -1 -1 -1 }
uniques = {3 2 1 1 0 0 0 0 0 0 }
values  = {1 2 3 -1 -1 -1 -1 -1 -1 -1 }
uniques = {3 2 2 0 0 0 0 0 0 0 }
values  = {3 2 1 -1 -1 -1 -1 -1 -1 -1 }

The third and fourth test results are harder to interpret because it isn't so obvious what the intended output should be. The counting function appears to be intended to report counts of unique numbers in the order in which it finds those numbers in list. With the third test, however, the first appearance of "3" is at the fourth item in the list. Changing:

uniques[i]++;

to

uniques[t]++;

... means that the count is output as the tth item in the count list, giving the output:

uniques = {3 4 0 0 0 0 0 0 0 0 }
values  = {1 2 -1 -1 -1 -1 -1 -1 -1 -1 }
uniques = {3 3 3 0 0 0 0 0 0 0 }
values  = {1 2 3 -1 -1 -1 -1 -1 -1 -1 }
uniques = {3 2 2 0 0 0 0 0 0 0 }
values  = {1 2 3 -1 -1 -1 -1 -1 -1 -1 }
uniques = {3 2 2 0 0 0 0 0 0 0 }
values  = {3 2 1 -1 -1 -1 -1 -1 -1 -1 }

This output is correct now, but it is difficult to interpret the counts found in uniques without the values array that I've added to the code. See that, in the last test case, the first count is the number of 3s in list, not the number of 1s, for instance.

Finally, it is generally poor practice to modify a parameter to a function at all. It is necessary to do so in C because you can't return an array from a function but modifying the arrays pointed to by uniques and values is generally tolerable because they are explicitly available to return results outwards from the function. Modifying a parameter used to supply input data to a function, though, as countOccurrences() does with list is generally unwise because that means the code that uses countOccurrences() has to make a copy of list before passing the pointer to that list to countOccurrences(), if it wants to use the original content of list for some other purpose as well.

If we know that the integers to be counted are all less than or equal to than the size of the uniques array, the function suggested by @Saravana Kumar is both quicker to run and easier to make correct:

// Requirements: 
// uniques initially contains all zeros
// no integer in list is less than zero or greater than sizeof(uniques)/sizeof(int)-1
//
void countOccurrences2 (int *list, int size; int *uniques) {
    for (int i = 0; i < size; i++) {      
        uniques[list[i]]++;
    }
}

Answer 2

It is because, 3 comes as last number and you reset the count of occurrence to 1

uniques[t] = 1;

and for loop doesn't run at all since thats the last number, you are not looking back in the array.

I would simply write this program as below.Given list has values >=0

for (int i = 0; i < size; i++){      //this iterates through list for any repeats of temp
            uniques[list[i]]++;
 }

For a list with any values, use a hash table data structure

Answer 3

I wouldn't go stomping over the original data.

High level view:

for each element
   if it apeared before
      increment it's count
   else
      record it's first occurence

Say you need to count the contents of an N element array, it can't contain more than N different elements. One simple way of representing the counts is to have an array of values and counts, and a number of used entries (different values seen). This would be along the lines:

#define N ...

struct {
         int value, cnt;
       } count[N];
int entries = 0;

Your check to see if the value v is already there is:

for(k = 0; k < entries && count[k].value != v; k++)
    ;
if(k == entries) {
    /* Not found */
    count[k].value = v;
    count[k].cnt   = 1;
    entries++;
}
else {
    /* Found it */
    count[k].value++;
}

Just need to wrap this up with the code to comb your data array...

(Yes, this is quite inefficient; for serious use a smarter/faster structure to keep the values would be needed).