• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

brunogsimoes

Quick Sort

5 mensagens neste tópico

Como escrever o mítico algoritmo quicksort em haskell hehe:

quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = 
  y1++[x]++y2
  where
  (x1, x2) = pv x xs
  y1 = quickSort x1; y2 = quickSort x2

pv :: Ord a => a -> [a] -> ([a], [a])
pv _ [] = ([], [])
pv v (x:xs)
| x < v  = (x:x1s, x2s)
where
(x1s, x2s) = pv v xs
pv v (x:xs)
| x >= v = (x1s, x:x2s)
where
(x1s, x2s) = pv v xs

Não chegei a testar ... qualquer anormalia digam.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tens mais hiposes e mais simples...

- usando o filter

- usando listas por compreensão

ambas são semalhantes

qs :: Ord a => [a] -> [a]
qs [] = []
qs (x:xs) = qs( filter (<x) xs)++[x] ++ qs(filter (>=x) xs)

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

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em programação é sempre difícil dizer que algo é mais simples que alguma outra coisa em comparação.

Na minha experiência pessoal quando dou explicações as pessoas tem mais dificuldades nas listas em compreensão.

Contudo há sempre excepções.

Contudo, pessoalmente adoro o teu post  :)

Quanto menos se escrever melhor.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

quicksort::[int]->[int]
quicksort []=[]
quicksort (x:xs)= quicksort lmenor++[ x ] ++ quicksort lmaior
                             where
                                  lmenor=[k|k<-(x:xs),k<x]
                                  lmaior=[k|k<-(x:xs),k>x]

Abraço

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

esta última implementação é praticamente igual à segunda apresentada.

quanto às listas por compreensão serem difíceis, também há quem ache a recursividade difícil.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora