🚀 go-pugleaf

Dnia Sun, 15 Jun 2003 20:09:33 +0000 (UTC), Marcin Gajda napisał(a):
> Witam,
  
> Tak więc - macie może jakiś pomysł na coś szybszego? Mógłbym posortować w
> O(nlogn) jakimś merdżsortem, ale nie jestem pewien, czy tędy droga...

tak jak Qrczak już napisał sort + przeleciec sie po liscie, mi też nie
przychodzi nic prostszego do głowy
 
> Wszelkie uwagi (krytyczne!) na temat stylu i podejścia miło widziane - dopiero
> się zapoznaję z tym Haskellem :P

Przeczytałem ten kod i nie bardzo rozumiem, po co wyznaczasz tam medianę
ze środkowego i skrajnych elementów listy. Quicksort działa dla 
dowolnego, wybranego do podziału elementu - niekoniecznie środkowego.
W ten sposób parę razy niepotrzebnie biegasz po liście (drop,
reverse). Być może bredzę (czegoś nie zrozumiałem), ale wydaje mi się,
że takie coś również zadziała i to pewnie szybciej:

#v+
rozna_lista2 :: Ord a => [ a ] -> Bool
rozna_lista2 [] = True 
rozna_lista2 l = let m = head l
                     in
                 length ( [a | a <- l, a == m] ) == 1 &&
                 rozna_lista2 [ a | a <- l , a < m ] &&
                 rozna_lista2 [ a | a <- l , a > m ]
#v-

Jest w miarę zwięźle ale biegamy po liście 3 razy. Z akumulatorem byłoby
tylko raz.

-- 
Pasza
JMS dla MIDP - http://jmsme.sf.net
pasza (at) zodiac.mimuw.edu.pl