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.