Counting sort with negative integers?

Question

I wanna modify my counting sort algorithym to work with negative integers.

here is what i have so far(segmentation fault):

void counting_sort(int *vet, int max, int min, int n){

  int i, j, C[(max-min)+1], B[n];

  for (i=0;i<=max;i++){
    C[i]=0;
  }

  for (i=0;i<n;i++){
    C[vet[i]-min]++;
  }

  for (i=1;i<=(max-min);i++){
    C[i]=C[i]+C[i-1];
  }

  for (i=n-1;i>=0;i--){
    B[C[(vet[i])-min]-1]=vet[i];
    C[vet[i]-min]--;
  }

  for (i=0;i<n;i++){
    printf("%d ",B[i]);
  } 
}

Answer 1

I do not know what's causing the segmentation fault but if you want to sort negative numbers using counting sort, you just need to find the lowest negative number in the array and add the absolute value to all values of array temporary. After this, use the normal counting sort algo to sort the array then substract the lowest minimum value from every number in the array obtained.

---

Adding/Subtracting a number from all elements of the array do not affect the result of sorting.

Answer 2

This loop looks like it has an off-by-one error in it:

for (i=1;i<=(max-min+1);i++){
    C[i]=C[i]+C[i-1];
}

Note that the array C has max - min + 1 elements in it, so if you iterate up to and including index max - min + 1, you’re writing off the end of the array.

There may be other issues here as well, but I’d start by looking into that.

Answer 3

You can change this to sort in forward order:

    int i, j, C[(max-min)+2], B[n];   // ...+2...
    for (i=0;i<=(max-min)+1;i++){     // ...+1...
        C[i]=0;
    }
    for (i=0;i<n;i++){
        C[vet[i]+1-min]++;            // ...+1...
    }
    for (i=2;i<=(max-min);i++){       // i = 2
        C[i]+=C[i-1];
    }
    for (i=0;i<n;i++){                // 0 to n-1 sort
        B[C[vet[i]-min]++]=vet[i];
    }