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.