Quicksort
Från Unix.se, den fria unixresursen.
Quicksort är en sorteringsalgoritm för jämförelsebaserad sortering som bygger på algoritmkonstruktionsmönstret dekomposition. Den beskrevs först av C. A. R. Hoare på 60-talet. Quicksort använder i genomsnitt Θ(n log n) jämförelser för att sortera n element. I värsta fall krävs dock Θ(n2) jämförelser, vilket gör att Quicksort i teorin är ett sämre val än Mergesort eller Heapsort. Med vissa modifikationer till algoritmen kan dock det teoretiska värsta fallet förbättras.
| Innehåll |
[edit]
Modifikationer
Man brukar använda medianen av tre (första, mittersta, sista) för att minska risken att uppnå Θ(n2) jämförelser, något som kan inträffa om elementen redan är sorterade vid inmatning. Ännu bättre ur värstafallssynpunkt är att använda Select.
[edit]
Implementationer
[edit]
Prolog
qsort(L,S):-qs(L,[],S). qs([],A,A). qs([H|T],A,S):-pivoting(H,T,L1,L2),qs(L1,A,S1),qs(L2,[H|S1],S)
[edit]
Lisp
(defun qsort (lst &aux (h (pop lst)))
(macrolet ((f (x) `(qsort (remove-if (lambda (z) (,x z h)) lst))))
(when h `(,@(f >=) ,h ,@(f <)))))
[edit]
Haskell
qsort [] = [] qsort (h:t) = qsort (filter (<h) t) ++ [h] ++ qsort (filter (>=h) t)
[edit]
J
qsort =: ]`(($:@:((}.<:{.)#}.)),{.,($:@:((}.>{.)#}.)))@.(*@#)
[edit]
O'Caml
let rec quicksort = function
[] -> []
| e :: es ->
let left, right = List.partition (function x -> x > e) es in
(quicksort left) @ e :: (quicksort right)
;;
