Burbuja, inserción y selección

Nadie ordena un millón de elementos con burbuja. Pero los tres algoritmos cuadráticos son el lugar donde se ven, sin ruido, las propiedades con las que después se comparan los ordenamientos serios: cuánta memoria extra usan, si respetan el orden previo de los empates y si aprovechan que los datos ya vengan casi ordenados.

In situ, estable y adaptativo

Antes de los algoritmos conviene fijar el vocabulario. Un ordenamiento es in situ si usa memoria extra constante, sin copiar el arreglo. Es estable si dos elementos con la misma clave quedan en el orden en que estaban.

La estabilidad importa más de lo que parece: permite ordenar por un criterio y después por otro sin perder el primero, que es cómo funciona ordenar una tabla por varias columnas. Y es adaptable si tarda menos cuando la entrada ya está parcialmente ordenada.

Selección: siempre lo mismo, pase lo que pase

Selección busca el mínimo del tramo sin ordenar y lo intercambia con la primera posición de ese tramo. Repite hasta terminar. Siempre hace $\Theta(n^2)$ comparaciones, tanto si el arreglo viene ordenado como si viene al revés: no es adaptable.

Lo que sí tiene es la menor cantidad de escrituras posible entre estos tres: exactamente $n-1$ intercambios. Eso lo hace razonable cuando escribir es carísimo comparado con comparar. El intercambio a distancia rompe la estabilidad.

Inserción: la que sirve de verdad

Inserción toma cada elemento y lo desliza hacia atrás hasta su lugar dentro de la parte ya ordenada, como quien acomoda cartas en la mano. Es estable, in situ y, sobre todo, adaptable: si cada elemento está cerca de su posición final, cada inserción recorre poco.

En el mejor caso —arreglo ya ordenado— hace $\Theta(n)$ comparaciones y ningún movimiento. Por eso las implementaciones reales de quicksort y mergesort cortan la recursión en tramos chicos y los terminan con inserción.

Burbuja, que se enseña y no se usa

Burbuja compara pares adyacentes y los intercambia si están fuera de orden, pasada tras pasada, hasta que una pasada no cambie nada. Es estable e in situ, y con la bandera de corte temprano detecta en $\Theta(n)$ que el arreglo ya estaba ordenado.

Fuera de ese caso es el peor de los tres: hace muchos más intercambios que inserción para el mismo trabajo, porque sólo mueve elementos de a una posición. Su valor es didáctico.

Por qué los tres son cuadráticos

Los tres comparten la misma razón de fondo para ser cuadráticos: sólo comparan e intercambian elementos vecinos o mueven de a un lugar por paso. Cada intercambio de adyacentes elimina exactamente una inversión —un par que está en orden invertido—, y un arreglo puede tener hasta

inversiones. Ningún algoritmo que trabaje así puede bajar de $\Theta(n^2)$ en el peor caso. Los ordenamientos rápidos, justamente, mueven elementos a distancia.

El caso real donde todavía ganan

Con todo, hay un caso real: arreglos chicos. La complejidad asintótica esconde constantes, y las de inserción son muy bajas —sin recursión, sin memoria extra, con acceso secuencial que la caché favorece—. Para unas pocas decenas de elementos le gana a mergesort.

El otro caso es el de datos que llegan casi ordenados o de a uno, en vivo: inserción mantiene la colección ordenada con trabajo proporcional al desorden real.

Inserción, escrita

De los tres cuadráticos, el único que vale la pena escribir bien es el de inserción, porque es el que sigue vivo adentro de las bibliotecas.

const insertionSort = (values: number[]): number[] => {
  for (let index = 1; index < values.length; index += 1) {
    const current = values[index]!;
    let position = index - 1;

    // correr hacia la derecha todo lo que sea mayor que current
    while (position >= 0 && values[position]! > current) {
      values[position + 1] = values[position]!;
      position -= 1;
    }

    values[position + 1] = current;
  }

  return values;
};

Dos detalles que no son cosméticos. El primero: el ciclo interno mueve, no intercambia. Intercambiar son tres asignaciones por paso y correr es una, y sobre un arreglo casi ordenado esa diferencia se nota. El segundo: la comparación es > y no >=, y eso es lo que lo hace estable —dos elementos iguales nunca se cruzan—, que es la propiedad por la que sigue en uso.

Por qué siguen existiendo

Cierre

Selección minimiza escrituras y no se adapta; burbuja es estable y detecta lo ordenado, pero mueve de más; inserción es estable, adaptable y la única que sobrevive en el código real, como caso base de los algoritmos $O(n\log n)$. Las tres propiedades —in situ, estable, adaptable— son el marco con el que se leen todos los ordenamientos.