Classificação rápida vs Radix

Question

Em um exame de codificação, já foi perguntado esta pergunta:

.

Supondo que você esteja Somente Classificando inteiros em ordem crescente, que algoritmo você usa quando deseja priorizar a velocidade mais, mas você também deseja economizar espaço?

As opções foram:

.

• lsd radix sort
• Merge Sort
• classificar rápido

Eu acho que um argumento pode ser feito entre LSD Radix Classe e QuickSort .

radix classificar funcionaria na $ O (kn) $ e QuickSort funcionaria na $ O (n \ log n) $ e pior caso, $ O (n ^ 2) $

Eu escolhi radix classificar como a resposta, mas estou curioso sobre o que os outros tiveram a dizer.

Answer 1

Isso depende ... Se o número de números de entrada for $ n $ , assumindo o modelo de RAM de palavras de computação, um tamanho de palavra $ \ theta (\ log n) $ bits e piores insumos:

• radix tipo exigiria $ o (n \ log n) $ tempo e $ O (n) $ espaço auxiliar.

• QuickSort com seleção de pivô fixo ou aleatório exigiria $ O (n ^ 2) $ tempo de pior caso e $ O (\ Log n) $ Espaço auxiliar.

• mergesort requer $ o (n \ log n) $ tempo e $ O (n) $ < / SPAN> Espaço auxiliar.

Classe Radix e tipo de mesclagem são então equivalentes nesta configuração.

Observe que o uso do QuickSort com a seleção de Pivoit aleatório resulta em uma complexidade de tempo de $ o (n \ log n) $ com alta probabilidade. Selecionando o pivô deterministicamente de uma forma que particiona os elementos em dois conjuntos cujos cardinalidades são, no máximo, um fator constante Apart dá a sua um algoritmo com a pior complexidade de tempo de $ O (n \ logs n) $ e $ o (\ log n) $ espaço auxiliar.