Carrera de algoritmos de ordenamiento

sigue paso a paso dos algoritmos compitiendo con la misma entrada — comparaciones, intercambios, complejidad

Cargando simulación interactiva...

el Big-O no es toda la historia 🖖

El ordenamiento de burbuja hace exactamente n(n−1)/2 comparaciones en el peor caso — unas 2000 para n=64. Cada pasada debe recorrer toda la región restante sin ordenar, sin salida anticipada. La partición de quicksort coloca el pivote en su posición final y divide el problema en dos subproblemas; cada nivel de recursión realiza O(n) trabajo a lo largo de O(log n) niveles, dando O(n log n) en total. La trampa: si el pivote siempre cae en un extremo — por ejemplo, entrada ordenada con el último elemento como pivote — la partición degenera en n subproblemas de tamaño n−1, n−2, ... que suman O(n²). El pivote del elemento central usado aquí evita eso, por lo que la entrada invertida se mantiene rápida. Los valores con pocos únicos son el caso interesante: cuando muchos elementos igualan al pivote, intercambiar valores idénticos desperdicia trabajo y puede acercarse a lo cuadrático. El Big-O te indica la clase de crecimiento; las constantes, la sensibilidad a la entrada y el comportamiento de la caché determinan qué algoritmo realmente conviene usar.

Por qué cuenta pasos, no segundos 🖖

Esta carrera puntúa cada algoritmo contando comparaciones e intercambios, no con un cronómetro. El tiempo real depende de tu CPU, del navegador y de qué más se esté ejecutando, así que el mismo código puede parecer rápido o lento en distintas máquinas. Contar operaciones da una medida limpia y reproducible del trabajo realmente hecho: la misma entrada siempre produce los mismos recuentos, lo que te permite comparar los algoritmos en sí y no el hardware.

Quicksort nació traduciendo ruso 🖖

Tony Hoare inventó Quicksort en 1959, siendo estudiante visitante en Moscú, mientras trabajaba en un proyecto de traducción automática. Para buscar una frase rusa en el diccionario, primero necesitaba ordenar sus palabras alfabéticamente, y el método habitual era desesperadamente lento. Su solución, particionar en torno a un pivote, se convirtió en uno de los algoritmos más usados de la historia. Las barras que compiten aquí provienen de un problema lingüístico, no informático.

Problema resuelto al detalle

Predicción exacta del recuento de intercambios de la ordenación de burbuja en 64 elementos invertidos 7 pasos
Ejecute la carrera en el preajuste invertido — 64 elementos, los mayores primero. Prediga el número de intercambios de la ordenación por burbuja exactamente, no su orden de crecimiento; luego diga qué impide que cualquier algoritmo de intercambio de vecinos lo supere.
1. Una inversión es un par que se encuentra en un orden relativo incorrecto. La entrada invertida es el caso extremo: para cada i < j el elemento anterior es el mayor, de modo que cada par está invertido y el recuento abarca a todos ellos. Obtener este número antes de que nada se mueva resulta ser todo el problema.
  
  $I = # {(i, j) : i < j, a_{i} > a_{j}} = (2 64) = \frac{64 \times 63}{2} = 2, 016$
2. La ordenación por burbuja solo intercambia elementos adyacentes, y únicamente cuando están desordenados. Dicho intercambio corrige ese par en concreto y no altera ningún otro, ya que los dos elementos que se mueven mantienen la misma relación con todo lo que queda fuera de ellos. Un intercambio, una inversión: nunca dos, nunca ninguna.
  
  $a_{k} > a_{k + 1} ⟶ I \mapsto I - 1$
3. Estar ordenado significa cero inversiones. Comenzar en 2.016 y eliminar exactamente una por intercambio no deja margen de maniobra: el número de intercambios resulta forzado. El panel muestra 2.016 intercambios, y eso es una identidad más que una cota del peor caso.
  
  $S = I_{0} - 0 = 2, 016$
4. Las comparaciones son un recuento independiente que aquí resulta coincidir. La pasada i recorre j = 0 … 62 − i, por lo que el total es 63 + 62 + ⋯ + 1, los mismos 2.016 que muestra la fila peor caso de burbuja n(n−1)/2. Que los recuentos sean iguales significa que cada una de las comparaciones encontró una inversión, que es lo que significa "peor caso" aquí. El contador bajo el título de cada panel cuenta un paso por comparación más uno por intercambio, de modo que marca paso 0 / 4.032 antes de empezar, y el botón › consume exactamente uno de esos pasos por clic. La O(n²) junto al título es una etiqueta, no un recuento.
  
  $C = i = 0 \sum 62 (63 - i) = 63 + 62 + \dots + 1 = \frac{63 \times 64}{2} = 2, 016 = \frac{n ( n - 1 )}{2}, C + S = 4, 032$
5. Ahora generalice el paso 2, porque esto es lo que aprovecha quicksort. Intercambiar dos elementos separados d posiciones deja intacto en total todo par formado con un elemento fuera del intervalo: dicho elemento se vuelve a comparar con el otro extremo, las dos comparaciones se intercambian y su contribución no cambia. Lo que puede cambiar es el propio par, más los 2(d − 1) pares que cada extremo forma con las d − 1 entradas intermedias. Como máximo pueden eliminarse 2d − 1 inversiones por intercambio, y fijar d = 1 recupera la única inversión del paso 2.
  
  $1 + 2 (d - 1) = 2 d - 1 (d = 1 \Rightarrow 1)$
6. La primera partición de quicksort toma el elemento central como pivote, a[31] = 33, e intercambia (0, 63), (1, 62), … , (31, 32): 32 intercambios a distancias 63, 61, … , 1. El paso 5 limita su efecto combinado a 2.016 inversiones, y esa única pasada deja el vector completamente ordenado, por lo que se eliminaron exactamente 2.016. El límite se alcanza con igualdad: cada uno de los 32 intercambios logró su propio máximo.
  
  $p = a_{31} = 33, d = 63, 61, \dots, 1 : m = 1 \sum 32 (2 (2 m - 1) - 1) = m = 1 \sum 32 (4 m - 3) = 2, 112 - 96 = 2, 016$
7. Por tanto, los dos algoritmos no compiten en ingenio, sino en alcance. Las 334 comparaciones y 64 intercambios impresos de quicksort suman los 398 de su contador, y solo 32 de esos intercambios mueven algo, siendo los otros 32 el pivote intercambiado consigo mismo en tramos que ya están ordenados. Sus 334 comparaciones también quedan por debajo de la referencia impresa n·log₂n de 384, porque el elemento central de una secuencia invertida es su mediana, por lo que cada división es equitativa.
  
  $334 + 64 = 398, 64 lo g_{2} 64 = 384, \frac{2 , 016}{32} = 63$
Respuesta

2.016 intercambios y 2.016 comparaciones: los 4.032 pasos del contador. Y 2.016 no es un dato propio de la ordenación por burbuja: es una cota inferior para toda una familia. Cualquier algoritmo limitado a intercambiar elementos adyacentes —ordenación por inserción, ordenación de coctelera, ordenación gnomo o uno que nadie haya escrito aún— elimina como máximo una inversión por intercambio según el paso 2, por lo que todos ellos necesitan al menos 2.016 intercambios con esta entrada y todos ellos son Ω(n²) en datos invertidos debido al modelo en el que trabajan, no porque sean torpes. Quicksort escapa de esa cota inferior al permitírsele mover un elemento 63 posiciones a la vez: 2.016 inversiones eliminadas mediante 32 intercambios reales suponen 63 inversiones por intercambio, y el paso 5 afirma que eso es lo máximo que cualquier intercambio individual a esa distancia podría haber logrado. El panel no calcula ni el recuento de inversiones ni la cota inferior que este implica.

$S \geq I_{0} = (2 64) = 2, 016 (d = 1), \frac{I _{0}}{32} = 63$

Ruta de aprendizaje

Contar trabajo, no segundos

Lleva a recursion-tree

Referencias (1)

Insight block 3 — quicksort as its author published it: C. A. R. Hoare, "Quicksort." The Computer Journal 5(1), 10–16, 1962. The algorithm first appeared the year before as C. A. R. Hoare, "Algorithm 64: Quicksort", Communications of the ACM 4(7), 321, 1961.

Por el equipo de 42Math · Actualizado 2026-05-27

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

Problemas de ejemplo

casi ordenado - La distribución de la entrada cambia la eficiencia relativa de los algoritmos.
invertido - El ordenamiento de burbuja efectúa 2.016 comparaciones y 2.016 intercambios: todas y cada una de las comparaciones encuentran a su par desordenado, porque invertir 64 elementos invierte los 2.016 pares de golpe. Quicksort lo soluciona con 334 comparaciones y 64 intercambios. Queda así por debajo de su referencia n·log₂n de 384, dado que el elemento central de un arreglo invertido es exactamente la mediana en cada partición.
pocos valores únicos - Ochenta elementos tomados de solo ocho valores distintos. Quicksort necesita 534 comparaciones frente a su referencia n·log₂n de 506. Es la única de las tres configuraciones en la que termina por encima de su propia línea: los elementos iguales al pivote se intercambian sin obtener ventaja alguna. El ordenamiento de burbuja sigue realizando sus 3.160 comparaciones fijas y apenas 1.330 intercambios, porque muchos pares contiguos ya coinciden.