c++ counting sort

Question

I tried to write a countingsort, but there's some problem with it.

here's the code:

int *countSort(int* start, int* end, int maxvalue)
{
    int *B = new int[(int)(end-start)];
    int *C = new int[maxvalue];

    for (int i = 0; i < maxvalue; i++) 
    { 
        *(C+i) = 0; 
    }
    for (int *i = start; i < end; i++) 
    { 
        *(C+*i) += 1; 
    }
    for (int i = 1; i < maxvalue-1 ; i++) 
    { 
        *(C+i) += *(C+i-1); 
    } 
    for (int *i = end-1; i > start-1; i--) 
    { 
        *(B+*(C+(*i))) = *i; 
        *(C+(*i)) -= 1; 
    }
    return B;   
}

In the last loop it throws an exception "Acces violation writing at location: -some ram address-"

Where did I go wrong?

Answer 1

In my opinion, using simple pointer arithmetic is what is lacking. Here is my code and it works (I tested with sample code).

int* sort1(int *start, int *end, int max) {

int min = INT_MAX;
int n = abs(end - start) + 1;

int* arr = new int[n];
for(int i = 0; i < n; ++i) {
  arr[i] = *(start + i);
  //cout << arr[i] << endl;
}

for(int i =0 ; i < n; ++i) {
  min = ((arr[i] < min)? arr[i] : min);
}

int r = abs(max - min);
int t[r + 1] = {0};

for(int i = 0; i < n; ++i) {
  t[arr[i] - min]++;
}

for(int i =0, j =0; i < (r+1); ++i) {
  if(t[i] > 0) {
    arr[j] = i + min;
    ++j;
  }
}

return arr;

}

int main()
{

  int arr1[] = {3,1,5,9};

  int arr2[] = {6,4,100,0,-1,50,-11,-101};

  int n1 = (sizeof(arr1)/sizeof(arr1[0]));
  int n2 = (sizeof(arr2)/sizeof(arr2[0]));

  int n3 = (n1 + n2);
  int arr3[n3];

  for(int i = 0; i < n1; ++i) {
    arr3[i] = arr1[i];
  }
  for(int i = 0; i < n2; ++i) {
    arr3[n1 + i] = arr2[i];
  }

  int *arr5 = sort1(&arr3[0], &arr3[n3 - 1], 100);
  for(int i = 0; i < (n1 + n2); ++i) {
    cout << *(arr5 + i) << endl;
  }

  return 0;
}

The output:
-101
-11
-1
0
1
3
4
5
6
9
50
100

Answer 2

for (int i = 1; i < maxvalue-1 ; i++) 

That's the incorrect upper bound. You want to go from 1 to maxvalue.

for (int *i = end-1; i > start-1; i--) 
{ 
    *(B+*(C+(*i))) = *i; 
    *(C+(*i)) -= 1; 
}

This loop is also completely incorrect. I don't know what it does, but a brief mental test shows that the first iteration sets the element of B at the index of the value of the last element in the array to the number of times it shows. I guarantee that that is not correct. The last loop should be something like:

int* out = B;
int j=0; 
for (int i = 0; i < maxvalue; i++) {  //for each value
    for(j<C[i]; j++) {                //for the number of times its in the source
        *out = i;                     //add it to the output
        ++out;                        //in the next open slot
    }
}

As a final note, why are you playing with pointers like that?

*(B + i)  //is the same as
B[i]      //and people will hate you less

*(B+*(C+(*i))) //is the same as
B[C[*i]]  

Answer 3

Since you're using C++ anyway, why not simplify the code (dramatically) by using std::vector instead of dynamically allocated arrays (and leaking one in the process)?

std::vector<int>countSort(int* start, int* end, int maxvalue)
{
    std::vector<int> B(end-start);
    std::vector<int> C(maxvalue);

    for (int *i = start; i < end; i++) 
        ++C[*i];

// etc.

Other than that, the logic you're using doesn't make sense to me. I think to get a working result, you're probably best off sitting down with a sheet of paper and working out the steps you need to use. I've left the counting part in place above, because I believe that much is correct. I don't think the rest really is. I'll even give a rather simple hint: once you've done the counting, you can generate B (your result) based only on what you have in C -- you do not need to refer back to the original array at all. The easiest way to do it will normally use a nested loop. Also note that it's probably easier to reserve the space in B and use push_back to put the data in it, rather than setting its initial size.