Menu
I'm searching for a fast stable radix sort implementation (with support of floats) which returns the indices of the sorted order instead of the sorted values.
Pierre Terdiman's version from his article "Radix Sort Revisited" does exactly what I want however it is more than 13 years old, and not suitable for modern pipelined CPUs.
Michael Herf's RadixSort11 from "Radix Tricks" is pretty fast, the only problem that it returns the sorted values instead of the indices, furthermore it corrupts the values of the input array.
Any help would be appreciated.
471
Radix sort can be extended to floats, pairs, tuples and std::array. So if your struct can provide for example a std::pair<bool, float> and use that as a sort key, you can sort it using radix sort.
If all your parameters are all integers and if you have over 1024 input parameters, then radix sort is always faster.
Radix sort can be applied to data that can be sorted lexicographically, such as words and integers. It is also used for stably sorting strings. It is a good option when the algorithm runs on parallel machines, making the sorting faster.
The merge sort is significantly, almost 6 times, faster than the Radix sort. I understand the time complexity of Radix sort also depends on the number of digits of the integers, but my merge implementation is beating my Radix implementation on all input sizes.
You can either
Expand each item to include its original index (this could be done during the first counting pass). Of course, the index digits are ignored for sorting purposes.
Store indices into buckets instead of values. Lookup the value each time the digits are required.
The first takes more space but has better locality of reference, the second saves space.
115
It is fairly straight forward to make any sort index based. Any sort is a series of comparisons and swaps, so do this.
// data to be sorted is in data[ 0 .. n ]
int index[ n + 1 ];
for( int i = 0; i <= n; i++ ) index[i] = i;
// To compare data, compare data[index[j]] < data[index[k]]
// To swap values, swap index[j] <=> index[k]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
