Radix Sort è l'unico algoritmo di ordinamento senza confronto?

Question

Come dice il titolo, radix sort è l'unico algoritmo di ordinamento senza confronto?La mia ipotesi è sì.

Answer 1

No - contano anche il conto e il taglio del secchio, tra gli altri.Controlla il wikipedia Articolo per ulteriori informazioni.

Answer 2

Qualsiasi insieme può essere ordinato senza utilizzare i confronti.

Il processo è

• decidere una dimensione gestibile del dominio di input M che è possibile gestire per registrare in un array gestibile.Per i caratteri (8 bit) il dominio sarebbe 0-255.
• dividere l'input in modo ordinato nell'array.
• ripetere e risciacquare se l'input non è ancora completamente considerato, ad es.tutti i bit in M ​​non sono stati considerati.

Ad esempio, un ordinamento di numeri interi M a 32 bit potrebbe essere eseguito come:

• guarda i primi 8 bit, inserisci (riferimenti, puntatori o ciò che il tuo lang ha a disposizione), nell'intervallo di 8 bit.inseriscili in un array [0-255], ora hai un ordinamento approssimativo (ballpark) dei tuoi valori.
• guarda i successivi 8 bit, inseriscili in un array simile, mantieni un riferimento al primo ordinamento.I successivi 8x2 bit vengono gestiti allo stesso modo.Per estrarlo segui i link del primo set.

L'ordinamento radicale utilizza cifre e ha 2 varianti, (da MSB a LSB) e (da LSB a MSB).

L'ordinamento del conteggio utilizza solo il primo passaggio

L'ordinamento bucket viene solitamente menzionato quando si fa riferimento a un mix di ordinamento di conteggio e di confronto.

È interessante notare che, per alcuni casi d'uso, i tipi di confronto risultano insufficienti.