Ordenamiento 1: burbuja, selección e inserción

El ordenamiento por selección hace exactamente 45 comparaciones con cualquier lista de 10 valores, ya empiece desordenada o ya en orden.

Poner las cosas en orden

Ordenar significa reacomodar una lista para que sus valores vayan del más pequeño al más grande (o por nombre, fecha, precio, cualquier orden que se pueda comparar). Es uno de los trabajos más comunes de una computadora: los contactos de un celular, los resultados de búsqueda clasificados por relevancia, una columna de hoja de cálculo ordenada por fecha. Ordenar también facilita otros trabajos. Como mostró la unidad anterior, en una lista ordenada se puede buscar con búsqueda binaria, y los duplicados de una lista ordenada quedan uno al lado del otro.

Esta unidad trata tres métodos sencillos. Los tres funcionan comparando dos valores a la vez y moviendo valores dentro de la misma lista. Son cortos de escribir y fáciles de seguir, y los tres se vuelven mucho más lentos con listas largas. Ver por qué se hacen lentos es la mejor preparación para los métodos más rápidos de la unidad siguiente. Todo el tiempo contamos dos cosas: comparaciones (preguntar "¿este valor es mayor que ese?") e intercambios (cambiar de lugar dos valores).

Ordenamiento de burbuja: intercambiar vecinos desordenados

El ordenamiento de burbuja recorre la lista comparando cada par de vecinos. Cuando el de la izquierda es mayor, los intercambia. Después de una pasada completa, el valor más grande ha sido llevado paso a paso hasta el extremo derecho, como una burbuja que sube, y ya nunca tiene que moverse. La pasada siguiente puede terminar un lugar antes. Una mejora común es fijarse en si hay una pasada sin ningún intercambio: eso significa que todo ya está en orden, así que el ordenamiento puede terminar antes.

Síguelo con la lista [5, 1, 4, 2, 8]. La primera pasada compara 5 y 1 (intercambio), 5 y 4 (intercambio), 5 y 2 (intercambio), 5 y 8 (se dejan): la lista queda [1, 4, 2, 5, 8] y el 8 está en su lugar. La segunda pasada compara 1 y 4, 4 y 2 (intercambio), 4 y 5, y da [1, 2, 4, 5, 8]. La tercera pasada compara 1 y 2, luego 2 y 4, no hace ningún intercambio y termina. Total: 4 + 3 + 2 = 9 comparaciones y 4 intercambios.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // intercambio
        swapped = true;
      }
    }
    if (!swapped) break;  // ya está ordenada
  }
  return a;
}

Ordenamiento por selección: buscar el menor y ponerlo a continuación

El ordenamiento por selección funciona como mucha gente ordena una mano de cartas. Recorre toda la lista buscando el valor más pequeño y lo intercambia a la primera posición. Luego recorre el resto buscando el menor de los que quedan y lo intercambia a la segunda posición, y así sucesivamente. Con [5, 1, 4, 2, 8], el primer recorrido encuentra el 1 y lo intercambia con el 5; el segundo encuentra el 2 y lo intercambia con el 5; los dos últimos encuentran el 4 y el 5 ya en su lugar. Son solo 2 intercambios, pero los recorridos siguen comparando 4 + 3 + 2 + 1 = 10 veces.

El ordenamiento por selección nunca termina antes. Incluso con una lista que ya está ordenada, tiene que revisar todos los valores restantes para estar seguro de que tiene el menor. Para n valores, las comparaciones siempre suman (n − 1) + (n − 2) + … + 1 = n(n − 1)/2. Para 10 valores son 45; para 100 valores, 4950; para 1000 valores, 499 500. Su punto fuerte es el número pequeño de intercambios: como máximo n − 1, lo que importa cuando mover un valor es caro.

Ordenamiento por inserción: deslizar cada valor nuevo a su lugar

El ordenamiento por inserción mantiene ordenada la parte izquierda de la lista y la hace crecer de un valor en un valor. Toma el valor siguiente y lo mueve a la izquierda, intercambiándolo con su vecino, hasta que el vecino no sea mayor. Entonces ese valor ya está en su lugar entre los ordenados. En una lista que ya está casi en orden, cada valor nuevo se mueve apenas uno o dos pasos, así que ahí el ordenamiento por inserción es muy rápido. Con [5, 1, 4, 2, 8] hace 7 comparaciones y 4 intercambios.

Contar los intercambios: inversiones

Hay una forma elegante de predecir cuántos intercambios necesitan el ordenamiento de burbuja y el de inserción. Cuenta las inversiones: pares de valores que están en el orden equivocado uno respecto del otro. En [5, 1, 4, 2, 8] las inversiones son (5, 1), (5, 4), (5, 2) y (4, 2), cuatro en total. Cada intercambio de dos vecinos desordenados corrige exactamente una inversión y no crea ninguna, así que los dos métodos hacen exactamente 4 intercambios. Una lista invertida de n valores tiene todos los pares invertidos, n(n − 1)/2 inversiones, que es el peor caso.

Cada celda da comparaciones / intercambios. La lista de ejemplo es [5, 1, 4, 2, 8]. El ordenamiento de burbuja de aquí es la versión que termina después de una pasada sin intercambios.

Los tres métodos comparten la misma debilidad. En el peor caso, cada uno compara más o menos todos los pares de valores, unas n²/2 comparaciones. Duplica la lista y el trabajo se multiplica por cuatro. Una lista diez veces más larga significa cien veces más trabajo. Con unas cuantas decenas de valores casi no importa; con un millón no hay nada que hacer, y la unidad siguiente muestra cómo hacerlo muchísimo mejor.