Name: Anonymous 2013-03-05 19:43
Write a QuickSort implementation. Here are a few examples...
Symta:
J:
Factor:
Haskell:
Symta:
quicksort<H@T>=<@T[?≤H],r H@T[?≥≥H],r>J:
quicksort=:(($:@(<#[),(=#[),$:@(>#[))({~ ?@#))^:(1<#)Factor:
: qsort ( seq -- seq )
dup empty? [
unclip [ [ < ] curry partition [ qsort ] bi@ ] keep
prefix append
] unless ;Haskell:
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
quicksort (p:xs) = quicksort [x | x<-xs, x<p] ++ [p] ++ quicksort [x | x<-xs, x>=p]
(define (split-by l p k)
(let loop ((low '())
(high '())
(l l))
(cond ((null? l)
(k low high))
((p (car l))
(loop low (cons (car l) high) (cdr l)))
(else
(loop (cons (car l) low) high (cdr l))))))
(define (quicksort l gt?)
(if (null? l)
'()
(split-by (cdr l)
(lambda (x) (gt? x (car l)))
(lambda (low high)
(append (quicksort low gt?)
(list (car l))
(quicksort high gt?))))))
(quicksort '(1 3 5 7 9 8 6 4 2) >)