Comparación De Algoritmos De Ordenación

´ Departamento de Ciencias de la Computacion
CC3001 Algoritmos y Estructuras de Datos

Informe Tarea 2 Comparaci´n de algoritmos iterativos y recursivos o

Fecha: 27 de Agosto de 2012 Autor: Cristian J´uregui S. a E-mail: cristiaaan.25@gmail.com

Profesor: Benjam´ Bustos ın Auxiliares: Diego Rivera Iv´n Sipiran a

CC3001 Algoritmos y Estructuras de Datos

´ INDICE

´ Indice
1.Introducci´n o 2. An´lisis del problema a 3. Soluci´n del Problema o 3.1. Algoritmo Inserci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 3.2. Algoritmo Shellsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3. Algoritmo Recursivo Stooge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.Aleatorio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5. Copiar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6. Invertir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7. Main . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . 4. Resultados 4.1. Algoritmo Inserci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 4.2. Algoritmo Shellsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3. Algoritmo Recursivo Stooge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4. Conclusiones . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5. Anexos 6. Bibliograf´ ıa 3 4 6 6 7 8 8 9 9 10 13 13 14 16 20 21 24

1

CC3001 Algoritmos y Estructuras de Datos

´ INDICE DE FIGURAS

´ Indice de figuras
1. 2. 3. 4. 5. 6. 7. 8. 9. Algoritmo de Inserci´n. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Algoritmo Shellsort. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Algoritmo de Inversi´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Comparaciones en funci´n del tama˜o, Algoritmo Inserci´n. . . . . . . . . . . . . . . . . . . . o n o Ajuste polinomial para arreglos aleatorios, Algoritmo Inserci´n. . . . . . . . . . . . . . . . . . o Comparaciones enfunci´n del tama˜o, Algoritmo Inserci´n. . . . . . . . . . . . . . . . . . . . o n o Ajuste polinomial para arreglos aleatorios, Algoritmo Shellsort. . . . . . . . . . . . . . . . . . Comparaciones en funci´n del tama˜o, Algoritmo Recursivo Stooge Sort. . . . . . . . . . . . o n Ajuste polinomial para todos los arreglos, Algoritmo Recursivo Stooge Sort. . . . . . . . . . . 4 5 9 13 14 16 16 18 182

CC3001 Algoritmos y Estructuras de Datos

1

´ INTRODUCCION

1.

Introducci´n o

El tratamiento de datos es una rama muy importante de las ciencias de la computaci´n hoy en d´ ya o ıa, que un sinf´ de procedimientos se realizan entorno a ellos y producen aun m´s datos. Ahora bien, estos ın a procedimientos en general conllevan millones de datos, los cuales se deben manipular deciertas formas para obtener representaciones sistem´ticas u organizadas de los mismos. Sin embargo, se deben buscar a procedimientos que impliquen el menor uso de recursos posible, tanto temporales como computacionales. Bajo este contexto es que se plantea el marco de la Tarea 2, cuyo objetivo es comparar diversos m´todos e para ordenar de menor a mayor los datos contenidos en un arreglo y determinarel desempe˜o de ellos frente n a la tarea asignada en diversas situaciones. En particular, se deben implementar las soluciones denominadas Algoritmo Inserci´n y Algoritmo Shellsort, que caben en la categor´ de algoritmos iterativos, y Algoritmo o ıa Recursivo denominado Stooge Sort. Por otra parte, se deben someter a comparaci´n cada una de las t´cnicas mencionadas, para lo cual se o e medir´...