← Volver a los ejercicios

insercion: en qué posición queda el elemento que se inserta

iSort ordena la cola y después mete la cabeza en su lugar, así que ordenar List(8, 4, 11, 2) son cuatro llamadas a insertar, cada una sobre una lista que ya está ordenada. Las cuatro corren de adentro hacia afuera: primero el 2 sobre la lista vacía, de último el 8 sobre los tres que quedaron. En cada ronda diga la posición en que va a quedar el elemento antes de correr la ejecución, y después compruébela paso por paso.

1. Las cuatro inserciones

El árbol de llamadas de iSort(List(8, 4, 11, 2)). La línea resaltada es la inserción de esta ronda; los resultados aparecen cuando la predicción queda acertada.

def iSort(xs: List[Int]): List[Int] = xs match {
  case Nil     => Nil
  case y :: ys => insertar(y, iSort(ys))
}

2. La predicción

Ronda en curso: insertar(2, List()). La lista que recibe ya está ordenada, así que el elemento tiene un solo lugar donde cabe. Las posiciones van de 1 a 1, contando desde la izquierda.

3. La ejecución de insertar

paso 0 de 0
■ la cabeza y que se está comparando ■ el elemento x ya colocado ■ las cabezas que la condición dejó atrás
elemento que se inserta: –
lo que devuelve la llamada: –

Los botones quedan disponibles cuando la predicción de la ronda esté acertada. El contador de cada línea dice cuántas veces se evaluó: la línea 4 cuenta las cabezas que el elemento dejó atrás y la 3, las comparaciones.

4. Lo que se lleva de aquí

iSort(List(8, 4, 11, 2)) devuelve –. Ninguna de las cuatro llamadas a insertar comparó nada con el resto de la lista original: cada una recibió una lista ya ordenada y solo tuvo que encontrar el primer elemento que no fuera menor que el suyo. Esa es la condición que hace funcionar al algoritmo, y iSort la garantiza porque ordena la cola antes de insertar la cabeza.

La predicción de cada ronda se puede dar sin correr nada: la posición es el número de elementos menores que x, más uno. La ejecución llega al mismo lugar bajando por la lista, y lo que cuesta es precisamente esa bajada. El contador de la línea 4 dice cuántas cabezas se saltaron en la ronda, y el peor caso es insertar el mayor de todos, que recorre la lista completa.

El x :: xs del caso que coloca no copia la lista que recibió: crea el nodo de x apuntando a ella y nada más. Lo que sí se reconstruye son los nodos de las cabezas que se saltaron, uno por cada y :: insertar(x, ys) que quedó pendiente.