Análisis de algoritmos
Análisis de Algoritmos
Lic. en Ciencias de la Computación
Luis Arnoldo Galaz Castillo 04/10/2011
Universidad de Sonora 2 Análisis de Algoritmos Luis Arnoldo GalazCastillo
TAREA 1. ANALISIS DE ALGORITMOS En el presente trabajo se hace uso de los algoritmos de ordenamiento vistos en clase tales como: insertion-sort, selectionsort y merge-sort respectivamente. Paracada uno de los algoritmos se aplicaron 10 diferentes valores de n, para el Mejor caso, Peor caso y caso Promedio, además se calcularon sus tiempos de ejecución. Los algoritmos fueron implementadosen lenguaje c++. Peor caso: Se utilizó un arreglo ya ordenado en orden creciente. Mejor caso: Se utilizó un arreglo ya ordenado en orden decreciente. Caso Promedio: Se utilizó la función rand() parageneral números aleatorios y fueron almacenados en un arreglo. Tiempos de ejecución: Se utilizó la función clock() de la librería time.h, y mediante la siguiente operación se obtuvo un tiempo enmilisegundos (ms). t=((fin-ini)/(double)CLOCKS_PER_SEC)*1000; donde fin-ini representa la diferencia de el valor inicial y final obtenido de la función clock(), dividiendo entre CLOCKS_PER_SEC para obtenerlos segundos y multiplicándolo por 1000 para llegar a los milisegundos. A continuación se muestran los algoritmos ya implementados en el lenguaje c++. Especificaciones más relevantes del sistema depruebas: Procesador: AMD Phenomx4 9950be quad-core 2.6Ghz @ 3.0Ghz Memoria: 4GB ram 800mhz dual channel Sistema Operativo: Windows 7 Ultimate 64bits
Universidad de Sonora 3 Análisis de AlgoritmosLuis Arnoldo Galaz Castillo
INSERTION-SORT El ordenamiento por inserción (insertion-sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar unmazo de cartas numeradas en forma arbitraria. Requiere O(n²) operaciones para ordenar una lista de n elementos. Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado....
Regístrate para leer el documento completo.