Comparacion Algoritmos

Algorítmica y modelos de computación
Practica1 Análisis experimental de los algoritmos de ordenación

Luis Castilla Pla

Pág 1

Índice
Análisis teórico-practico.............................................................................................................Pág 2Ordenación....................................................................................................................................Pág 2 O.Selección....................................................................................................................................Pág 2 O.Insercción...................................................................................................................................Pág 4O.Burbuja......................................................................................................................................Pág 5 O.Shell...........................................................................................................................................Pág 7 O.QuickSort.................................................................................................................................Pág 10O.HeapSort..................................................................................................................................Pág 12 O.MergeSort................................................................................................................................Pág 13 Comparacion de Ordenamientos.................................................................................................Pág15 Búsqueda.....................................................................................................................................Pág 16 Busqueda Lineal..........................................................................................................................Pág 17 BusquedaBinaria.........................................................................................................................Pág 18 Busqueda Hash............................................................................................................................Pág 19 Comparacion de Busquedas........................................................................................................Pág 22 Diseño de laaplicación..............................................................................................................Pág 23 Implementación...........................................................................................................................Pág 23 Diagrama de Clases.....................................................................................................................Pág 23

Luis Castilla Pla

Pág 2

Análisisteóricos-empiricos
Para todos los estudios teóricos, hemos tomado las operaciones como 1, ya que el hecho de que sea un numero de operaciones constante no va a variar el resultado del orden del algoritmo

Ordenación:
Ordenación por selección: Este tipo de ordenación consiste en buscar en nuestro array, ver el mas pequeño y ponerlo el primero, buscar en el vector restante el siguiente mas pequeño, colocarloel segundo, y así sucesivamente hasta tener ordenado el vector. CODIGO:
para i=1 hasta n-1 minimo = i;__________________________________________________ 1 para j=i+1 hasta n___________________________________________3 si lista[j] < lista[minimo] entonces_____________________ 1 minimo = j /* (!) */_________________________________ 1 fin si fin para intercambiar(lista[i],lista[minimo])________________________3 fin para

A través del estudio teórico obtenemos O(n2):

Luis Castilla Pla

Pág 3

El estudio empírico:

Nos confirma nuestros datos, y vemos como la gráfica se aproxima a O(n2). Ordenación por inserción: Para este método, vamos seleccionando los elementos, y los comparamos con sus anteriores, dado que empezamos por el primero, los elementos “anteriores” al elemento se...