Entendiendo Quicksort con ejemplos en JavaScript

Quicksort es un algoritmo de ordenamiento de tipo divide y vencerás: elige un elemento pivote, particiona el arreglo de modo que los elementos menores queden a la izquierda y los mayores a la derecha, y luego ordena recursivamente cada lado in situ.

La mayoría de nosotros nos topamos con él por primera vez frente a una pizarra con alguien observando, y el bucle de partición es donde la confianza suele desvanecerse. Se ejecuta en tiempo O(n log n) en promedio, ordena sin necesidad de asignar un segundo arreglo, y es el algoritmo al que recurren la mayoría de los entrevistadores cuando te piden que “ordenes esto a mano”.

Este artículo cubre tres cosas: una versión legible para construir intuición, un recorrido manual de una pasada de partición para que veas cómo se mueven los elementos, y la implementación in situ que realmente escribirías en una entrevista, además de notas sobre complejidad, elección del pivote y estabilidad.

¿Cómo funciona el algoritmo quicksort?

Quicksort ordena dividiendo repetidamente el arreglo alrededor de un pivote elegido. Una pasada de partición reorganiza los elementos de modo que todo lo menor que el pivote quede antes de él y todo lo mayor quede después; el pivote entonces ocupa su posición final ordenada. Al aplicar el mismo paso a los subrangos izquierdo y derecho, el arreglo completo se ordena por sí solo.

Comparte la estructura de divide y vencerás del merge sort, pero los compromisos difieren. Tanto quicksort como merge sort promedian O(n log n), pero quicksort ordena in situ con O(log n) de espacio auxiliar, mientras que merge sort necesita O(n) de espacio extra, y merge sort es estable mientras que quicksort no lo es. Quicksort intercambia esa estabilidad garantizada por una menor sobrecarga de memoria y una gran velocidad en el mundo real.

Primero, la versión legible (filter y spread)

El quicksort más fácil de leer particiona con filter y reconstruye el arreglo con el operador de propagación (spread). Es la forma más rápida de captar la recursión, y es una buena herramienta didáctica, pero asigna nuevos arreglos en cada llamada, por lo que no es realmente in situ y usa memoria adicional.

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const [pivot, ...rest] = arr;
  const left = rest.filter((x) => x < pivot);
  const right = rest.filter((x) => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort([3, 7, 2, 5, 1, 4, 6, 8]); // [1, 2, 3, 4, 5, 6, 7, 8]

El caso base (length <= 1) detiene la recursión, ya que un arreglo de cero o un elemento ya está ordenado. Cada llamada construye tres arreglos nuevos, por lo que el uso de memoria de esta versión crece con la entrada en lugar de mantenerse constante. Úsala para explicar la idea; usa la versión in situ que aparece más abajo cuando la memoria o las expectativas de una entrevista sean lo importante.

¿Cómo funciona el particionado?

El particionado es el motor de quicksort, así que vale la pena observar una pasada de cerca. El esquema de Lomuto toma el último elemento como pivote, recorre el rango con un índice de escaneo j y mantiene un índice de frontera i que marca dónde corresponde el siguiente elemento “menor que el pivote”. Cada vez que arr[j] es menor que el pivote, intercambia arr[i] y arr[j] y avanza i. Al final, intercambia el pivote a la posición i.

Sigamos el recorrido de [7, 2, 1, 8, 6, 3, 5, 4] con pivote 4 (el último elemento), comenzando con i = 0:

El pivote 4 queda en el índice 3, con [2,1,3] a su izquierda y [6,7,5,8] a su derecha. Ninguno de los dos lados está ordenado todavía, pero el pivote está colocado de forma permanente, y los dos lados son ahora subproblemas independientes.

function partition(arr, lo, hi) {
  const pivot = arr[hi];          // last element as pivot
  let i = lo;                     // boundary for elements < pivot
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // move pivot into place
  return i;
}

El quicksort in situ que escribirías en una entrevista

El quicksort con forma de producción conserva la función auxiliar de partición anterior y aplica recursión sobre rangos de índices (lo, hi) en lugar de construir nuevos arreglos. Esta es la versión a la que debes recurrir cuando alguien te pida implementar quicksort: muta un único arreglo y solo utiliza la pila de recursión como espacio adicional.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

quickSort([7, 2, 1, 8, 6, 3, 5, 4]); // [1, 2, 3, 4, 5, 6, 7, 8]

Cada llamada particiona su rango y luego aplica recursión sobre los dos subrangos alrededor del pivote. La condición lo < hi es el caso base: un rango de cero o un elemento ya está ordenado. Si la recursión no es una opción (una pregunta de seguimiento habitual en entrevistas), la misma lógica se convierte en una versión iterativa apilando pares lo/hi en una pila explícita en lugar de la pila de llamadas.

Complejidad, elección del pivote y estabilidad

El costo de quicksort lo determina casi por completo el pivote. Con divisiones equilibradas, cada nivel de recursión toca cada elemento una vez a lo largo de aproximadamente log n niveles, lo que da O(n log n). Cuando las divisiones son sistemáticamente desbalanceadas, la profundidad de la recursión crece hasta n y el costo se degrada a O(n²). In situ, la pila de recursión representa O(log n) de espacio con entradas equilibradas.

La trampa clásica: elegir el primer o el último elemento como pivote hace que quicksort alcance su peor caso O(n²) con entradas ya ordenadas, porque cada partición separa solo un elemento. Puedes evitar el peor caso con entradas ordenadas eligiendo el elemento central, usando la mediana de tres o escogiendo un pivote aleatorio. La mediana de tres ordena el primer elemento, el central y el último, y usa la mediana, lo que resiste tanto entradas adversarias ordenadas como ordenadas de forma inversa:

function medianOfThree(arr, lo, hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] < arr[lo]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
  if (arr[hi]  < arr[lo]) [arr[lo], arr[hi]]  = [arr[hi], arr[lo]];
  if (arr[hi]  < arr[mid]) [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  // median now sits at mid; move it to hi so Lomuto uses it as the pivot
  [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  return arr[hi];
}

Hay una propiedad que ninguna estrategia de pivote puede recuperar: quicksort no es un ordenamiento estable, por lo que los elementos iguales pueden reordenarse respecto a sus posiciones originales. Eso importa cuando ordenas registros por una clave secundaria y esperas que el orden principal se conserve.

¿El sort integrado de JavaScript es quicksort?

No. Aunque el algoritmo quicksort es inestable, el método integrado Array.prototype.sort de JavaScript tiene estabilidad garantizada desde ES2019, la décima edición del estándar del lenguaje. V8 ordena arreglos con Timsort desde la v7.0 y Chrome 70: un merge sort que aprovecha las secuencias de datos ya ordenados y deja los elementos iguales en el orden en que los encontró. Todos los demás motores principales están sujetos al mismo requisito de estabilidad por parte de la especificación. Así que “quicksort es inestable” describe el algoritmo, no el sort integrado de ningún navegador moderno.

Quicksort se ha ganado su reputación gracias a un bucle de partición compacto, su funcionamiento in situ y su velocidad promedio O(n log n), siempre que mantengas el pivote alejado de los extremos del arreglo. Implementa la versión in situ mostrada arriba con una mediana de tres o un pivote aleatorio, pruébala con una entrada ya ordenada para confirmar que no explota, y serás capaz tanto de escribir quicksort como de explicar sus compromisos cuando te lo pidan.

Preguntas frecuentes

¿Cuándo debería usar quicksort en lugar de merge sort?

Usa quicksort cuando la memoria esté limitada y quieras ordenar in situ, ya que solo necesita O(log n) de espacio auxiliar para la pila de recursión frente al arreglo extra de O(n) del merge sort. Ambos promedian O(n log n), pero quicksort es más rápido en la práctica con datos típicos. Elige merge sort cuando necesites estabilidad garantizada o un peor caso garantizado de O(n log n), ya que quicksort puede degradarse a O(n cuadrado).

¿Por qué quicksort alcanza O(n cuadrado) con un arreglo ya ordenado?

Un pivote fijo en el primer o último elemento se degrada a O(n cuadrado) con entradas ordenadas porque cada partición coloca el pivote en un extremo y produce un subrango vacío y otro rango de n menos 1 elementos. Eso genera n niveles de recursión en lugar de log n, cada uno realizando trabajo lineal. La solución es elegir el elemento central, usar la mediana de tres o escoger un pivote aleatorio, opciones que restauran divisiones equilibradas con datos ordenados.

¿Array.prototype.sort de JavaScript está implementado con quicksort?

No. Los motores modernos no usan quicksort para el sort integrado. V8 usa Timsort desde la v7.0 y Chrome 70, un merge sort que aprovecha las secuencias de datos ya ordenados y preserva el orden de los elementos iguales. Desde ES2019, la especificación ECMAScript exige que Array.prototype.sort sea estable, y todos los motores principales incluyen un ordenamiento estable. Así que el algoritmo quicksort es inestable, pero el sort integrado no es quicksort y tiene estabilidad garantizada.

¿Cuál es la diferencia entre los esquemas de partición de Lomuto y de Hoare?

Lomuto usa un único índice de escaneo y normalmente toma el último elemento como pivote, intercambiando los elementos menores hacia un índice de frontera; es más sencillo de escribir y de seguir paso a paso. Hoare usa dos punteros que se mueven hacia adentro desde ambos extremos y generalmente realiza menos intercambios, lo que lo hace más rápido en la práctica. Ambos particionan in situ y devuelven un punto de división, pero el índice que devuelve Hoare no coloca el pivote en su posición final como sí hace el de Lomuto.

¿Cómo convierto un quicksort recursivo en una versión iterativa?

Reemplaza la pila de llamadas por una pila explícita de rangos de índices. Apila el par inicial lo y hi, y luego itera mientras la pila no esté vacía: extrae un rango, particiónalo para obtener un índice de pivote p, y vuelve a apilar los dos subrangos de lo a p menos 1 y de p más 1 a hi cuando contengan más de un elemento. Esto produce el mismo resultado evitando la recursión, una pregunta de seguimiento habitual en entrevistas.