Vamos a comparar los algoritmos de ordenación mas conocidos que se usan hoy día, a saber:
Bubblesort
Insertion Sort
Selection Sort
Quicksort (que es una optimización de Tree Sort)
Mergesort
1
Algoritmos que vamos a comparar
Para nuestra comparativa vamos a usar un lenguaje imperativo frecuentemente utilizado como es Java; y como lenguaje funcional vamos a usar Haskell.
2
¿Qué lenguajes vamos a usar?
Esta comparativa la pretendíamos realizar con las siguientes condiciones:
Un array con un número determinado de elementos dependiendo del algoritmo que usemos para que no sea demasiado costosa la medida de tiempos.
Estos elementos serán números aleatorios.
Mediremos el tiempo que tarda cada ordenación ignorando la generación de números aleatorios.
3
¿Cómo pensábamos realizar la comparativa?
Usaremos un algoritmo iterativo para bubble sort e insertion sort en Java y sus versiones recursivas en Haskell.
La máquina que vamos a usar para realizar la comparativa tiene las siguientes características:
CPU: Intel Core i7-2600 @3.40 GHz
Memoria RAM: 8 GB DDR3
S.O: Windows 7
4
¿Cómo pensábamos realizar la comparativa?
La eficiencia temporal de los algoritmos es muy distinta.
Algunos tardan minutos en lo que otros tardan meses.
No queremos comparar entre sí los algoritmos, ya que sabemos lo que van a tardar más o menos; sino que vamos a comparar entre los 2 lenguajes que hemos dicho anteriormente.
Solución:
El número de elementos a ordenar lo ajustaremos según el algoritmo.
5
Problemas que se plantean: Velocidad de los algoritmos
Haskell utiliza internamente listas enlazadas.
Java puede utilizar Arrays y Listas.
Si utilizamos Arrays, tenemos ventaja ya que el acceso a la posición de memoria es inmediato.
Las listas enlazadas son mucho mas eficientes en Haskell que en Java.
Solución:
Analizar 4 opciones:
Haskell interpretado, Haskell compilado, Java con Arrays y Java con LinkedList.
6
Problemas que se plantean: Estructuras de datos
7
Algoritmos de ordenación
Se basa en en comparar cada par de elementos adyacentes.
De cada par de elementos uno es mas ligero (menor) que el otro.
Si el elemento mas ligero está a la derecha, entonces cambia de lugar.
8
Bubble Sort
Se van comparando cada par de elementos adyacentes de la lista.
Si se llega al final de la lista se vuelve al principio hasta que la lista quede ordenada.
9
Bubble Sort
for (int i=1; i< a.length;i++)
{
for(int j=0;j< a.length-1;j++)
{
if (a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
10
Bubble Sort: Implementación en Java
bsort :: Ord a => [a] -> [a]
bsort s = case _bsort s of
t | t == s -> t
| otherwise -> bsort t
where _bsort (x:x2:xs) | x > x2 = x2:(_bsort (x:xs))
| otherwise = x:(_bsort (x2:xs))
_bsort s = s
11
Bubble Sort: Implementación en Haskell
3000 numeros aleatorios.
Java con listas enlazadas: 33.0202s
Haskell (interpretado): 5.9411s
Haskell (compilado): 0.3382 s
Java con Arrays: 15,3ms
12
Bubble Sort: Conclusiones
Página siguiente  |