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