Why this radixSort doesn't work

Question

It look's like it's OK. But result is telling something different. Really, I don't know whats wrong with it. Maybe it's because I wrote it at 2 o'clock at night ...

EDIT:

template <class T>
void radixSort(T & arr, msize numberBase)
{
    long maxValue = findMax(arr);
    dynarray<long> tarr(arr,arr.size());
    dynarray<long> presenceTable(numberBase+1);
    for (register long i=0, max=presenceTable.size(); i<max; ++i)
    {
        presenceTable[i] = 0;
    }
    for (register long exp=1; maxValue/exp>0; exp*=numberBase)
    {
        for (register long i=0, max=tarr.size(); i<max; ++i)
        {
             ++(presenceTable[(tarr[i]/exp)%numberBase]);
        }
        for (register long i=1, max=presenceTable.size(); i<max; ++i)
        {
            presenceTable[i] += presenceTable[i-1];
        }
        for (register long i=0, max=tarr.size(); i<max; ++i)
        {
            arr[  (--(presenceTable[(tarr[i]/exp)%numberBase]))  ] = tarr[i];
        }
        tarr = arr;
        for (register long i=0, max=presenceTable.size(); i<max; ++i)
        {
        presenceTable[i] = 0;
        }
    }
}

Without going into details, are you sure the integer division in loop termination works as intended? 1/2 would return 0 here — fkl, Apr 13 '14 at 00:15
No, I'm not sure. But, is there any other way to slice number to digits? — dev1223, Apr 13 '14 at 08:28
There are several ways including using a double at first and converting it to integer latter or even general rounding off techniques for integers. — fkl, Apr 13 '14 at 19:28

score -1 · Answer 1 · answered Aug 04 '22 at 14:45

Try algorithm from this code:

#include<bits/stdc++.h>
using namespace std;
 
// Function to get maximum value in array a[].
int getmax(int a[], int n)
{
  int max = a[0];
  for (int x=1; x<n; x++)
    if (a[x] > max)
      max = a[x];
  return max;
}
 
// Function to do counting sort according to significant digits repesented by
// exp (where exp is 10^i).
void CountSort(int a[], int n, int exp)
{  
  int result[n], i, count[10] = {0};
 
  // Counting occurence of digits
  for (i =0; i <n; i++)
    count[(a[i] / exp) % 10]++;
 
  // Changing the position of count so that it appears at actual position in result.
  for (i =1; i<10; i++)
    count[i] += count[i-1];
 
  // Resultant output array
  for (i =n-1; i>= 0; i--)
  {
    result[count[(a[i] / exp) % 10] - 1] = a[i];
    count[(a[i] / exp) % 10]--;
  }
  for (i =0; i <n; i++)
    a[i] = result[i];
}
 
// Radix Sort to sort a[] of given size.
void radixsort(int a[], int n)
{
  int exp, i;
  i = getmax(a, n);
  for (exp = 1; i/exp > 0; exp *= 10)
    CountSort(a, n, exp);
}
// Driver Program
int main()
{
  int n;
  cout<<" Enter the number of elements to be sorted: ";
  cin>>n;
    int a[n];
  
  cout<<"\n Enter the elements: ";
  for(int i =0; i <n; i++)
  {
    cin>>a[i];
  }
    radixsort(a, n);
 
  // Printing the sorted list.
  cout<<"\nSorted List: ";
  for (int i = 0; i < n; i++)
    cout<<a[i]<<", ";
  return 0;
}

I changed it a bit and it worked for me

`count[(a[i] / exp) % 10]++` **exp is an extremely bad name for a variable**, especially when combining with `#include` and `using namespace std;` because there's already `std::exp` which is introduced into the current scope by `using namespace std;`. Same to `max` which is the same as `std::max` and you can find lots of issues related to `max` on SO — phuclv, Aug 04 '22 at 15:16
see also [Why should I not #include ?](https://stackoverflow.com/q/31816095/995714), [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/q/1452721/995714) — phuclv, Aug 04 '22 at 15:17

Why this radixSort doesn't work

1 Answers1