5
\$\begingroup\$

I've tried to implement the counting sort algorithm in C.

What efficiencies can you spot? I squint at the end when running through the original array again to assign it the sorted array. Maybe there is a better way?

/**
* Sorts array of n values.
* Using counting sort O(n)
*/
void sort(int values[], int n)
{
  //set our known max length, initialize our placer array and then our sorted array
  int maxLength = 65536;
  int placer[maxLength];
  int sorted[n];

  //so we can know which indexes in our placer array are in values array
  for ( int i = 0; i < n; i++ ) {
    placer[ values[i] ] += 1;
  }

  //store the sum of previous elements in each element at each index because this will give us the sorted position
  for (int i = 0; i < maxLength; i++ ) {
    placer[ i + 1 ] += placer[i];
  }

  //fill the sorted array with the values elements using the corresponding placer index
  for ( int i = 0; i < n; i++ ) {
    sorted[ placer[ values[i] ] - 1 ] = values[i];
    placer [ values[i] ] -= 1;

  }

  //set the unsorted values array to the sorted array
  for (int i = 0; i < n; i++) {
    values[i] = sorted[i];
  }
}
\$\endgroup\$
2
\$\begingroup\$

Off by one error

This loop goes over by 1 and writes past the last array element:

  for (int i = 0; i < maxLength; i++ ) {
    placer[ i + 1 ] += placer[i];
  }

You could either stop the loop at maxLength - 1, or rewrite the loop to start at 1 like this:

  for (int i = 1; i < maxLength; i++ ) {
    placer[i] += placer[i-1];
  }

Uninitialized variable causes crash

When I ran your program, it crashed due to an uninitialized variable, here:

int placer[maxLength];

Later on, you do placer[values[i]] += 1 without ever having cleared the placer array to zeros, so you can get garbage values in the array. You can fix this by clearing the array like this:

memset(placer, 0, sizeof(placer));

However, I recommend not using variable length arrays. One reason is that they are only optionally supported in the latest C standard. The other reason is that sometimes you can overflow your stack if you allocate a large variable length array. I would use calloc() here to allocate the counting array.

Simplify the function

It looks like you are using a version of counting sort that is used for radix sort, which needs to move elements around in the array. For a simple counting sort, you don't need to do that. After the counting pass, you can just fill in the original array with values from the counts, like this:

// Uses counting sort to sort an array which contains values in the
// range [0..65535].  The counting array is allocated using calloc() in
// order to avoid putting a large array on the stack.
void sort(int values[], int n)
{
    const int maxLength = 65536;
    int      *counts    = calloc(maxLength, sizeof(*counts));

    if (counts == NULL) {
        return;
    }

    for (int i = 0; i < n; i++) {
        counts[values[i]]++;
    }

    int outIndex = 0;
    for (int i = 0; i < maxLength; i++) {
        for (int j = 0; j < counts[i]; j++) {
            values[outIndex++] = i;
        }
    }

    free(counts);
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Could you explain the last part of the simplified function to me? \$\endgroup\$ – Joseph Palomino Mar 1 '17 at 18:00
  • \$\begingroup\$ @JosephPalomino You loop through each number 0, 1, 2, .., 65535. For each number, you write k of that number into the output array, where k is the number of times you counted it in the input array, i.e. counts[i]. (The input array and output array are the same array but I'm just clarifying what is happening). The variable outIndex holds the place of where to write the next number in the output array. If you counted all the numbers correctly, you will end up writing exactly n numbers to the output array. \$\endgroup\$ – JS1 Mar 1 '17 at 18:34
  • \$\begingroup\$ Awesome, I understand it now. However, wont values[0] index never get written to? \$\endgroup\$ – Joseph Palomino Mar 1 '17 at 23:24
  • \$\begingroup\$ @JosephPalomino values[0] is written the very first time because outIndex starts as 0. The notation outIndex++ is a postIncrement, so the first time, it will write to values[0] and then increment outIndex to 1. \$\endgroup\$ – JS1 Mar 2 '17 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.