Redix sort issue

Question

I have a task of making radix sort without 2d array or list "from scratch".

This is my code that works fine... untill you introduce numbers with 4 mor more digits.

int* radix( int n, int* a, int k) {

int m=10,temp;
int count[10],dest[n],*b=a;

for(int i=0;i<k;i++){
    for(int j=0;j<m;j++)   {count[j]=0;}
    for(int j=0; j<n;j++) {count[((b[j]%((int)pow(10,i+1)))-(b[j]%((int)pow(10,i))))/(int)pow(10,i)]++;}
    for(int j=m-1;j>=0;j--) {
        temp=0;
        for(int l=0;l<j;l++)     {temp+=count[l];}
        count[j]=temp;
    }

    for(int j=0; j<n;j++){
        temp=((b[j]%((int)pow(10,i+1)))-(b[j]%((int)pow(10,i))))/(int)pow(10,i);
        dest[count[temp]]=b[j];
        count[temp]++;
    }

    for(int j=0;j<n;j++){ b[j]=dest[j];}
    for(int j=0;j<n;j++){ cout<<b[j]<<' ';}
    cout<<endl<<endl;
}



return b;

}

error occurs at dest[count[temp]]=b[j]; near the end. I suspect that problems arise becose of relativly complex radix isolation.

I am too stuck in my head and dont see a possible solution.Plese help!

Your formatting is making it very hard on yourself, and on others, to read your code. Why are you cramming multiple things onto one line, and using completely inconsistent whitespace? — user229044, Sep 15 '22 at 17:14
Your code is [*not* valid C++ code](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). It's also rather horrible and close to unreadable. Please don't learn programming or *any* kind from so-called "competition" or "judge" sites. Such sites are not learning or teaching resources. — Some programmer dude, Sep 15 '22 at 17:15
`int *b=a;` I'm not sure what do you expect this to be doing, given the following loop `for(int j=0;j<10;j++){ a[j]=b[j]; }`. Could you please remove all the timing and counting stuff to produce a [mre], stating what the parameters stand for? — Bob__, Sep 15 '22 at 18:18
Consider avoid floating-point calculations, which may introduce rounding errors: `for(int i=0;i `for(int i=0, pow_i = 1, pow_next = 10; i — Bob__, Sep 15 '22 at 18:31
`n` seems to be the number of array elements, but what's `k`? — John Bollinger, Sep 15 '22 at 19:03
And what is the point of `b`? You initialize it as a copy of (pointer) `a`, and never afterward modify either `b` or `a`, so why not just use `a` throughout and omit `b`?. — John Bollinger, Sep 15 '22 at 19:07
At the end of your main loop you copy exactly 10 elements of `dest` back to `a`. That's definitely wrong if `a` has fewer than 10 elements, and it appears to be wrong if `a` (and `dest`) have more than 10 elements, too. — John Bollinger, Sep 15 '22 at 19:11
k is a max number of digits in any given element of array, so if k is 3 that means that array can contain numbers from 0 to 999. thank you Jhon Bollinger using 10 instead of n is a mistake. thou it still does not function with k>3. — Piece - kun, Sep 15 '22 at 19:30
Perhaps the problem revolves around your use of `pow()`. Floating-point math is inexact. If one of your `pow(10, x)` calls produces a value even 1 ulp less than the expect integer power of 10 then you are hosed: truncating that to an `int` will produce a result different from the expected power of 10. You don't need `pow()` or FP math for this anyway. — John Bollinger, Sep 15 '22 at 20:33
... and that would explain why the misbehavior doesn't happen until you reach a certain number of digits. — John Bollinger, Sep 15 '22 at 20:41

rcgldr · Accepted Answer · 2022-09-16T09:31:16.213

I changed the code to allocate dest[], but otherwise it seems to be working as is, with Visual Studio. Note that the code would require modification to work with negative elements. For example, if range is -9999 to +9999, then add 9999 to all elements, treat the elements as unsigned integers, and do one more radix sort pass for the most significant digit (0 or 1). Subtract 9999 from all elements after radix sort is done.

void radix( int n, int* a, int k)
{
int m=10,temp;
int count[10], *b=a;
int *dest = new int[n];

  for (int i = 0; i < k; i++) {
    for (int j = 0; j < m; j++) { count[j] = 0; }
    for (int j = 0; j < n; j++) { count[((b[j] % ((int)pow(10, i + 1))) - (b[j] % ((int)pow(10, i)))) / (int)pow(10, i)]++; }
    for (int j = m - 1; j >= 0; j--) {
        temp = 0;
        for (int l = 0; l < j; l++) { temp += count[l]; }
        count[j] = temp;
    }

    for (int j = 0; j < n; j++) {
        temp = ((b[j] % ((int)pow(10, i + 1))) - (b[j] % ((int)pow(10, i)))) / (int)pow(10, i);
        dest[count[temp]] = b[j];
        count[temp]++;
    }

    for (int j = 0; j < n; j++) { b[j] = dest[j]; }
  }
  delete[] dest;
}

Classic implementation:

void radix(int n, int* a, int k)
{
    int cnt[11];                        // size is +1
    int i,j;
    int p=1;                            // powers of 10
    unsigned *src = (unsigned *)a;      // source = a
    unsigned *dst = new unsigned[n];    // allocate dest array
    for(i=0; i<k; i++){
        for(j=0; j<11; j++)             // clear cnt[]
            cnt[j]=0;
        for(j=0; j<n; j++)              // set counts
            cnt[1+(src[j]/p)%10]++;     //  at (1+digit)
        for(j=2; j<10; j++)             // convert counts to indexes
            cnt[j] += cnt[j-1];
        for(j=0; j<n; j++)              // radix sort pass
            dst[cnt[(src[j]/p)%10]++] = src[j];
        p *= 10;                        // setup for next digit
        std::swap(src, dst);            // swap src, dst
    }
    if(k&1){                            // if odd number of passes
        for(j=0; j<n; j++)              //  copy src to dst
            dst[j] = src[j];
        std::swap(src, dst);            //  swap src, dst
    }
    delete [] dst;
}

Redix sort issue

1 Answers1