Implementazione ordinamento scambio radix?

Question

Implementazione ordinamento scambio radix?

#1 da (1 voti)
#2 da (0 voti)

1

Ho bisogno di un piccolo aiuto per capire l'implementazione dell'algoritmo di scambio di scambio di radix.

Lo scambio di raggi (non so se è il nome esatto nella letteratura inglese) è molto simile a quicksort, ma usa la rappresentazione binaria dei numeri.

Iniziamo guardando la cifra più alta nella rappresentazione binaria, e quindi usando due indici (dall'inizio della matrice e dalla fine, incrementiamo il primo se la cifra data è 0, e decrementiamo l'altra se la cifra data è 1). Quindi scambiamo due numeri e quindi continuiamo il lavoro fino a quando i = j (gli indici sono uguali). Quindi abbiamo due partizioni separate e le ordiniamo usando la seconda cifra più importante e così via ...

Principalmente, ho alcune domande:

Questo algoritmo si chiama davvero scambio di radix o ha qualche altro nome più comunemente usato?
Quali sono i vantaggi di questo algoritmo? Sembra un sacco di lavoro, e non molto efficace?
Dove posso vedere un esempio di implementazione dell'algoritmo? Forse sarà un po 'più chiaro su cosa sia realmente, perché al momento è davvero difficile per me.

data-structures algorithms data sorting

posta idjuradj 02.06.2013 - 00:48

fonte

2 risposte

Leggi altre domande sui tag data-structures algorithms data sorting

Test dell'interfaccia utente per l'app Web blu su iPad Come ottenere un riferimento ad un AssetLoader centrale in ogni Widget?

score 1 · Answer 1

sembra che la complessità temporale sarebbe O (n * k) e la complessità spaziale è O (k) con k che è il numero di bit di ciascun elemento

in C ++ sarebbe

radixQsort(int* arrb, int* arre, int rad=INT_BITS){
    if(arrb==arre)return;

    int* arrm = std::partition(arrb,arre,[rad](a){return !(a&(1<<rad));});

    radixQsort(arrb,arrm,rad-1);
    radixQsort(arrm,arre,rad-1);
}

questo è implementato usando la partizione nella libreria standard che funziona come la partizione che hai descritto

score 0 · Answer 2

In contrasto con l'ordinamento rapido, l'ordinamento digitale usa "rappresentazione interna" dei valori che sono ordinati. Cioè non li confronta semplicemente con < & Gt ;. Ed è davvero efficace quando prendi diversi bit, non uno, su ogni passaggio di smistamento. 4 bit, forse 8. Quindi dividerete l'array su 256 gruppi per ogni passaggio in quest'ultimo caso. E hanno solo 4 passaggi per numeri interi a 32 bit.

link