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
iSort :: Ord a => [a] -> [a]
iSort [] = []
iSort (h:t) = insert h (iSort t)
Explicação
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
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
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