Error in Sorting Algorithm in C (variation of Radix Sort)

Question

I'm learning C and I read some sorting algorithms on internet. I tried to make my own sorting algorithme, and it looks a bit like the radix sort. Radix sort on Wikipedia. Below is a program with my sort algorithm.

#include <stdio.h>
#include <stdlib.h>

/* prints all elements of an array of n length */
void printArray(int *arr, int n){
  if (n < 0){
    return;
  } else if (n == 0){
    printf("()\n");
  } else {
    int i;
    printf("(%d", arr[0]);
    for(i=1; i<n; i++){
      printf(", %d", arr[i]);
    }
    printf(")\n");
  }
}

/* safe replacement for malloc. */
void *safeMalloc(int size) {
  void *ptr = malloc(size);
  if (ptr == NULL) {
    printf("\nError: memory allocation failed....abort\n");
    printf("\nNot enough space for %d int numbers\n", size);
    exit(-1);
  }
  return ptr;
}

/* safe replacement for realloc. */
int *resizeArray(int *arr, int newSize){
  int *ptr = realloc(arr, newSize*sizeof(int));
  if (ptr == NULL) {
    printf("\nError: memory allocation failed....abort\n");
    exit(-1);
  }
  return ptr;
}

/* check if array is sorted */
void checkArray(int length, int *a){
  int i;
  for(i=0; i<length-i; i++){
    if (a[i] > a[i+1]){
      printArray(a, length);
      printf("Error in: %d\n", i);
      return;
    }
  }
}

/*///////////////////////////////////////////////////
 * /////////////// SORTING ALGORITHM ////////////////
 * ////////////////////////////////////////////////*/
void sort(int length, int a[], int digits){
  /* base case */
  if ((length <= 1) || (digits == 0)){
    return;
  }
  /* recursive case */
  /* declare variables */
  int i, j, digit, idx = 0, sum = 0;
  int *copy[10], lengthCopy[10];
  for(i=0; i<10; i++){
    lengthCopy[i] = 0;
    copy[i] = safeMalloc(sizeof(int));
  }
  for(i=0; i<length; i++){
    /* get the n'th digit. Example: a[i]=12345 and digits=100 --> digit=3 */  
    digit = (a[i]/digits)%10;

    lengthCopy[digit]++;
    if (lengthCopy[digit] > 1){
      resizeArray(copy[digit], lengthCopy[digit]);
    }
    copy[digit][lengthCopy[digit]-1] = i;
  }
  /* Get the values */
  for(i=0; i<10; i++){
    for(j=0; j<lengthCopy[i]; j++){
      copy[i][j] = a[copy[i][j]];
    }
  }
  /* fill in the elements of copy in the original array */
  for(i=0; i<10; i++){
    for(j=0; j<lengthCopy[i]; j++){
      a[idx] = copy[i][j];
      idx++;
    }
    /* copy[i] is no longer necessary, so free it */
    free(copy[i]);
  }

  for(i=0; i<10; i++){
    /* call recursive function */
    sort(lengthCopy[i], &a[sum], digits/10);
    sum += lengthCopy[i];
  }
}

int getMax(int length, int a[]){
  int i, max = 1;
  for(i=0; i<length; i++){
    while(a[i] > max*10){
      max *= 10;
    }
  }
  return max;
}

int main(int argc, char *argv[]){
  int i, *a, length=20;
  a = safeMalloc(length*sizeof(int));
  for(i=0; i<length; i++){
    a[i] = rand()%100;
  }
  sort(length, a, getMax(length, a));
  checkArray(length, a);
  printArray(a, length);
  free(a);
  return 0;
}

Now, the extremely strange thing when i tried out my program, is that a segmentation fault occurs when i had in the main function: int length = 1000, but not if i had typed: int length = 20;

I don't know where this error coms from. Can someone help me?

Thanks in advance,

Patrick

p.s. Sorry for my English, it's not my first languague ;)

Answer 1

As Rubens suggested, using Valgrind leads you straight to the bug:

==7369== Invalid write of size 4
==7369==    at 0x400991: sort (/tmp/t.c:77)
==7369==    by 0x400BF2: main (/tmp/t.c:118)
==7369==  Address 0x4de46e4 is 0 bytes after a block of size 4 free'd
==7369==    at 0x402FD9E: realloc (valgrind/coregrind/m_replacemalloc/vg_replace_malloc.c:661)
==7369==    by 0x4007AA: resizeArray (/tmp/t.c:33)
==7369==    by 0x40096A: sort (/tmp/t.c:75)
==7369==    by 0x400BF2: main (/tmp/t.c:118)

After you realloc, you can not access the old array, you must use the new array. Your resizeArray function returns new array for a reason; it's a bug to ignore that return value.

Now, your program still "works" despite that bug, but only by accident. Heap corruption bugs are nasty like that.