Difference between revisions of "Quicksort"
Jump to navigation
Jump to search
m |
BrettGiles (talk | contribs) m (Category) |
||
Line 1: | Line 1: | ||
+ | [[Category:Ro]] |
||
Cea mai scurta implementare de algoritm Quicksort <br> |
Cea mai scurta implementare de algoritm Quicksort <br> |
||
se poate face in Haskell astfel: <br> <br> |
se poate face in Haskell astfel: <br> <br> |
Revision as of 21:23, 23 June 2007
Cea mai scurta implementare de algoritm Quicksort
se poate face in Haskell astfel:
quick :: [Integer] -> [Integer]
quick [] = []
quick (h:t)= quick [ y | y <- t , y < h] ++ [h] ++ quick [ y | y <- t , y > h]
Matematicienii vor recunoaste imediat ideea care l-a inspirat: Daca separam primul element dintr-o lista (multime ordonata) restul se poate sorta sortand recursiv multimea elementelor mai mici si a celor mai mari ca el. Apoi e suficient sa concatenam aceste multimi ordonate:
{ y | y <- t , y < h }
{h}
{ y | y <- t , y > h}
Versiunile Quicksort-ului in Pascal, C , C++, Java si alte "C-like languages" sunt cam de 10 ori mai lungi !!!