Perché quicksort è più popolare di radix-tipo?

Question

Perché quicksort (o introsort), o qualsiasi algoritmo di ordinamento basato sui confronti è più comune di quanto radix-tipo? Soprattutto per l'ordinamento numeri.

Radix-tipo non è confronto basato, quindi può essere più veloce di O (n logn). In realtà, è O (k n), dove k è il numero di bit utilizzati per rappresentare ciascun elemento. E il sovraccarico di memoria non è critica, in quanto si può scegliere il numero di secchi da usare, e memoria richiesta può essere inferiore a requisiti di mergesort.

Ha a che fare con il caching? O forse l'accesso ai byte casuali di interi nella matrice?

Answer 1

Due argomenti mi vengono in mente:

1. Quicksort / Introsort è più flessibile:

   Quicksort e Introsort lavoro bene con tutti i tipi di dati. Tutto ciò che serve per l'ordinamento è la possibilità di confrontare gli elementi. Questo è banale con i numeri, ma è possibile ordinare altri dati pure.

   Radix sorta d'altra parte appena ordina cose con il loro rappresentazione binaria. Non è mai confronta articoli contro l'altro.

2. Radix ha bisogno di specie più memoria.

   Tutte le implementazioni ordinamento digitale che ho visto usare un buffer secondario per memorizzare i risultati parziali smistamento. Questo aumenta i requisiti di memoria del algoritmo di ordinamento. Che potrebbe non essere un problema se solo tipo un paio di kilobyte, ma se si va nella gamma gigabyte fa una differenza enorme.

   Se ricordo bene un posto in radix-sorta algoritmo di esistere sulla carta però.

Answer 2

Una risposta ovvia è che si può tipi sorta arbitrarie utilizzando quicksort (vale a dire tutto ciò che è paragonabile), mentre si sono limitati a solo numeri con radix. E IMO Quicksort è molto più intuitivo.

Answer 3

Radix sort è più lento per (la maggior parte) i casi d'uso reali.

Una delle ragioni è la complessità dell'algoritmo:

Se gli articoli sono unici, k> = log (n). Anche con gli elementi duplicati, l'insieme dei problemi in cui k

Un altro è l'implementazione:

Il requisito di memoria aggiuntiva (che è di per sé è uno svantaggio), influisce negativamente le prestazioni della cache.

Penso che sia giusto dire che molte biblioteche, come la libreria standard, utilizzare Quicksort perché comporta meglio nella maggior parte dei casi. Non credo che "l'attuazione difficile" o "meno intuitiva" sono i principali fattori.

Answer 4

Come accennato in Wikipedia

  

Il tema dell'efficienza del radix sort rispetto ad altri algoritmi di ordinamento è un po 'difficile e soggetto a un bel po' di incomprensioni. Sia ordinamento digitale è altrettanto efficiente, meno efficiente o più efficienti i migliori algoritmi di confronto basata dipende dai dettagli delle assunzioni fatte. Radix efficienza ordinamento è O (d · n) per n chiavi che hanno D o meno cifre. A volte d si presenta come una costante, il che renderebbe radix sort migliore (per n sufficientemente grande) rispetto ai migliori algoritmi di ordinamento basato sui confronti, che sono tutti O (n · log (n)) numero di confronti necessari. Tuttavia, in generale, d non può essere considerata una costante. In particolare, sotto il comune (ma talvolta implicita) presupposto che tutte le chiavi sono distinte, allora D deve essere almeno dell'ordine di log (n), che dà al meglio (con tasti densamente) un tempo di complessità O (n · log (n)) . Questo sembrerebbe rendere radix sort al massimo altrettanto efficace come i migliori tipi di confronto-based (e peggio se le chiavi sono molto più lungo di log (n)).

     

L'argomento contatore è algoritmi di confronto basati sono misurati in numero di confronti non corrisponde alla complessità temporale. Sotto alcune ipotesi il confronto sarà costante di tempo, in media, sotto gli altri non lo faranno. Confronti di chiavi generate in modo casuale impiega un tempo costante in media, come chiavi differiscono sul primo bit nella metà dei casi, e differiscono sul secondo bit metà della metà rimanente, e così via, determinando una media di due bit che bisogno di essere confrontato. In un algoritmo di ordinamento primi confronti effettuati soddisfa la condizione di casualità, ma come ordinamento progredisce i tasti confronto non sono chiaramente scelti più casualmente. Ad esempio, si consideri un approccio bottom-up merge sort. Il primo passaggio confronterà coppie di chiavi casuali, ma l'ultima passata confronterà chiavi che sono molto vicini nell'ordine di ordinamento.

     

Il fattore decisivo è il modo le chiavi vengono distribuite. Il caso migliore per ordinamento digitale è che essi sono presi come modelli di bit consecutivi. Questo renderà i tasti più corti possono essere, sempre supponendo sono distinti. Questo rende radix sort O (n · log (n)), ma il genere di confronto basato non sarà così efficace, come il confronto non sarà costante di tempo in tale ipotesi. Se invece assume che le chiavi sono modelli di bit di lunghezza k · log (n) per una costante k> 1 e base 2 log, e che sono uniformemente casuale, quindi ordinamento digitale sarà ancora O (n · log (n) ), ma così sarà il genere di confronto basato, come la lunghezza "extra" rende anche le chiavi che sono consecutivi nel risultato ordinato differire sufficiente che i paragoni sono costante di tempo in media. Se i tasti sono più lunghi di O (log (n)), ma casuale, quindi radix sort sarà inferiore. Ci sono molte altre ipotesi che possono essere fatte così, e la maggior parte richiede un attento studio per fare un confronto corretto.

Answer 5

Punti realizzati in altre risposte sono valide, ma per quanto riguarda la vostra preoccupazione di cui diversi commenti

  

... il fatto che il default algoritmi di ordinamento per i numeri vengono implementati utilizzando Quicksort. Soprattutto le implementazioni nelle biblioteche ...

Quicksort è la scelta 'sicuro'. Il potenziale di esecuzione di un radix sort basata su un conteggio sorta è molto interessante, sì, ma radix sort è subsceptible per scarso rendimento sul set di dati maligni / sfortunato. Se il numero di cifre dei tasti vengano filtrate avvicina al numero di chiavi da ordinare, esegue ordinamento digitale su n ^ 2 lungo una superficie complessità non trascurabile, e tende ad avere abbastanza elevato built costanti runtime diverse da quella del numero di cifre delle chiavi da ordinare.
Mergesort è interessante perché il suo comportamento è, per certi versi, analoga a un Quicksort che raccoglie un perno ottimale in ogni occasione (la mediana). Tuttavia, si tratta di uno spazio complessità apprezzabile. Non è così per subsceptible maligni / dati sfortunati come radix, ma anche non offre l'interessante possibilità di esecuzione. A esegue Quicksort di base molto bene sulla maggior parte dei set di dati, eccetto quasi (o del tutto) ordinati quelli, e viene fornito con un piccolo spazio complessità.
La vulnerabilità di Quicksort è facilmente trattata da convertendolo in un quicksort randomizzato. La vulnerabilità di radix sort viene risolto ponendo restrizioni sui tasti in fase di ordinamento, che sarebbe intrinsecamente limitare gli utenti della biblioteca. Quicksort è più performante rispetto merge su piccoli insiemi di dati, e effettua ragionevolmente quando merge potrebbe essere più veloce.
Quando si implementa una libreria, si vuole rendere più genericamente utile. Prendete questi esempi, un'applicazione web e un piccolo dispositivo con un microcontrollore estremamente limitato. Le applicazioni Web hanno bisogno di trattare con dati dannosi su base regolare, e hanno anche una vasta gamma di esigenze. Una biblioteca con restrizioni precondizionati ha meno probabilità di essere utili. Nel caso del microcontrollore, esso può essere restrittivo limitato sullo spazio e in grado di cedere il minimo in cui si può essere salvati. Quicksort consente di risparmiare spazio, e completerà solo più lento per una costante moltiplicatore IF si verifica una situazione che è più lento.
In sintesi -
1.) Le biblioteche sono spesso codificate per quanto più l'usabilità generico possibile
2.) Buona prestazione tutto è accettabile, soprattutto se si è in molti casi, le migliori prestazioni
3.) Lo spazio non è sempre una questione primaria, ma quando lo è, è spesso esplicitamente restrittivamente, in modo

Answer 6

l'efficienza di Radix sort = O (c.n) dove c = maggior numero di cifre tra i set di chiavi di ingresso. n = numero di chiavi in ??set di chiavi di ingresso.

migliore dei casi di rapida sorta = O (n. Log n) dove n = numero di chiavi in ??set di chiavi di ingresso.

Si supponga 16 numeri da ordinare a 6 cifre ogni:

Radix sort = 16 unità * 6 = 96 tempo. Breve sort = 16 * 4 = 64 unità di tempo.

Lezione: Quando 'c' è meno, Radix non vincere. Quando è alto, perde. Breve sorta è indipendente dal numero di cifre in una chiave e che rende alquanto migliore e più praticamente accettabile