Быстрая, ранговая сортировка Radix для поплавков?
Я ищу быструю стабильную реализацию сортировки по основанию (с поддержкой чисел с плавающей запятой), которая возвращает индексы отсортированного порядка вместо отсортированных значений.
Пьера Тердимана версия из его статьи «Radix Sort Revisited» делает именно то, что я хочу, но ему больше 13 лет, и он не подходит для современных конвейерных процессоров.
Майкл Херф RadixSort11 от «Radix Tricks» довольно быстро, единственная проблема в том, что он возвращает отсортированные значения вместо индексов, кроме того, он портит значения входного массива.
Любая помощь будет оценена.
Решение
Вы также можете
-
Разверните каждый элемент, чтобы включить его исходный индекс (это можно сделать во время первого прохода подсчета). Конечно, цифры индекса игнорируются для целей сортировки.
-
Храните индексы в контейнерах вместо значений. Выполняйте поиск значения каждый раз, когда требуются цифры.
Первый занимает больше места, но имеет лучшую локальность, второй экономит пространство.
Другие решения
Это довольно просто сделать любой вид индекса на основе.
Любой вид — это серия сравнений и свопов, так что сделайте это.
// 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]
Я не знаком с этими реализациями, но вот внутренняя функция в одной из моих реализаций, только для целых чисел:
//-------------------------------------------------------------------------------------
//! sort the source array based on b-th byte and store the result in destination array
//! and keep index (how to go from the sorted array to the un-sorted)
template<typename T, typename SS, typename SD> inline
void radix_sort_byte(size_t b, array<T, SS>& src, array<T, SD>& dest,
size_array& ind_src, size_array& ind_dest)
{
b *= 8;
size_t B = 256, N = src.size();
size_array bytes = (src >> b) & 0xff; // current byte of each element
size_array count(B, size_t(0)); // occurrences of each element
++count[bytes];
if(count[0] == N) // all bytes are zero; order remains unchanged
{ dest = src; ind_dest = ind_src; return; }
size_array index = shift(cumsum(count), 1); // index-list for each element
size_array pos(N); // position of each element in the destination array
for(size_t i=0; i<N; i++) pos[i] = index[bytes[i]]++;
dest[pos] = src; // place elements in the destination array
ind_dest[pos] = ind_src; // place indices
}
Он не доступен для непосредственного чтения, поскольку использует множество вспомогательных структур и функций, но идея заключается в том, что вы храните отдельный массив с индексами. Когда у вас есть положение элементов в массиве назначения (pos), последние две строки обновляют массив значений и индексный массив точно таким же образом.
Я думаю, вы можете применить ту же идею к любой реализации, но вам придется изменить код.