Quicksort tiene O ( n 2) peor tiempo de ejecución y O ( n log n ) promedio de tiempo de ejecución del caso. Sin embargo, es mejor combinar el orden en muchos escenarios porque muchos factores influyen en el tiempo de ejecución de un algoritmo y, cuando se combinan todos, gana la selección rápida.
En particular, el tiempo de ejecución a menudo citado de los algoritmos de clasificación se refiere a la cantidad de comparaciones o la cantidad de intercambios necesarios para realizar la clasificación de los datos. De hecho, esta es una buena medida de rendimiento, especialmente porque es independiente del diseño de hardware subyacente. Sin embargo, otras cosas, como la localidad de referencia (es decir, ¿leemos muchos elementos que probablemente están en caché?) También juegan un papel importante en el hardware actual. Quicksort en particular requiere poco espacio adicional y exhibe una buena ubicación de caché, y esto hace que sea más rápido que la fusión en muchos casos.
Además, es muy fácil evitar el tiempo de ejecución de O ( n 2) en el peor de los casos de quicksort casi por completo utilizando una elección adecuada del pivote, como elegirlo al azar (esta es una estrategia excelente).
- ¿Encontrar la complejidad temporal de los algoritmos está relacionado con las matemáticas discretas?
- Cómo implementar un algoritmo de programación de disco C-SCAN para encontrar su tiempo de búsqueda
- ¿Cuáles son algunos algoritmos utilizados por las grandes empresas (como Amazon) para determinar de manera eficiente desde qué almacén se debe cumplir un pedido?
- ¿Cuál es el problema con mi código de C ++ para SPOJ.com - Problema PALIN?
- ¿Es el tiempo de blog digno de mí?
En la práctica, muchas implementaciones modernas de quicksort (en particular, stst std::sort libstdc ++) son en realidad introsort, cuyo peor caso teórico es O ( n log n ), igual que merge sort. Esto se logra limitando la profundidad de recursión y cambiando a un algoritmo diferente (montón) una vez que excede el log n
