Ordenamiento rápido
Ordenamiento rápido es un experimento interactivo de Algoritmos en acción, una simulación gratuita de StudyFi Lab que funciona directamente en el navegador.
El ordenamiento rápido elige un pivote —aquí el último elemento del tramo (partición de Lomuto)— y reorganiza el tramo para que los menores queden a la izquierda y el resto a la derecha. Así el pivote queda en su lugar definitivo y las dos partes se ordenan igual. En promedio es O(n log n), pero si el pivote divide mal (por ejemplo, con un arreglo ya ordenado o invertido) cae a O(n²).
Prueba esto: Compara una entrada aleatoria con una invertida. En el arreglo invertido el pivote siempre es el mayor o el menor: observa cómo se disparan las comparaciones.
Preguntas frecuentes
¿Qué muestra el experimento «Ordenamiento rápido»?
El ordenamiento rápido elige un pivote —aquí el último elemento del tramo (partición de Lomuto)— y reorganiza el tramo para que los menores queden a la izquierda y el resto a la derecha. Así el pivote queda en su lugar definitivo y las dos partes se ordenan igual. En promedio es O(n log n), pero si el pivote divide mal (por ejemplo, con un arreglo ya ordenado o invertido) cae a O(n²).
¿Cómo pruebo «Ordenamiento rápido»?
Compara una entrada aleatoria con una invertida. En el arreglo invertido el pivote siempre es el mayor o el menor: observa cómo se disparan las comparaciones.
¿Estudias para un examen?
Sube tus apuntes y StudyFi los convierte en tarjetas, tests y pódcasts.