Ordina rapida VS Radix Sort

Question

In un esame di codifica, una volta mi è stata fatta questa domanda:

.

Supponendo che tu sia solo ordinamento interi in ordine crescente, quale algoritmo usi quando si desidera dare priorità alla velocità di più, ma vuoi anche salvare lo spazio?

Le opzioni erano:

.

.
• lsd radix ordina
• Unisci ordinamento
• Quick Quick

Penso che un argomento possa essere realizzato tra LSD Radix Sort e quicksort .

radix sort funzionerebbe in $ o (kn) $ e quicksort funzionerebbe in $ o (n \ log n) $ e peggiore dei casi, $ o (n ^ 2) $

Ho scelto radix ordina come risposta, ma sono curioso di sapere cosa hanno da dire gli altri.

Answer 1

Dipende ... Se il numero di numeri di input è $ N $ , supponendo il modello di calcolo della RAM di parole, una dimensione della parola di $ \ theta (\ log n) $ bit e ingressi peggiori:

.

• Radix Sort richiederebbe $ o (n \ log n) $ tempo e $ o (n) $ spazio ausiliario.

• quicksort con selezione di pivot fissa o casuale richiederebbe $ o (n ^ 2) $ tempo peggiore e $ O (\ log n) $ spazio ausiliario.

• mergesort richiede $ o (n \ log n) $ tempo e $ o (n) $ < / span> spazio ausiliario.

Radix Sort e Merge Ordinty vengono quindi equivalenti in questa impostazione.

Avviso che utilizzare Quicksort con la selezione PIVOIT casuale Risultati in una complessità del tempo di $ o (n \ log n) $ con alta probabilità. Selezione del pivot deterministicamente in un modo che divise le partizioni degli elementi in due serie le cui cardinalizzazioni sono al massimo un fattore costante, a parte il tuo algoritmo con un algoritmo con la complessità del tempo peggiore di $ o (n \ log n) $ e $ o (\ log n) $ spazio ausiliario.