Personal tools

Quicksort

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
  +
[[Image:Haskelllogo-small-flag-RO-8.jpg|center|Haskell - Quicksort]]
  +
  +
[[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>
<nowiki>
+
<haskell>
   
quick :: [Integer] -> [Integer] </nowiki> <br> <nowiki>
+
quick :: [Integer] -> [Integer]
quick [] = [] </nowiki> <br> <nowiki>
+
quick [] = []
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] </haskell>
   
 
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:
 
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:
Line 12: Line 15:
   
 
Versiunile Quicksort-ului in Pascal, C , C++, Java si alte "C-like languages" sunt cam de 10 ori mai lungi !!!
 
Versiunile Quicksort-ului in Pascal, C , C++, Java si alte "C-like languages" sunt cam de 10 ori mai lungi !!!
  +
  +
P.S. Ei bine am exagerat putin, adevaratul Quicksort ar trebui sa aleaga intai pivotul apoi sa faca apelul recursiv. Oricum, in Haskell multe programe se pot scrie repede, inclusiv algoritmi ca cel de mai sus, deoarece beneficiem de acele liste descrise in stilul multimilor de la matematica.
  +
  +
----
  +
Pagina indexata la indexul [[Category:Ro]] [http://www.haskell.org/haskellwiki/Category:Ro Categories:Ro]
  +
----
  +
[http://www.haskell.org/haskellwiki/Ro/Haskell <= Inapoi la pagina principala Ro/Haskell. ]<br> <br>
  +
[http://www.haskell.org/haskellwiki/Intrebarile_incepatorului <'''-''' Inapoi la Intrebarile incepatorului Ro/Haskell. ]

Latest revision as of 13:23, 4 October 2008

Haskell - Quicksort

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

P.S. Ei bine am exagerat putin, adevaratul Quicksort ar trebui sa aleaga intai pivotul apoi sa faca apelul recursiv. Oricum, in Haskell multe programe se pot scrie repede, inclusiv algoritmi ca cel de mai sus, deoarece beneficiem de acele liste descrise in stilul multimilor de la matematica.


Pagina indexata la indexul Categories:Ro


<= Inapoi la pagina principala Ro/Haskell.

<- Inapoi la Intrebarile incepatorului Ro/Haskell.