Cristo Jesus Alanis Barrera

AL12508835

Evidencia de Aprendizaje. Presentación de Resultados

Computación I

Lic. en Matemáticas

Instrucciones: Resuelve los siguientes ejercicios que se presentan a continuación

a. Calcula los tiempos de ejecución en el mejor, peor, y caso promedio del programa siguiente:

Constante n = un número entero (int)Type vector = Array [1..n] de int

Programa Algoritmo1(VAR a:vector)int i,jint temp

BEGIN For i=1 to n-1 do (* 1 *) For j=n to i+1 by -1 do (* 2 *) If a[j-1]>a[j] then (* 3 *) temp=a[j-1] (* 4 *) a[j-1]=a[j] (* 5 *) a[j]=temp (* 6 *) END IF (* 7 *) END FOR (* 8 *) END FOR (* 9 *)END Algoritmo1;

Como primer paso estableceremos el número de operaciones elementales (OPEL) que se ejecutan en el algoritmo:

Instrucción OPELFor i=1 to n-1 do

For j=n to i+1 by -1 doIf a[j-1]>a[j] then 3

temp=a[j-1] 2a[j-1]=a[j] 2a[j]=temp 1

END IFEND FOR 2

END FOR 2

La cantidad de operaciones por cada iteración interior, en caso de que a[j-1] > a[j] está dada por:

T(n) = 3 + 2 + 2 + 1 + 2 = 10

Para el caso de que no se cumpla la condición a[j-1] > a[j]

T(n) = 3 + 2 = 5 Cabe hacer mención que en todos los casos las veces que se ejecutan ambas iteraciones es igual, lo único que difiere es la cantidad que se ejecutan las asignaciones dentro del bucle if, lo que hace que se ejecuten n-1 veces el ciclo interior, y n-1 veces el ciclo interior, o un total de n²-2n+1 veces ambos ciclos.

En cuanto al tiempo de ejecución se tiene que se ejecutan dos OPEL en el ciclo exterior, lo que hace para el mejor de los casos

T(n) = 2 (n-1) * 5 (n-1) = 10n²-20n+10

Y para el peor de los casos en que se ejecutarían los ciclos if para todos los casos:

T(n) = 2 (n-1) * 10 (n-1) = 20n²-40n+20

El cual toma el doble de tiempo que del mejor de los casos, lo cual podemos deducir que para el caso promedio tendríamos

T(n) = 15n²-15n+15

Dependiendo de la cantidad de elementos del arreglo (n)

b. Investiga acerca del algoritmo de Ordenamiento por Inserción (Insertion Sort).

i. Escribe el procedimiento para que ordene de forma creciente.ii. Construye su representación en pseudocódigoiii. Construye su representación en diagrama de flujoiv. Programa el código en lenguaje C o Java, y reporta los resultados

Este método de ordenación itera un elemento por cada repetición moviéndolo a una posición ordenada en una lista creciente. Por cada iteración, el algoritmo remueve un elemento de los datos de entrada, encuentra la localidad que le pertenece dentro de una lista ordenada de elementos previamente iterados y lo inserta ahí. Se repite hasta que no existan elementos de entrada.

Cabe hacer mención que es común que la ordenación se realiza en el mismo arreglo de entrada, esto para evitar uso adicional de memoria; la ordenación se realiza iterando el arreglo de entrada, haciendo que la lista ordenada crezca al inicio de el. En cada posición del arreglo, se verifica el valor de esa posición contra el valor más alto de la lista ya ordenada. Si es mayor, deja el elemento en lugar y se mueve al siguiente. Si es menor, encuentra la posición correcta dentro de la lista ordenada, y mueve todos los valores más grandes para hacer espacio para insertar el valor en la posición correcta.

Para el pseudocódigo, por simplicidad se omite la llamada desde una rutina main, llenado del arreglo, y mostrar el arreglo ordenado.

1. Inicio de rutina de ordenación (parámetros: variable arreglo con valores a ordenar pasado por referencia)

2. Declara variables índice indice, indice_previo, cantidad_elementos y valor_actualcantidad_elementos <- cantidad de elementos en arreglo

indice <- 1for indice < cantidad_elementos - 1valor_actual = arreglo[indice]indice_previo <- indice – 1while indice_previo >= 0 and arreglo[indice_previo] > valor_actualarreglo[indice] <- arreglo[indice_previo]indice_previo <- indice_previo – 1

end-whilearreglo[indice] <- valor

end-for3. retorna a función principal4. Fin

Pseudocódigo de algoritmo de ordenamiento por inserción

Diagrama de flujo de algoritmo de ordenamiento por inserción

Implementación en C de algoritmo de ordenamiento por inserción

Al compilar el programa y ejecutarlo nos muestra el arreglo ordenado ascendentemente:

Ejecución de programa compilado de algoritmo de ordenamiento por inserción

c. Reescribe el procedimiento de Ordenamiento por Inserción del ejercicio anterior para que lo ordene de forma decreciente.

i. Construye las nuevas representaciones (pseudocódigo y diagrama de flujo).

ii. Programa el código para que acepte un valor de selección que determine la entrega del resultado (orden creciente o decreciente seleccionable en pantalla).

Para el pseudocódigo, por simplicidad se omite la llamada desde una rutina main, llenado del arreglo, y mostrar el arreglo ordenado, a diferencia del paso anterior se hace que los elementos se corran si son mayores y no menores (se subraya la diferencia del programa previo).

5. Inicio de rutina de ordenación (parámetros: variable arreglo con valores a ordenar pasado por referencia)

6. Declara variables índice indice, indice_previo, cantidad_elementos y valor_actualcantidad_elementos <- cantidad de elementos en arreglo

indice <- 1for indice < cantidad_elementos - 1valor_actual = arreglo[indice]indice_previo <- indice – 1while indice_previo >= 0 and arreglo[indice_previo] > valor_actualarreglo[indice] <- arreglo[indice_previo]indice_previo <- indice_previo – 1

end-whilearreglo[indice] <- valor

end-for7. retorna a función principal8. Fin

Pseudocódigo de algoritmo de ordenamiento por inserción en orden descendente

Diagrama de flujo de algoritmo de ordenamiento por inserción en orden descendente

Implementación en C de algoritmo de ordenamiento por inserción ascendente o descendente

Al compilar el programa y ejecutarlo nos pregunta el orden y dá el arreglo ordenado apropiadamente:

Ejecución de programa compilado de algoritmo de ordenamiento por inserción ascendente o descendente

Referencia:http://es.wikipedia.org/wiki/Ordenamiento_por_inserci%C3%B3n