And also qsort may take up to n stack frames for collection of n elements if you partition function is not optimal. In your case - if input collection is sorted (as long as you split by first element).
On Tue, Dec 28, 2010 at 11:13 PM, Petr Gladkikh <petrg...@gmail.com> wrote: > Why do you call qsort* inside of partify? I do not really grasp your > logic behind this. > > On Tue, Dec 28, 2010 at 8:20 PM, Baishampayan Ghose <b.gh...@gmail.com> wrote: >> 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 clojure@googlegroups.com >> Note that posts from new members are moderated - please be patient with your >> first post. >> To unsubscribe from this group, send email to >> clojure+unsubscr...@googlegroups.com >> For more options, visit this group at >> http://groups.google.com/group/clojure?hl=en > > > > -- > Petr Gladkikh > -- Petr Gladkikh -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
