Practica 01

Anlisis de algoritmos
Practica 01 : Pruebas a posteriori (Algoritmos de

Ordenamiento)
Entrega va Web: Mircoles 10 de Septiembre de 2014
M. en C. Edgardo Adrin Franco Martnez
http://www.eafranco.com
edfrancom@ipn.mx
@edfrancom
edgardoadrianfrancom
Definicin del problema

Actividades
Observaciones
Reporte de prctica
Entrega va Web
Fecha de entrega
Practica 01 : Pruebas a posteriori
Prof. Edgardo Adrin Franco Martnez
Contenido
Con base en el archivo de entrada proporcionado

que tiene 10,000,000 nmeros diferentes.
Ordenarlo bajo los siguientes mtodos de
ordenamiento y comparar experimentalmente las
complejidades de estos.
Burbuja (Bubble Sort)
Burbuja Simple
Burbuja Mejorada
Insercin (Insertion Sort)
Seleccin (Selection Sort )
Shell (Shell Sort)
Ordenamiento con rbol binario de busqueda (Binary
Search Tree)
Compiladores (Anlisis Lxico II - Edgardo A. Franco)
Definicin del problema
Burbuja Simple
El mtodo de la burbuja es uno de los mas simples,
es tan fcil como comparar todos los elementos de
una lista contra todos, si se cumple que uno es
mayor o menor a otro, entonces los intercambia de
posicin. Procedimiento BurbujaSimple(A,n)
para i=1 hasta (i<n) hacer
para j=0 hasta (j<n-1) hacer
si (A[j]>A[j+1]) hacer
temp = A[j]
A[j] = A[j+1]
A[j+1] = temp
fin si
fin para
fin para
fin Procedimiento
Ordenamiento Burbuja
Procedimiento BurbujaMejorada(A,n)
para i=1 hasta (i<n) hacer
para j=0 hasta (j<i) hacer
si(A[i] < A[j]) hacer
temp = A[j]
A[j] = A[i]
A[i] = temp
fin si
fin para
fin para
fin Procedimiento
Burbuja Mejorada
El hecho que los elementos que estn detrs del que
se esta comparando, ya estn ordenados, permite
realizar un numero menor de comparaciones.
Es una manera muy natural de ordenar para un ser humano,

y puede usarse fcilmente para ordenar un mazo de cartas
numeradas en forma arbitraria.
Inicialmente se tiene un solo elemento, que obviamente es
un conjunto ordenado. Despus, cuando hay k elementos
ordenados de menor a mayor, se toma el elemento k+1 y se
compara con todos los elementos ya ordenados,
detenindose cuando se encuentra un elemento menor
(todos los elementos mayores han sido desplazados una
posicin a la derecha) o cuando ya no se encuentran
elementos (todos los elementos fueron desplazados y este
es el ms pequeo). En este punto se inserta el elemento
k+1 debiendo desplazarse los dems elementos.
Ordenamiento por insercin
Procedimiento Insercion(A,n)
{
para i=1 hasta i<n hacer
temp=A[i]
j=i-1
mientras((A[j]>temp)&&(j>=0)) hacer
A[j+1]=A[j]
j-fin mientras
A[j+1]=temp
fin para
fin Procedimiento
Se basa en buscar el mnimo elemento de la

lista e intercambiarlo con el primero, despus
busca el siguiente mnimo en el resto de la
lista y lo intercambia con el segundo, y as
sucesivamente.
Ordenamiento por seleccin
Algoritmo
Buscar el mnimo elemento entre una posicin
i y el final de la lista Intercambiar el mnimo
con el elemento de la posicin i.
8
Procedimiento Seleccion(A,n)
para k=0 hasta k<n-1 hacer
p=k;
para i=k+1 hasta i>n-1 hacer
si A[i]<A[p] hacer
p = i
fin si
fin para
si p!=k hacer
temp = A[p]
A[p] = A[k]
A[k] = temp
fin si
fin para
fin Procedimiento
El Shell es una generalizacin del ordenamiento por

insercin, teniendo en cuenta dos observaciones:
1. El ordenamiento por insercin es eficiente si la entrada
est "casi ordenada".
2. El ordenamiento por insercin es ineficiente, en
general, porque mueve los valores slo una posicin
cada vez.
El algoritmo Shell mejora el ordenamiento por insercin

comparando elementos separados por un espacio de
varias posiciones. Esto permite que un elemento haga
"pasos ms grandes" hacia su posicin esperada. Los
pasos mltiples sobre los datos se hacen con tamaos
de espacio cada vez ms pequeos. El ltimo paso del
ordenamiento Shell es un simple ordenamiento por
insercin, pero para entonces, ya est garantizado que
los datos del vector estn casi ordenados.
Ordenamiento Shell
10
Se debe empezar con k=n/2, siendo n el nmero de elementos

de array, y utilizando siempre la divisin entera
Despus iremos variando k hacindolo ms pequeo
mediante sucesivas divisiones por 2, hasta llegar a k=1.
Compiladores (Anlisis Lxico II Practica 01 : Pruebas a posteriori
Edgardo A. Franco)
Shell propone que se haga sobre el array una serie de

ordenaciones basadas en la insercin directa, pero dividiendo
el array original en varios sub-arrays tales que cada elemento
est separado k elementos del anterior (a esta separacin a
menudo se le llama salto o gap)
11
Procedimiento Shell(A,n)
k = n / 2;
mientras k >= 1 hacer
para i=k hasta i>=n hacer
v = A[i]
j = i - k;
mientras j >= 0 && A[j] > v hacer
A[j + k] = A[j];
j -= k;
fin mientras
A[j + k] = v;
fin para
k/=2;
fin mientras
fin Procedimiento
12
El ordenamiento con la ayuda de un rbol binario

de bsqueda es muy simple debido a que solo
requiere de dos pasos simples.
1. Insertar cada uno de los nmeros del vector a
ordenar en el rbol binario de bsqueda.
2. Remplazar el vector en desorden por el vector
resultante de un recorrido InOrden del rbol
Binario, el cual entregara los nmeros ordenados.
La eficiencia de este algoritmo esta dada segn la

eficiencia en la implementacin del rbol binario de
bsqueda, lo que puede resultar mejor que otros
algoritmos de ordenamiento.
Ordenamiento con un rbol binario de bsqueda
13
para i=0 hasta i>=n hacer

Insertar(ArbolBinBusqueda,A[i]);
fin para
Procedimiento OrdenaConArbolBinario(A,n)
GuardarRecorridoInOrden(ArbolBinBusqueda,A);
fin Procedimiento
14
1. Programar en ANSI C, cada uno de los algoritmos

de ordenamiento mencionados.
Actividades
2. Adaptar el programa para que sea capaz de recibir

un parmetro n que indica el numero de
enteros a ordenar a partir de un archivo con
mximo 10,000,000 de nmeros en desorden.
4
9
1
2
5
6
9
0
1
1
3
2
2
2
9
9
0
2
3
5
4
9
1
2
5
6
9
0
1
1
3
2
2
2
9
9
0
2
3
5
4
9
1
2
5
6
9
0
1
1
3
2
2
2
9
9
0
2
3
5
15
Auxiliarse de la librera de C proporcionada para medir

tiempos de ejecucin bajo Linux.
Algoritmo
Tiempo Real
Tiempo
CPU
Tiempo E/S
3. Medir el tiempo que tarda cada algoritmo en

ordenar el archivo completo (n=10,000,000) y
compare los tiempos (Real y de CPU) de cada
algoritmo grficamente en una grafica de barras
(2 graficas de barras).
% CPU/Wall
16
Los primeros 100, 1000, 5000, 10000, 50000, 100000,

200000, 400000, 600000, 800000, 1000000, 2000000,
3000000, 4000000, 5000000, 6000000, 7000000,
8000000, 9000000 y 10000000.
Graficar el comportamiento temporal de cada
Ordenamiento Shell
algoritmo
4. Realizar un anlisis temporal para cada algoritmo,

ordenando:
7000
TIEMPO (SEG)
6000
5000
4000
Tiempo real
3000
Tiempo CPU
2000
Tiempo E/S
1000
0
0
5000
10000 15000 20000 25000 30000 35000

TAMAO DE PROBLEMA (N)
5. Graficar una comparativa de los 5 algoritmos de

ordenamiento (Tiempo real).
17
Aproximar cada algoritmo con un polinomio de grado 1, 2, 3,

4 y 8.
7. Mostrar grficamente la comparativa de las

aproximaciones para cada algoritmo (5 graficas) y
determinar de manera justificada cul es la mejor
aproximacin para cada algoritmo.
8. Determine con base en las aproximaciones obtenidas
cual ser el tiempo real de cada algoritmo para
50000000, 100000000, 500000000, 1000000000 y
500000000 de nmeros a ordenar.
6. Realizar una aproximacin polinomial del

comportamiento temporal (tiempo real), de cada uno
de los algoritmos probados segn el punto 4.
18
i.
ii.
iii.
iv.
v.
vi.
vii.
viii.
ix.
x.
Cul de los 5 algoritmos es ms fcil de implementar?

Cul de los 5 algoritmos es el ms difcil de
implementar?
Cul algoritmo tiene menor complejidad temporal?
Cul algoritmo tiene mayor complejidad temporal?
Cul algoritmo tiene menor complejidad espacial?
Por qu?
Cul algoritmo tiene mayor complejidad espacial?
Por qu?
El comportamiento experimental de los algoritmos era
el esperado? Por que?
Sus resultados experimentales difieren mucho de los
del resto de los equipos? A que se debe?
Existi un entorno controlado para realizar las pruebas
experimentales? Cul fue?
Qu recomendaciones daran a nuevos equipos para
realizar esta practica?
9. Finalmente responda a las siguientes preguntas:
19
Utilizar solo ANSI C.
La programacin de cada uno de los mtodos de ordenamiento

no deber de incluir recursividad (Algoritmos secuenciales). Por
lo tanto buscar una implementacin no recursiva para la
insercin en un rbol binario y para realizar el recorrido inOrden.
Indique cual fue su plataforma experimental (Caractersticas del
hardware, compilador, sistema operativo y entorno controlado)
Observaciones
Se sugiere crear scripts que faciliten la experimentacin.

En el laboratorio mostrar el funcionamiento de los programas,
estos ya deber de contar con la documentacin necesaria.
Autodocumentacin
Documentacin de funciones y algoritmos
20
Portada
Introduccin
Planteamiento del problema
Algoritmos (Descripcin de la abstraccin
del problema y los algoritmos de

ordenamiento que dan solucin, apoyndose de pseudocdigo, diagramas y figuras
en un lenguaje claro)
Implementacin de los algoritmos
(Dados los algoritmos de ordenamiento
Reporte de practica
como se implementaron en el cdigo)
Actividades y Pruebas
(Verificacin de la solucin, pruebas y resultados de la
prctica segn lo solicitado)
Errores detectados
(Si existe algn error detectado, el cul no fue posible

resolver o se desconoce el motivo y solo ocurre con ciertas condiciones es necesario
describirlo)
Posibles mejoras
(Describir posibles disminuciones de cdigo en la

implementacin o otras posibles soluciones)
Conclusiones (Por cada integrante del equipo)

Anexo (Cdigos fuente *con colores e instrucciones de compilacin)
Bibliografa (En formato IEEE)
21
Grupo
Contrasea
3CM5
analisis3cm5
3CM6
analisis3cm6
En un solo archivo comprimido (ZIP, RAR, TAR, JAR o GZIP)
Entrega va Web
Reporte (DOC, DOCX o PDF)

Cdigos fuente (.C, .H, etc.)
Cdigo documentado: Titulo, descripcin, fecha, versin, autor.
(Funciones y Algoritmos: Qu hace?, Cmo lo hace?, Qu recibe?, Qu
devuelve?, Causa de errores?).
OBSERVACIONES
*NO enviar ejecutables o archivos innecesarios, las instrucciones de
compilacin van en el anexo del reporte. (Yo compilare los fuente).
*NO enviar archivo de nmeros en desorden ni archivo de numeros
ordenados.
22
Demostracin (Laboratorio de Sistemas 1)

3CM5 Mircoles 03 de Septiembre de 2014
3CM6 Mircoles 03 de Septiembre de 2014
Entrega de reporte y cdigo
Fecha de entrega
En un solo archivo comprimido
Fecha y hora limite de entrega va Web

Mircoles 10 de Septiembre de 2014 a las
23:59:59 hrs.
23

Practica 01

Cargado por

Copyright:

Formatos disponibles

Practica 01

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Practica 01

Cargado por

Copyright:

Formatos disponibles

Anlisis de algoritmos

Practica 01 : Pruebas a posteriori (Algoritmos de

Definicin del problema

Con base en el archivo de entrada proporcionado

Definicin del problema

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

Es una manera muy natural de ordenar para un ser humano,

Ordenamiento por insercin

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

Se basa en buscar el mnimo elemento de la

Ordenamiento por seleccin

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

El Shell es una generalizacin del ordenamiento por

El algoritmo Shell mejora el ordenamiento por insercin

Se debe empezar con k=n/2, siendo n el nmero de elementos

Shell propone que se haga sobre el array una serie de

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

El ordenamiento con la ayuda de un rbol binario

La eficiencia de este algoritmo esta dada segn la

Ordenamiento con un rbol binario de bsqueda

para i=0 hasta i>=n hacer

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

1. Programar en ANSI C, cada uno de los algoritmos

2. Adaptar el programa para que sea capaz de recibir

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

Auxiliarse de la librera de C proporcionada para medir

3. Medir el tiempo que tarda cada algoritmo en

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

Los primeros 100, 1000, 5000, 10000, 50000, 100000,

4. Realizar un anlisis temporal para cada algoritmo,

10000 15000 20000 25000 30000 35000

5. Graficar una comparativa de los 5 algoritmos de

Aproximar cada algoritmo con un polinomio de grado 1, 2, 3,

7. Mostrar grficamente la comparativa de las

6. Realizar una aproximacin polinomial del

Cul de los 5 algoritmos es ms fcil de implementar?

9. Finalmente responda a las siguientes preguntas:

Utilizar solo ANSI C.

La programacin de cada uno de los mtodos de ordenamiento

Se sugiere crear scripts que faciliten la experimentacin.

del problema y los algoritmos de

Implementacin de los algoritmos

(Dados los algoritmos de ordenamiento

como se implementaron en el cdigo)

(Verificacin de la solucin, pruebas y resultados de la

prctica segn lo solicitado)

(Si existe algn error detectado, el cul no fue posible

(Describir posibles disminuciones de cdigo en la

Conclusiones (Por cada integrante del equipo)

En un solo archivo comprimido (ZIP, RAR, TAR, JAR o GZIP)

Reporte (DOC, DOCX o PDF)

Demostracin (Laboratorio de Sistemas 1)

Entrega de reporte y cdigo

En un solo archivo comprimido

Fecha y hora limite de entrega va Web

Compiladores (Anlisis Lxico II - Edgardo A. Franco)

También podría gustarte