Ordenar rápido vs Radix Sort

Question

En un examen de codificación, una vez me preguntaron esta pregunta:

Suponiendo que usted es solo Clasificación de enteros en orden ascendente, ¿qué algoritmo utiliza cuando desea priorizar la velocidad más, pero también desea ahorrar espacio?

Las opciones fueron:

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

Creo que se puede hacer un argumento entre LSD Radix Sort y Quicksort .

Radix Sort funcionaría en $ o (kn) $ y Quicksort funcionaría en $ o (n \ log n) $ y el peor de los casos, $ o (n ^ 2) $

Elegí Radix Sort como la respuesta, pero tengo curiosidad en cuanto a lo que otros tuvieron que decir.

Answer 1

Esto depende ... Si el número de números de entrada es $ n $ , suponiendo que el modelo de cálculo de Word-Ram, un tamaño de palabra de $ \ THETA (\ log n) $ bits, y en el peor de los casos:

• Radix Ordenaría $ o (n \ log n) $ tiempo y $ o (n) $ espacio auxiliar.

• Quicksort con selección de pivote fijo o aleatorio requeriría $ o (n ^ 2) $ tiempo en el peor caso y $ O (\ log n) $ espacio auxiliar.

• Mergesort requiere $ o (n \ log n) $ tiempo y $ o (n) $ < / span> espacio auxiliar.

Radix Sort and Ferge Sort es entonces equivalente en esta configuración.

Observe que el uso de Quicksort con la selección de pivoit aleatorios da como resultado una complejidad de tiempo de $ o (n \ log n) $ con alta probabilidad. Seleccionando el pivote determinista de manera determinista de manera que particione los elementos en dos conjuntos cuyas cardinales son a lo sumo un factor constante, le da a su algoritmo con la complejidad del peor de los casos de $ o (n \ log n) $ y $ o (\ log n) $ espacio auxiliar.