ProAlgos/ProAlgos-Cpp

Fix radix sort

faheel opened this issue · 2 comments

faheel commented

Radix sort seems to be broken as pointed out in #430

pm100 commented

there are two issues here.

  • there is a trivial bug to do with passing arguments in the wrong order. I can post a fix for that. Its a bug in the sort not in the test harness
  • radix sort cannot work with negative values as currently coded. This causes the test harness to fail even with the first thing fixed.

I can post the fix to the first one, this makes code like this work

vector<int> arr{ 1, 8, 5, 12, 3 };
radix_sort(arr, 1, true);
return 0;

but crashes with (negative array indexes get generated by get_digit)

vector<int> arr{ 1, 8, -5, 12, 3 };
radix_sort(arr, 1, true);
return 0;

the second one is tougher. Two choices

  • fix it so that it can support negative values. Not sure if radix sort can be made to do that
  • doc it as an algorithm that only supports >=0 values and enforce that. Test harness would need to be changed too

I have verified that if I change the test harness to only generate >=0 values it works fine

pm100 commented

one way to fix would be

  • partition into neg and pos sub vectors
  • change signs of neg part
  • sort pos one way, neg the other way
  • merge

I have coded this up, works fine