Strange output from Counting Sort in C

Question

I have the following Counting Sort function

/*
 *File: countingSort.c
 *Description: A counting sort subroutine. Takes as input an array of integers.
 *             an array length and a range. All values in the input array must fall within                  [0, range].
 *            Takes O(range + arrayLen) time and O(range + arrayLen) extra space
 *
*/

#include "countingSort.h"

int* countingSort(int unsorted[], int arrayLen, int range) {
  int store[range + 1];
  int sorted[arrayLen];

  for ( int i = 0; i <= range; i++ ) {
    store[i] = 0;
  }

  for ( int i = 0; i < arrayLen; i++ ) {
    sorted[i] = 0;
  }

  for ( int j = 0; j < arrayLen; j++ ) {
    store[unsorted[j]] ++;
  }

  for ( int i = 1; i <= range; i++ ) {
    store[i] += store[i-1];
  }

  for( int j = arrayLen - 1; j >= 0; j-- ) {
    sorted[store[unsorted[j]]] = unsorted[j];
    store[unsorted[j]] --;
  }

  return sorted;
}

The function is giving me really strange output. The output is nothing like the input most of the times but sometimes it just works. Why is this happening?

I am calling it from another file called cSortTest.c. That file looks like this

/*
 *File: cSortTest.c
 *Description: Tests countingSort.c
 *
*/

#include <stdio.h>
#include "countingSort.h"

int main() {
  int data[8] = { 2, 1, 9, 4, 4, 56, 90, 3 };
  int* p;

  p = countingSort(data, 8, 90);
  for ( int i = 0; i < 8; i++ ) {
    printf("%d Element: %d\n", i, *(p+i) );
  }
}

unwind · Accepted Answer · 2014-04-04 07:18:18Z

3

You are returning a local array variable. This variable is destroyed when the function exits, making the address to it no longer safe or valid to access. In fact accessing it will give you what is called undefined behavior, which explains why it sometimes appears to "work".

This is a classic beginner's mistake in C. You must either have the caller pass in the desired destination array, or use malloc() to allocate "persistent" heap memory and return that:

int* countingSort(int unsorted[], int arrayLen, int range) {
  int *sorted = malloc(arrayLen * sizeof *sorted );
  if (sorted== NULL)
    return NULL;
  /* rest of sorting */
  return sorted;
}

The arrayLen * sizeof *sorted expression computes the number of bytes required for the allocation. There's no need to use calloc() which clears the memory; you're going to overwrite each element so clearing it is just wasted effort.

edited Apr 4, 2014 at 7:18

answered Apr 4, 2014 at 7:00

unwind

402k64 gold badges492 silver badges620 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Yudhishthir Singh Over a year ago

Should I use alloc()/calloc() for arrays as this page seems to suggest

Collectives™ on Stack Overflow

Strange output from Counting Sort in C

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related