La ordenación rápida es una ordenación de “divide y vencerás” que funciona creando dos sublistas de una lista y ordenando recursivamente las sublistas. Esto hace que el tiempo de ejecución promedio sea proporcional a N log N donde N es el número de elementos en la lista.
En el peor de los casos, donde el pivote es el elemento mínimo o máximo en la lista cada vez, la ordenación se convierte en una ordenación N ^ 2 pero se ejecuta muy lentamente porque cada elemento individual se ordena recursivamente. Por lo tanto, la selección adecuada del pivote es vital.
Siempre que el elemento sobre el que se divide la lista (el pivote) se elija al azar, se puede esperar una división 3: 1 de la lista (es decir, una sublista contiene 3 veces más elementos que la otra). Esto hace que el tiempo de ejecución sea un poco más largo que un logaritmo de base 2 puro (la base es 1.333) pero aún logarítmico.
- ¿Cómo funciona el algoritmo de acortador de URL?
- ¿Qué algoritmo se usa para detectar "No más interruptores posibles, barajar" en la saga Candy Crush?
- ¿Es la incapacidad de implementar estructuras de datos básicas como una lista doblemente enlazada, un árbol con punteros primarios usando un código seguro la mayor debilidad de Rust?
- ¿Cómo se puede resolver el coeficiente binomial usando programación dinámica y tabla hash?
- Cómo usar un algoritmo para resolver problemas de la vida real
