Quicksort: algoritmo de ordenación por particiones — definición y funcionamiento

Quicksort: explicación clara del algoritmo de particiones, funcionamiento, elección de pivote, eficiencia y ejemplos prácticos. Aprende su definición y aplicación.

Quicksort es un algoritmo de ordenación que se utiliza para ordenar los elementos de un arreglo. Fue creado por Tony Hoare en 1959 y sigue siendo uno de los algoritmos de referencia para ordenar por comparación. Su idea básica es dividir y conquistar: selecciona un elemento llamado pivote, reordena (particiona) el arreglo para que los elementos menores queden a un lado y los mayores al otro, y luego aplica recursivamente el mismo procedimiento a las subpartes.

Cómo funciona (concepto general)

Los pasos generales de Quicksort son:

• Elegir un pivote: puede ser el primer elemento, el último, un elemento aleatorio o una mediana aproximada.
• Particionar: reorganizar el arreglo de modo que los valores ≤ pivote queden a la izquierda y los ≥ pivote a la derecha (la definición exacta depende del esquema de partición).
• Recursión: aplicar Quicksort a la subparte izquierda y a la subparte derecha hasta que las subpartes tengan tamaño 0 o 1.

Esquemas de partición

Los dos esquemas más conocidos son:

• Partición de Hoare: utiliza dos índices que se mueven desde los extremos hacia el centro; suele ser más eficiente y realiza menos intercambios.
• Partición de Lomuto: más simple de implementar, usa un índice para separar la zona de elementos menores y realiza más intercambios en promedio.

Además hay variantes de partición en tres vías (Dutch National Flag) que son útiles cuando hay muchos elementos iguales: separan en menor, igual y mayor al pivote.

Complejidad y características

• Complejidad promedio: O(n log n).
• Peor caso: O(n²), ocurre cuando la partición es muy desequilibrada (por ejemplo, pivote siempre mínimo o máximo en una lista ya ordenada y elección pobre del pivote).
• Mejor caso: O(n log n), cuando las particiones son equilibradas.
• Espacio: generalmente O(log n) adicional por la pila de recursión en la versión in-place; la implementación iterativa o con eliminación de recursión de cola puede reducir la profundidad práctica.
• No es estable en su forma estándar (el orden relativo de claves iguales no se preserva).
• In-place: sí, las versiones típicas realizan la ordenación sin necesitar una estructura auxiliar proporcional a n.

Optimización y variantes prácticas

• Elección aleatoria del pivote: reduce la probabilidad del peor caso en entradas adversas.
• Mediana de tres: elegir como pivote la mediana entre el primero, el último y el central mejora las particiones en datos parcialmente ordenados.
• Umbral para inserción: cuando las subpartes son pequeñas (p. ej. ≤ 10), cambiar a insertion sort suele ser más eficiente.
• Introsort: híbrido que empieza con Quicksort y cambia a Heapsort si la recursión se vuelve demasiado profunda, garantizando O(n log n) en el peor caso.
• Partición en tres vías: mejora el rendimiento cuando hay muchas claves repetidas.
• Paralelización: las subpartes independientes se pueden ordenar en paralelo para aprovechar arquitecturas multicore.

Ejemplo paso a paso (resumen)

Sea el arreglo [3, 7, 8, 5, 2, 1, 9, 5, 4] y supongamos que elegimos como pivote el último elemento (4) con partición de Lomuto:

• Partición: mover elementos menores que 4 al inicio → resultado parcial: [3, 2, 1, 4, 7, 9, 5, 5, 8] (4 queda en su posición final).
• Aplicar recursión a izquierda [3,2,1] y derecha [7,9,5,5,8] hasta que todas las sublistas estén ordenadas.
• Orden final: [1,2,3,4,5,5,7,8,9].

Implementación (pseudocódigo simplificado)

 function quicksort(A, lo, hi)   if lo < hi     p = partition(A, lo, hi)    // según Lomuto o Hoare     quicksort(A, lo, p - 1)     quicksort(A, p + 1, hi) 

La función partition varía según el esquema escogido. En Lomuto se devuelve la posición final del pivote; en Hoare se devuelve un índice que divide las subpartes.

Cuándo usar Quicksort

• Excelente rendimiento promedio y práctica para arreglos en memoria.
• Buena elección cuando se desea un algoritmo in-place y rápido en la mayoría de casos.
• Si se requiere estabilidad o garantizado O(n log n) en el peor caso, conviene considerar mergesort (estable, O(n log n) pero requiere espacio adicional) o usar introsort.

Resumen: Quicksort es un algoritmo de ordenación por particiones eficiente y versátil en la práctica. Su rendimiento depende mucho de la elección del pivote y del esquema de partición, y existen muchas mejoras y variantes que lo hacen robusto y competitivo en una gran variedad de aplicaciones.

Búsqueda por letra