Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #57 da revista programar. Faz já o download aqui!

brunogsimoes

Quick Sort

Mensagens Recomendadas

brunogsimoes    1
brunogsimoes

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Joe    0
Joe

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]

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
brunogsimoes    1
brunogsimoes

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.

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
K3nshin    0
K3nshin

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

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Rui Carlos    309
Rui Carlos

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.

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


×

Aviso Sobre Cookies

Ao usar este site você aceita a nossa Política de Privacidade