Radix Sort è l'unico algoritmo di ordinamento senza confronto?
-
12-11-2019 - |
Domanda
Come dice il titolo, radix sort è l'unico algoritmo di ordinamento senza confronto?La mia ipotesi è sì.
Soluzione
No - contano anche il conto e il taglio del secchio, tra gli altri.Controlla il wikipedia Articolo per ulteriori informazioni.
Altri suggerimenti
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.