Быстрый, ранг Radix Sort для поплавков?

Question

Я ищу для быстрого стабильного выполнения сортировки по ради (с поддержкой поплавков), который возвращает индексы отсортированного порядка вместо отсортированных значений. версия

Пьера Terdiman в из его статьи "Radix Sort Revisited" делает именно то, что я хочу, однако это более 13 лет, и не подходит для современных конвейерных процессоров.

Майкла Herf в RadixSort11 из "Radix Tricks" довольно быстро, единственная проблема, что она возвращает отсортированные значения вместо индексов, кроме того, она развращает значения входного массива.

Любая помощь будет оценена по достоинству.

Answer 1

Вы можете

1. Разверните каждый элемент, чтобы включить свой первоначальный индекс (это может быть сделано во время первого подсчета прохода). Разумеется, цифры индекса игнорируются для сортировки.

2. Хранить индексы в ведрах вместо значений. Поиск значения каждый раз, когда цифры необходимы.

Первый занимает больше места, но имеет лучшую локальность ссылки, а второй экономит место.

Answer 2

Достаточно просто сделать любой индекс на основе индекса. Любой вид - это серия сравнений и свопов, поэтому сделайте это.

// 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] 

Answer 3

Я не знаком с этими реализациями, но вот внутренняя функция в одной из моих реализаций, только для целых чисел:

//------------------------------------------------------------------------------------- 
//! 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), последние две строки точно обновляют массив значений и индексный массив.

Я думаю, вы можете применить ту же идею к любой реализации, но вам придется изменить код.