Free Palestine and Lebanon 🍉 Stop the Genocide
Haskell Logo

Programação Funcional

Questão 37: iSort

Voltar

Apresente uma definição recursiva da função iSort :: Ord a => [a] -> [a] que calcula o resultado de ordenar uma lista. Assuma, se precisar, que existe definida a função insert :: Ord a => a -> [a] -> [a] que dado um elemento e uma lista ordenada retorna a lista resultante de inserir ordenadamente esse elemento na lista.

Exemplo

> iSort [3,1,2,5,4]
[1,2,3,4,5]

Resolução

Clica para revelar

iSort :: Ord a => [a] -> [a]
iSort [] = []
iSort (h:t) = insert h (iSort t)

Explicação

Clica para revelar

Tendo em conta que o enunciado nos permite utilizar a função insert, esta é a forma mais fácil de definir a função. Contudo, existem formas alternativas e mais eficientes de ordenar listas. As outras resoluções apresentam outros algoritmos que podem ser usados para resolver esta questão, apesar de eu não recomendar que sejam usados num teste escrito, devido à dificuldade acrescida em escrever os mesmos.

Resolução

Clica para revelar

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (l:ls) = maisPequenos ++ [l] ++ maiores
    where maisPequenos = quickSort $ filter (<=l) ls
          maiores = quickSort $ filter (>l) ls

Resolução

Clica para revelar

mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort l = merge (mergeSort metade1) (mergeSort metade2)
    where (metade1,metade2) = splitAt (div (length l) 2) l
          merge :: Ord a => [a] -> [a] -> [a]
          merge [] l = l
          merge l [] = l
          merge (a:b) (c:d) = if a < c then a:merge b (c:d) else c:merge (a:b) d