Ordenamiento rápido (Quick Sort)

Mira cómo quicksort reparte las barras alrededor de un pivote. Media O(n log n) y suele ser el más rápido — pero el arreglo invertido cae a O(n²).

Algoritmo

Arreglo

Tamaño48
ComparandoIntercambioPivote/claveLecturaOrdenado
Velocidad50×

Comparaciones

0

Intercambios

0

Paso

0/467

Lecturas

0

Memoria aux.

0

Profundidad

1/1

Baja la velocidad y usa «Paso» para contrastar el resaltado del pseudocódigo con los colores de las barras.

Pseudocódigo

quickSort(lo, hi)

pivot ← a[hi]

for j ← lo to hi−1

if a[j] ≤ pivot: a[i++] ↔ a[j]

a[i] ↔ a[hi] // 피벗 확정

quickSort(lo,i−1) quickSort(i+1,hi)

Complejidad

MejorO(n log n)
MediaO(n log n)
PeorO(n²)
EspacioO(log n)
EstableNo

Quicksort elige un pivote (barra morada), mueve los menores a la izquierda y los mayores a la derecha, y repite en cada lado. La posición final del pivote queda fijada tras cada partición.

Con pivotes equilibrados la profundidad es log n: media O(n log n) y gran localidad de caché, por eso es la base de la mayoría de sorts integrados. Con un pivote siempre malo (último elemento en arreglo invertido) cae a O(n²) — pruébalo con el preset Invertido. Visualizador de ordenamiento

Preguntas frecuentes

¿Por qué es estándar si puede llegar a O(n²)?
El pivote aleatorio o mediana-de-tres hace el peor caso casi imposible, y su velocidad media y uso de caché superan a los demás O(n log n).
¿Es estable?
No — la partición intercambia elementos distantes.

Otros algoritmos