Insercion Tipo De Ordenamiento

^

1. Descripción.

^

Este algoritmo también es bastante sencillo. ¿Has jugado cartas?. ¿Cómo las vas ordenando cuando las recibes? Yo lo hago de esta manera: tomo la primera y la coloco en mi mano. Luego tomo la segunda y la comparo con la que tengo: si es mayor, la pongo a la derecha, y si es menor a la izquierda (también me fijo en el color, pero omitiré esa parte para concentrarme en la idea principal). Después tomo la tercera y la comparo con las que tengo en la mano, desplazándola hasta que quede en su posición final. Continúo haciendo esto, insertando cada carta en la posición que le corresponde, hasta que las tengo todas en orden. ¿Lo haces así tu también? Bueno, pues si es así entonces comprenderás fácilmente este algoritmo, porque es el mismo concepto.

Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.

2. Pseudocódigo en C.

^

Tabla de variables

Nombre Tipo Uso

lista Cualquiera Lista a ordenar

TAM Constante Entera Tamaño de la lista

i Entero Contador

j Entero Contador

temp El mismo que los elementos de la lista Para realizar los intercambios

1. for (i=1; i<TAM; i++)

2. temp = lista[i];

3. j = i - 1;

4. while ( (lista[j] > temp) && (j >= 0) )

5. lista[j+1] = lista[j];

6. j--;

7. lista[j+1] = temp;

Nota: Observa que en cada iteración del ciclo externo los elementos 0 a i forman una lista ordenada.

3. Un ejemplo

^

¿Te acuerdas de nuestra famosa lista?

4 - 3 - 5 - 2 - 1

temp toma el valor del segundo elemento, 3. La primera carta es el 4. Ahora comparamos: 3 es menor que 4. Luego desplazamos el 4 una posición a la derecha y después copiamos

...