Note that the whole point of the "real" quicksort is to sort in place with very good constants. In contrast, the commonly encountered functional quicksort-lookalike traverses its input twice, allocates two extra lists / seqs, then appends their sorted versions after recursive calls. Ultimately it ends up as a sort of a mix of the problems of QS and merge sort with a sprinkle of added complexity of its own (O(n^2) worst-case behaviour of QS, allocation overhead of merge sort, extra input traversal thrown in for good measure); better to implement the regular merge sort (that is, split input in half) for a perfectly respectably-performing purely functional, stable sort (with O(n log n) worst-case complexity and guaranteed logarithmic height of the recursion tree, in constrast to QS's O(n^2) and linear height). In Clojure, using vectors + subvec at the splitting stage may help performance (by avoiding unnecessary allocations and simplifying indexing); another approach would be to split the inputs into singletons and then perform repeated traversals to merge adjacent blocks.
Cheers, M. On 8 June 2012 11:21, nicolas.o...@gmail.com <nicolas.o...@gmail.com> wrote: > Stack-overflows in quicksort can mean that you are hitting the worst > case of this algorithm complexity. > (Meaning that you are sorting an array already sorted in one direction > or the other. > In this situation, the size of the recursive call are n - 1 and 0, > instead of being roughly n/2 for both calls. > Which means that: the stack usage is linear and the complexity is quadratic. > ) > > Can you try to shuffle your array first? > > -- > 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 -- 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
