Imaginemos un mundo libre

La paz interior comienza en el momento en el que decides no permitir, que ninguna persona o evento, tome el control de tus emociones.

Algoritmos de ordenación – Haskell

with 3 comments

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:

Written by Ronny Yabar

December 11, 2007 at 6:28 pm

3 Responses

Subscribe to comments with RSS.

  1. En el mergeSort tomás como caso base [] y retorna [], hasta ahi me gusta, pero fijate que pasa si la invocas con una lista de 1 elemento
    intentaria hacer
    merge (mergeSort izq) (mergeSort der)
    donde
    mitad = div (length l) 2 = 0
    izq take 0 l = []
    der drop 0 l = l
    merge [] (mergeSort der)
    el problema es que mergeSort der = mergeSort l que es lo que intentamos resolver antes, de esta manera entra en un bucle infinito, es decir para ordenar l, rimero tiene que ordenar l !!! absurdo, mi propuesta es:

    mergeSort :: Ord a => [a] -> [a]
    mergeSort l | length l <= 1 = l
    | otherwise = merge (ordNat izq) (ordNat der)
    where
    mitad = length l `div` 2
    izq = take mitad l
    der = drop mitad l
    si l es [] devuelve []
    si tiene un elemento ya esta ordenada
    Espero te sea de ayuda, seguramente no te diste cuenta del error xq no lo probaste, pero si lo probas no terminas mas ya me parecia raro que un core 2 duo tarde tanto con una lista de un elemento, cualquier cosa manda mail suerte y muchas gracias por tu aporte.

    Ariel

    May 15, 2008 at 5:38 am

    • El artículo me parece muy bueno, pero tienes razón, mergeSort no funciona

      Javier S.A

      September 24, 2014 at 7:34 am

  2. -> hola

    asdas

    January 28, 2009 at 1:37 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: