Comparaciones
Intercambios
Particiones

  • Parte que se particiona
  • Pivote
  • Comparadas
  • Intercambiadas
  • En su sitio

Más sobre quicksort

Quicksort

El quicksort, u ordenamiento rápido, elige un pivote, pone todos los valores menores antes de él y todos los demás después, y luego ordena los dos lados de la misma forma. Tras cada partición, el pivote queda en su lugar definitivo. Elige la regla del pivote, reproduce la ordenación a cualquier velocidad o avanza de comparación en comparación, y descubre por qué un mal pivote en una lista ordenada hace lento el quicksort. Pulsa Reproducir para ver la ordenación, o Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto. Los recuadros cuentan comparaciones, intercambios y particiones. Elige cuántas barras hay, cómo empiezan, o escribe tus propios números, y cómo se elige el pivote. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.

Cómo funciona

  1. Elige cuántas barras hay y cómo empiezan: aleatorias, casi ordenadas, invertidas o con pocos valores distintos. O escribe tus propios números.
  2. Pulsa Reproducir, o usa Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto de la ordenación.
  3. Elige la regla del pivote: el último valor, el valor central, un valor aleatorio o la mediana de tres. Prueba cada una con una lista ordenada.

Cómo funciona el quicksort

Elige un valor de la parte que hay que ordenar como pivote y muévelo al final. Recorre los demás valores de izquierda a derecha; cada uno que sea menor que el pivote se intercambia hacia una parte izquierda que crece desde el principio. Después, intercambia el pivote justo detrás de la parte izquierda. Todo lo que hay antes es ahora menor y nada de lo que hay después lo es, así que el pivote está en su lugar definitivo. Ordena igual la parte anterior y la posterior, hasta que cada parte tenga un solo valor.

Por qué importa el pivote

Cuando el pivote cae cerca del centro, cada partición divide el problema por la mitad y las comparaciones crecen como n log n: para 40 valores aleatorios, unas 190. Cuando el pivote es el valor más pequeño o el más grande, un lado queda vacío y el otro tiene todo lo demás. Con el último valor como pivote, eso pasa en cada paso con una lista ordenada o invertida, y la ordenación necesita n(n − 1)/2 comparaciones, 780 para 40 valores. Un pivote aleatorio o la mediana del primer valor, el central y el último lo evita en la práctica.

Preguntas frecuentes

¿Cómo funciona el quicksort?

Elige un pivote, particiona la lista para que los valores menores queden antes del pivote y el resto después, y luego ordena ambos lados con quicksort. Tras cada partición, el pivote está en su lugar definitivo.

¿Por qué el quicksort es lento con una lista ordenada?

Con el primer o el último valor como pivote, una lista ordenada siempre da como pivote el valor más pequeño o el más grande. Un lado de la partición queda entonces vacío, así que cada partición solo quita un valor, y la ordenación necesita n(n − 1)/2 comparaciones. Un pivote aleatorio o la mediana de tres lo soluciona en la práctica.

¿Es el quicksort más rápido que el ordenamiento por mezcla?

A menudo, en la práctica: ordena in situ, no necesita un búfer y su bucle interno es muy sencillo. De media hace algo más de comparaciones que el ordenamiento por mezcla, y su peor caso es n², mientras que el ordenamiento por mezcla siempre es n log n. Los ordenamientos de las bibliotecas, como introsort, empiezan con quicksort y pasan al ordenamiento por montículos si las divisiones se vuelven demasiado desiguales.

¿Es estable el quicksort?

No. Una partición intercambia valores a mucha distancia, así que valores iguales pueden cambiar de orden.

¿Se envían mis números a algún sitio?

No. La ordenación se ejecuta en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Ir al editor