Difference between revisions of "Quicksort"
BrettGiles (talk | contribs) m (Category) |
|||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
| + | [[Image:Haskelllogo-small-flag-RO-8.jpg|center|Haskell - Quicksort]] |
||
| + | |||
[[Category:Ro]] |
[[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> |
||
| − | < |
+ | <haskell> |
| − | quick :: [Integer] -> [Integer] |
+ | quick :: [Integer] -> [Integer] |
| − | quick [] = [] |
+ | quick [] = [] |
| − | quick (h:t)= quick [ y | y <- t , y < h] ++ [h] ++ quick [ y | y <- t , y > h] </ |
+ | 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 14: | Line 16: | ||
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/Intrebarile_incepatorului <'''-''' Inapoi la Intrebarile incepatorului Ro/Haskell. ] |
||
Revision as of 13:23, 4 October 2008
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.