Los algoritmos de ordenación, así como los de búsqueda, también son muy estudiados en el área de ciencia de la computación. Básicamente, el trabajo de un algoritmo de ordenación es establecer una relación de orden en una secuencia de elementos. La necesidad de ordenar archivos, datos, etc es una tarea que realizamos muy a menudo en nuestras vidas, por ello la importancia de investigar la eficiencia y complejidad de estos algoritmos.
A continuación vamos a ver algunos algoritmos de ordenación y su implementación en Haskell:
Insert Sort: Se trata de un algoritmo en el que va haciendo comparaciones del primer elemento del vector con el resto y se inserta ese elemento cuando encuentre su ubicación adecuada Es prácticamente un intercambio de elementos hasta que el vector se encuentre ordenado. ESte algoritmo tiene una complejidad en el mejor de los casos de Ω (n) y en el peor de los casos de O(n²). Veamos su implementación y explicación en haskell.
Primero creamos una función que me inserte un elemento dado en una lista en su correcta ubicación, esta función compara el elemento con la cabeza de la lista y si es menor lo inserta delante, caso contrario sigue recorriendo la lista recursivamente. Así:
insert::Ord a => a -> [a] ->[a]
insert e [] = [e]
insert e (x:xs)
| e<=x = e:x:xs
| otherwise = x: insert e xs
Main> insert 5 [1,9,4,7,8,43,34,65,89]
[1,5,9,4,7,8,43,34,65,89]
Como ya tenemos la función que hace ese trabajo, entonces la llamaremos desde otra función para que inserte la cabeza de la lista, en la cola de la misma. Entonces quedaría así:
insertSort::Ord a =>[a] ->[a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
Main> insertSort [45,23,78,96,22,7,6,14]
[6,7,14,22,23,45,78,96]
El algoritmo insertSort no es tan eficiente comparado a otros, pero se recomienda usarlo con vectores pequeños y cuando es necesario una solución rápida, dada su facilidad de programación.
Quick Sort: Algoritmo que utiliza la técnica divide y vencerás ,es uno de los algoritmos más conocidos y eficientes por su rapidez. Consiste en tomar un elemento pibote y a partir de él generar 2 sublistas una de los menores y una de los mayores a él. Y con cada una de estas sublistas hacer lo mismo, es decir es un algoritmo recursivo. Tiene una complejidad en el mejor de los casos de Ω (n log n) y en el peor de los casos de O(n²). Veamo como es en haskell:
quickSort::Ord a=>[a]->[a]
quickSort [] = []
quickSort (x:xs) = quickSort(menores) ++ [x] ++ quickSort(mayores)
where
menores = [y | y <-xs, y < x]
mayores = [z | z <-xs, z >= x]
Main> quickSort [‘p’,’d’,’g’,’r’,’h’,’s’,’x’,’w’,’l’,’i’,’t’,’y’,’a’,’z’,’e’]
“adeghilprstwxyz”
En este caso tomaríamos a p(cabeza de la lista como nuestro pibote y crearíamos 2 sublistas una de los menores de ‘p’ y otra de sus mayores e iríamos llamando a la función recursivamente para que hagan la misma operación con estas sublistas. Cuando se ha dividido hasta más no poder, entonces se empieza a concatenar los elementos menores con su pibote y con los mayores.
Merge Sort: Este también es un algoritmo que usa la técnica dividde y vencerás.Consiste en dividir el vector dado en 2 vectores, ordenar estos vectores aparte y luego mezclar el resultado de las 2 ordenaciones obteniendo así un nuevo vector ordenado.
Tiene una complejidad en el mejor de los casos de Ω (n) y en el peor de los casos de O(n log n). Veamo como es en haskell: Lo primeros que haremos es crear una función que concatener 2 listas ordenadas y el resultado también sea ordenado, llamaremos a esta función Merge, Veamos:
merge::Ord a =>[a] ->[a] ->[a]
merge [] l2 = l2
merge l1 [] = l1
merge (x:xs) (y:ys)
| x<=y = x : merge xs (y:ys)
| True = y : merge (x:xs) ys
Main> merge [1,3,5,7,9] [2,4,6,8]
[1,2,3,4,5,6,7,8,9]
La función Merge lo que hace es ir comparando la cabeza de las 2 lista. En caso que la cabeza de la x (primera lista) sea menor a la cabeza de y (la segunda lista), entonces concatenamos x con la llamada recurisva a su cola y la lista y. caso contrario concatenamos y con la llamada recursiva a la lista x con la cola de y.
Ahora llamaremos a la función Merge en nuestro algoritmo mergeSort, veamos:
mergeSort::Ord a =>[a] ->[a]
mergeSort [] = []
mergeSort l = merge (mergeSort izq) (mergeSort der)
where
mitad = (div (length l) 2)
izq = take mitad l
der = drop mitad l
Obtenemos cual es la mitad de la lista para obtener 2 divisiones con igual número de elementos, para ello simplemente dividimos la longitud de la lista (length) en 2. Las funciones take y drop se utilizan para tomar y quitar elementos de una lista, las veremos más adelante. Pero aquí el objetivo es tener 2 listas y después con la función Merge ordenarlas.
Main> mergeSort [1,3,5,7,9,2,4,6,8]
[1,2,3,4,5,6,7,8,9]
Gracias por tu visita al blog. Puedes seguirme en Twitter haciendo click en el siguiente enlace: Follow @ronnyml