Algoritmos de Ordenação em Haskell

Ordenar uma coleção é uma das principais atividades realizadas na computação. Neste post, apresentaremos diversos métodos de ordenação na linguagem Haskell.

Ordenação por Seleção 

Este método consiste em encontrar o menor da coleção e colocá-lo como primeiro da nova coleção criada.

ordsel :: (Ord a) => [a] -> [a] ordsel [] = [] ordsel x  = m : ordsel ( remove m x)                   where m = minimum x                remove :: (Ord a) => a -> [a] -> [a] remove m []       = [] remove m (x:xs)  | x == m    = xs                                                          | otherwise = x : (remove m xs)

Ordenação por inserção

Na ordenação por inserção, precisamos saber inserir um elemento em uma lista ordenada e gerar um nova lista ordenada.

A inserção de um elemento em uma lista ordenada pode ser realizada de três maneiras diferentes:

inserir :: (Ord a) => a -> [a] -> [a] inserir x [] = [x] inserir x (y:ys) | x < y = x : y : ys                  | otherwise = y : inserir x ys                   inserir2 :: (Ord a) => a -> [a] -> [a] inserir2 x [] = [x] inserir2 x (y:ys) =  if x < y then x : y : ys else y : inserir x ys --takeWhile :: (a -> Bool) -> [a] -> [a] -- aplica um predicado p e uma lista xs e devolve uma lista com os elementos de xs -- que satisfazem p --dropWhile :: (a -> Bool) -> [a] -> [a] --dropWhile p xs devolve uma lista com elementos restantes de takeWhile p xs  inserir3 :: (Ord a) => a -> [a] -> [a] inserir3 x xs = takeWhile ( (>=) x) xs ++ [x] ++ dropWhile ( (>=) x) xs

A ordenação por inserção é a aplicação sucessiva da operação de inserção em uma lista ordenada. Podemos fazer de duas maneiras:

ordinsercao :: (Ord a) => [a] -> [a] ordinsercao []     = [] ordinsercao (x:xs) = inserir x (ordinsercao xs)  --foldr :: (a -> b -> b) -> b -> [a] -> b --foldr aplica uma operacao binária, um valor inicial, e uma lista, reduz --reduz a lista usando a operacao binária --foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...) ordinsercao2 :: (Ord a) => [a] -> [a] ordinsercao2 []    = [] ordinsercao2 x = foldr inserir [] x

MergeSort

Para definir o mergesort, primeiramente, precisamos definir a função de merge. A função de merge recebe duas listas ordenadas e devolve uma lista ordenada formada pelo elementos das duas listas.

merge :: (Ord a) => [a] -> [a] -> [a] merge xs [] = xs merge [] ys = ys merge (x:xs) (y:ys) = if x <= y then x : merge xs (y:ys) else y : merge (x:xs) ys

O algoritmo de mergesort consiste em separar a lista em duas sublistas ordená-las recursivamente e realizar o merge das duas sublistas ordenadas.

mergesort :: (Ord a) => [a] -> [a] mergesort []  = [] mergesort [x] = [x] mergesort xs  | tamanho >= 1 = merge (mergesort metade1 (mergesort metade2) where  tamanho = length xs `div` 2 metade1 = take tamanho xs metade2 = drop tamanho xs y

QuickSort

Para definir o quicksort, primeiramente, precisamos definir a operação de particionamento do vetor dado um elemento especial que é chamado de pivô.

O recurso de Compreensão de Listas (List Comprehension) (Essa tradução é a melhor?) torna essa tarefa bastante fácil.

A lista formada pelos elementos de uma lista xs menores ou iguais a x é dada por

[ y | y <- xs , y <= x ]

Logo, o algoritmo de quicksort fica apenas:

quicksort :: (Ord a) => [a] -> [a] quicksort [] = [] quicksort (x:xs) = quicksort [ y | y <- xs , y <= x ] ++ [x] ++ [ y | y<-xs, y>x]

BubbleSort

O método de ordenação por bolha consiste em uma sucessão de troca entre elementos adjacentes. A cada iteração, um elemento é posicionado em uma sua posição correta. Na primeira iteração, o maior valor é colocado na última posição. Depois, o segundo maior é colocado na penúltima posição e assim por diante.

bolha :: (Ord a) => [a] -> [a] bolha []     = [] bolha lista  = bolhaOrd lista (length lista) bolhaOrd :: (Ord a) => [a] -> Int -> [a] bolhaOrd lista 0 = lista bolhaOrd lista n = bolhaOrd (troca lista) (n-1) troca :: (Ord a) => [a] -> [a] troca [x]     = [x] troca (x:y:zs) | x > y      = y : troca (x:zs)            | otherwise  = x : troca (y:zs)

Leia também:
Comparação dos métodos de ordenação
http://marathoncode.blogspot.com.br/2012/05/metodos-de-ordenacao.html
Encontrar a mediana
http://marathoncode.blogspot.com.br/2012/02/problema-da-mediana.html
Compreensão de Listas em Python
http://marathoncode.blogspot.com.br/2012/03/list-comprehension-e-generator.html
Contando o número de inversões
http://marathoncode.blogspot.com.br/2012/06/contando-numero-de-inversoes.html


Fontes 
1. Haskell - Uma abordagem prática. Cláudio César de Sá e Márcio Ferreira da Silva. Novatec, 2006. 2. 2. Haskell - The craft of functional programming. Simon Thompson. Pearson, Addison-Wesley, 1999.

Referências
http://www.facom.ufu.br/~madriana/PF/Haskell11.pdf