← Volver a los ejercicios

Ordenar insertando

Insertion sort sobre 6 4 8 2 9 5. En cada vuelta la clave es a[j] y se corre a la derecha todo lo que sea mayor que ella.

1. Los corrimientos de cada vuelta

¿Cuántos corrimientos hace el ciclo interno en las vueltas j = 1, 2, 3, 4, 5, y cuántos suman?

por vuelta:

¿Cuántos corrimientos suman en total?

2. El arreglo en dos cortes

¿Cómo queda el arreglo al terminar la vuelta j = 3 y al terminar la vuelta j = 5?

tras j = 3: tras j = 5:

3. La traza completa

jclavecorrimientosel arreglo al terminar la vuelta

4. La entrada más cara

Con la misma cantidad de elementos, ¿cuántos corrimientos hace insertion sort sobre 9 8 6 5 4 2?