CODEWITHSUNDEEP
csortingcounting-sort
Compacted
Compacted

Reputation: 1

Counting sort with negative integers?

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]);
  } 
}

Upvotes: 0

Views: 859

Answers (3)

rcgldr
rcgldr

Reputation: 28826

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];
    }

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 372872

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.

Upvotes: 1

Archaic
Archaic

Reputation: 57

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.

Upvotes: 0

Related Questions