Hello,
I tried writing a naive implementation of quicksort using an
accumulator. Right now, the code is stack-consuming and returns a
stackoverflowerror on large lists. Is there any way to prevent it from
consuming stack with some changes? The code is as follows -
(declare qsort qsort* partify)
(defn partify
[item coll [less equal greater] acc]
(if (empty? coll)
(qsort* less (concat equal (qsort* greater acc)))
(let [[head & tail] coll]
(cond
(< head item) (recur item tail [(cons head less) equal greater] acc)
(> head item) (recur item tail [less equal (cons head greater)] acc)
:else (recur item tail [less (cons head equal) greater] acc)))))
(defn qsort*
[coll acc]
(if-let [coll (seq coll)]
(partify (first coll) (rest coll) [[] [(first coll)] []] acc)
acc))
(defn qsort
"Perform Quicksort, with apologies to C.A.R. Hoare"
[coll]
(if-let [coll (seq coll)]
(qsort* coll [])
[]))
Regards,
BG
--
Baishampayan Ghose
b.ghose at gmail.com
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
