ORDENACION POR INSERCION
La ordenación por inserción es un algoritmo eficiente para ordenar pequeñas cantidades de elementos. La ordenación por inserción funciona de la misma manera que la mayoria de las personas ordena una mano de barajas. Se comienza con una la mano izquierda vacia, y la mano de barajas, boca abajo en la mesa. Entonces vamos recogiendo una a una las barajas de la mesa y las insertamos en la posición correcta en la mano izquierda. Para encontrar la posición correcta, comparamos la nueva baraja con las que tenemos en la mano, de derecha a izquierda. En todo momento, las barajas que tenemos en la mano izquierda se encuentran ordenadas.
A continuación presentamos un pseudocódigo para implementar el ordenamiento por inserción, nuestro procedimiento toma como entrada un arreglo A[1..n] que contiene una secuencia de elementos de longitud n.
ORDENAMIENTO-INSERCION (A)
1 desde j:=2 hasta Longitud(A) haz inicio
2 llave:=A[j]
3 i:=j - 1
4 mientras (i > 0) y (A[i] > llave) haz inicio
5 A[i + 1] := A[i]
6 i:=i - 1
7 fin-mientras
8 A[i + 1]:=llave
9 fin-desde
El código funciona de la siguiente manera, inicialmente tenemos el arreglo A con los elementos desordenados. Como se explico en el primer párrafo la ordenación por inserción busca siempre tener ordenada la parte izquierda del arreglo, e ir tomando uno a uno los elementos del lado derecho para insertarlos en su posición.
En la línea 1 del algoritmo, tenemos un ciclo que irá moviendo j desde 2 hasta el numero de elementos de A en este caso denotado por Longitud(A). ¿Por qué desde 2? Recordemos que al inicio tenemos el lado izquierdo vacio y tomamos elementos del lado derecho para insertarlos en su posición correcta. Sin embargo la posición del primer elemento es trivial, ya que un conjunto de 1 elemento siempre está ordenado! Por lo tanto no tiene caso buscar la posición del primer elemento.
Para cada índice, a partir del 2, el elemento que se está insertando se compara con los elementos ya ordenados de derecha a izquierda con el ciclo mientras de la línea 4. Aqui pueden suceder dos cosas, si el elemento que se está insertando es menor que el elemento ordenado, entonces el elemento ordenado se recorre un lugar hacia la derecha (asignación de la línea 5). Si el elemento que se está insertando es mayor o igual, entonces se coloca en ese lugar (asignación de la línea 8). Una vez que se encontro la posición del elemento, se avanza al siguiente índice. Cuando j sea igual a Longitud(A) + 1 el algoritmo termina y tenemos que los elementos en A están ordenados.
Para que puedas apreciar mejor el funcionamiento de este algoritmo te recomendamos seguirlo en papel con un arreglo de unos 5 números.
Revisemos ahora el costo computacional de ordenar por medio de la técnica de inserción, para esto revisemos de nuevo nuestro código
ORDENAMIENTO-INSERCION (A)
1 desde j:=2 hasta Longitud(A) haz inicio
2 llave:=A[j]
3 i:=j - 1
4 mientras (i > 0) y (A[i] > llave) haz inicio
5 A[i + 1] := A[i]
6 i:=i - 1
7 fin-mientras
8 A[i + 1]:=llave
9 fin-desde
costo
c1
c2
c3
c4
c5
c6
0
c7
0
#veces que se ejecuta
n
n-1
n-1
Sum(2,n,tj)
Sum(2,n,tj - 1)
Sum(2,n,tj - 1)
n-1
Para este ejemplo usamos la notación SUM(a,b,f(j)), que significa, la sumatoria desde j=a, hasta j=b de la función f(j).
Para analizar un algoritmo, los pasos a seguir son basicamente 2, el primer paso es asignar un costo computacional a cada línea del código, este costo computacional, que en la tabla esta representado por c1, c2, ... , c7, está determinada por la velocidad de la máquina y la naturaleza de la función, por ejemplo una suma requiere menos tiempo que una multiplicación. Determinar este costo no es sencillo, ya que varía de máquina a máquina y de arquitectura a arquitectura, por lo que muy rara vez se hará de manera exacta, sin embargo vale la pena tener presente que existe. El segundo paso es ver cuantas veces va a ser ejecutada cada línea de código, y está es la parte que más nos interesa, por lo que la analizaremos paso a paso para nuestro ejemplo.
* La línea 1 se ejecuta una vez por cada índice del arreglo, esto es desde 2 hasta Longitud(A)+1 por lo que en total será ejecutado n veces, donde n es el número total de elementos del arreglo.
* Las líneas 2,3 y 8 se ejecutan el mismo número de veces que la 1 menos uno. Hay que recordar que el ciclo desde (for), hace una última revisión para el caso en el que ya no cumple con la condición. Por lo tanto estas líneas se ejecutan n-1 veces.
* Entramos ahora a las líneas 4, 5 y 6 del algoritmo, estas líneas son las que se encargan de buscar la posición correcta del elemento j. Si recordamos el funcionamiento del algoritmo, para cada índice j se recorre la parte del arreglo ordenada de derecha a izquierda buscando su posición, en el momento en que se encuentra su posición se termina el ciclo mientras. Por lo tanto la función f(j) dependerá de cuantas comparaciones se tengan que hacer para encontrar la posición del elemento j.
Como puede verse del último punto del analisis, la cantidad de veces que se ejecutan las líneas 4, 5 y 6 no es fijo, sino que depende de la entrada. En la mayoría de los algoritmos, el tiempo de ejecución dependerá de la entrada, por lo que la mayoria de las veces se puede hacer un análisis de peor caso y análisis del caso promedio. En la teoría de la computación lo más importante es el análisis del peor caso, este análisis busca cual sería el tiempo de corrida del algoritmo con la peor entrada posible. Al obtener este tiempo, nos damos una idea de que es lo más que puede llegar a tardar nuestro algoritmo.
Para el caso de la ordenación por inserción, puede verse que el peor caso posible es que la entrada estuviera ordenada en orden inverso, es decir, de grande a chico y nosotros lo queremos ordenar de chico a grande, ya que en este caso, las líneas 4, 5, 6 se ejecutarían j-1 veces para cada índice. En este caso el tiempo total de corrida sería:
T=c1*n + (c2 + c3 + c7)*(n-1) + c4*SUM(2,n,j) + (c5 + c6)*SUM(2,n,j-1)
Sabemos que: SUM(2,n,j)=( n2 + n)/2 - 1 y que SUM(2,n,j-1)=( n2 - n)/2 por lo que si sustituimos tenemos que el tiempo total de corrida del peor caso seria:
T=c1*n + (c2 + c3 + c7)*(n-1) + c4*(( n2 + n)/2 - 1 ) + (c5 + c6)*(( n2 - n)/2 )
Para facilitar el análisis, consideremos que todas las constantes tienen el mismo valor, es decir c1=c2=c3=c4=c5=c6=c7=c entonces nos queda que
T=c*n + (3c)*(n-1) + c*(( n2 + n)/2 - 1 ) + (2c)*(( n2 - n)/2 )
T=1.5cn2 + 3.5cn - 4c
Donde se puede apreciar claramente que el tiempo de corrida del ordenamiento por inserción en el peor caso es una función cuadratica de n.
Cuando se analizan algoritmos, en general sólo importa el termino de la función que crece más rápido, y se eliminan las constantes, por lo tanto en el caso del ordenamiento por inserción, el término que crece más rápido es el término cuadrático, por lo que se dice que el ordenamiento por inserción tiene una complejidad de O(n2).
Es conveniente que revises todo este análisis una y otra vez hasta que lo entiendas perfectamente, ya que el analizar la complejidad de tus algoritmos es muy importante en las ciencias de la computación y por lo tanto en la olimpiada.
Usuarios que han visto este tema también han visto...
- Cómo ganar clientes en la web
- No se habla de usabilidad
- Trampas en ofertas de trabajo desde casa
- Buscador interno
- Consejos para tu Blog
- Versión imprimible de este documento
- Enviar por e-mail este documento
