G3ComparativaAlgoritmosOrdenacion

Algoritmos de
ordenación
Una comparativa de los principales algoritmos de
ordenación implementados en lenguajes
imperativos y funcionales

Fco. Elías Cabrera Lara
Juan Fco. Hiraldo Sánchez
1

Algoritmos que vamos a
comparar


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 unaoptimización de Tree Sort)
◦ Mergesort

2

¿Qué lenguajes vamos a
usar?


Para nuestra comparativa vamos a usar un
lenguaje imperativo frecuentemente
utilizado como es Java; y como lenguaje
funcional vamos a usar Haskell.

3

¿Cómo pensábamos realizar la
comparativa?


Esta comparativa la pretendíamos realizar
con las siguientes condiciones:
◦ Un array con un número determinado de
elementos dependiendodel 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.

4

¿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 quevamos 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

5

Problemas que se plantean:
Velocidad de los algoritmos


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 loque 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.

6

Problemas que se plantean:
Estructuras de datos



Haskell utiliza internamente listas enlazadas.
Java puede utilizar Arrays y Listas.
◦ Si utilizamos Arrays, tenemos ventaja ya que el
acceso a laposició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.
7

Algoritmos de ordenación

8

Bubble Sort


Se basa en en comparar cada par de
elementos adyacentes.
◦ De cada par de elementos uno es mas ligero
(menor) que el otro.

◦ Si elelemento mas ligero está a la derecha,
entonces cambia de lugar.

9

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.

10

Bubble Sort: Implementación en
Java
for (int i=1; i {
for(int j=0;j {
if (a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];a[j+1]=temp;
}
}
}

11

Bubble Sort: Implementación en
Haskell
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

12

Bubble Sort: Conclusiones


3000 numeros aleatorios.

Java con listas enlazadas: 33.0202s
 Haskell (interpretado): 5.9411s
 Haskell(compilado): 0.3382 s
 Java con Arrays: 15,3ms


13

Bubble Sort: Conclusiones


Es mucho más claro de leer el código en Haskell que en
Java. Esto lo veremos también con los siguientes
algoritmos.



Los Arrays otorgan muchísima ventaja a los algoritmos
que acceden mucho a posiciones concretas.



Las listas en Haskell son mas eficientes que en Java.



En general comparar los 2 lenguajes como sifuera una
competición no tiene mucho sentido, cada cual es
mejor en lo suyo, como veremos en la segunda parte.

14

FIN DE LA PRIMERA
PARTE

15

InsertionSort
Tiene complejidad O(n2).
 Funciona de la siguiente manera:


◦ Al principio se tiene un elemento, que se
considera un conjunto ordenado.
◦ Después , al haber k elementos ordenados de
menor a mayor se coge el elemento k+1 y se va...

Leer documento completo

Regístrate para leer el documento completo.