7.1 Ordenamiento 161 Si (V[j] > V[j+1]) entonces aux V[j] V[j] V[j+1] ! intercambiar V[j+1] aux fin si fin para fin para Repetir Para i 1, n Escribir (V[i]) fin para fin 7.1.3 Ordenamiento por inserción Este método, que recuerda la forma en que se ordena un mazo de naipes, comienza con- siderando que la primera componente del arreglo ya está ordenada, y toma la siguiente para determinar donde insertarla en la parte ordenada del arreglo (la izquierda). En ese momento se presentan tres posibilidades: 1. Si la que se está intentando insertar es menor que la primera, se la coloca en primer lugar, y se desplazan las restantes hacia la derecha. 2. Si la que se está intentando insertar es mayor que la última de la parte ordenada, queda en su misma posición, conformando la última del subconjunto ordenado. 3. Si la que se está intentando insertar no cumple ninguna de las dos condiciones anteriores, se la debe colocar en un lugar intermedio, desplazando las mayores a ella hacia la derecha. Por ejemplo, para ordenar en forma ascendente el arreglo: 8 6 -1 2 0 3 -4 3 es decir, queda 6 8 | -1 2 0 3 -4 3 donde las dos primeras componentes aparecen en orden creciente.Ahora se considera la tercera componente, y recorriendo las componentes de la izquierda, se la “inserta” delante de la primera componente que sea menor, o bien al principio. En el ejemplo habría que insertar el –1 al principio, y desplazar el 6 y el 8. Así: -1 6 8 | 2 0 3 -4 3 las tres primeras componentes quedan en orden creciente. Al tomar la cuarta componente, 2 , y recorrer el arreglo hacia la izquierda, vemos que –1 < 2,
162 Ordenamiento, Búsqueda e Intercalación luego insertamos 2 delante de 6 y desplazamos 6 y 8. obteniendo: -1 2 6 8 | 0 3 -4 3 Como observación: si la componente considerada es ya mayor que la anterior (p.ej: si en el paso anterior fuera 12 en vez de 2) simplemente se la deja como está, y se pasa a considerar la componente que sigue (el 0 en este caso). -1 6 8 12 0 3 -4 3 Volviendo al arreglo original, ya nos damos cuenta, entonces, cómo serán los pasos poste- riores, insertando las componentes restantes hasta la n -1 0 2 6 8 | 3 -4 3 -1 0 2 3 6 8 | -4 3 -4 -1 0 2 3 6 8 | 3 -4 -1 0 2 3 3 6 8 Veamos la implementación de un algoritmo para realizar este proceso. AlgoritmoInserción entero n, i, j real V[10000], aux logico cond inicio Leer (n) !suponemos 0<n<=10000 Repetir Para i 1, n leer(V[i]) finpara ! Comienza el ordenamiento Repetir Para i 2, n ! V[i] componente a insertar x V[i] ! almacenarla para no perderla j i – 1 ! posición componente anterior cond verdadero ! se puede comparar para insertar Repetir Mientras (cond y j>0) si x<V[j] entonces V[j+1] V[j] ! desplazar un lugar j j–1 sino cond falso
Created with BuildVu