Un ordinamento di classificazione veloce e basato su rango per i galleggianti?

Question

Sto cercando un'implementazione di ordinamento radix stabile e veloce (con supporto di float) che restituisce gli indici dell'ordine ordinato invece dei valori ordinati. La versione di

Pierre Terdiman dal suo articolo "Radix Sort Revisited" fa esattamente quello che voglio tuttavia è più di 13 anni, e non è adatto per le moderne CPU pipeline.

di Michael Herf RadixSort11 da "Radix Tricks" è abbastanza veloce, l'unico problema che restituisce i valori ordinati invece degli indici, inoltre corrompe i valori della matrice di input.

Qualsiasi aiuto sarebbe apprezzato.

Answer 1

è possibile

1. Espandere ogni elemento per includere il suo indice originale (questo potrebbe essere fatto durante il primo passaggio di conteggio). Ovviamente, le cifre dell'indice vengono ignorate ai fini dell'ordinamento.

2. Memorizza gli indici in bucket anziché valori. Cerca il valore ogni volta che le cifre sono richieste.

Il primo richiede più spazio ma ha una migliore località di riferimento, il secondo consente di risparmiare spazio.

Answer 2

È abbastanza semplice creare qualsiasi indice di ordinamento. Qualsiasi tipo è una serie di confronti e scambi, quindi fai questo.

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

non ho familiarità con queste implementazioni, ma qui è la funzione interna in uno dei miei implementazioni, per gli interi solo:

//------------------------------------------------------------------------------------- 
//! 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 
} 

Non è direttamente leggibile perché utilizza un sacco di strutture ausiliarie e funzioni, ma l'idea è di mantenere un array separato con gli indici. Una volta ottenuta la posizione degli elementi nell'array di destinazione (pos), le ultime due righe aggiornano la matrice di valori e l'array di indice esattamente nello stesso modo.

Immagino che tu possa applicare la stessa idea a qualsiasi implementazione, ma dovresti modificare il codice.