Personal tools

Quicksort

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m
m
Line 7: Line 7:
 
quick (h:t)= quick [ y | y <- t , y < h] ++ [h] ++ quick [ y | y <- t , y > h] </nowiki> <br>
 
quick (h:t)= quick [ y | y <- t , y < h] ++ [h] ++ quick [ y | y <- t , y > h] </nowiki> <br>
   
Versiunile in Pascal, C , C++, Java si alte "C-like languages" sunt cam de 10 ori mai lungi.
+
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 } <br> {h} <br> { 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 !!!

Revision as of 23:12, 19 December 2006

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 !!!