Slow 'quick sort' in clojure

Question

I wrote a quick sort function in clojure, but it runs extremely slow. Sometimes, if the input collection grows lager, it may even overflow the stack?

Anything wrong with my code?

(defn qsort [coll]
  (if (<= (count coll) 1)
    coll
    (let [pivot (last coll)
          head-half (filter #(< % pivot) (drop-last coll))
          tail-half (filter #(>= % pivot) (drop-last coll))]
      (concat (qsort head-half) (vector pivot) (qsort tail-half)))))

I also read the sort function in clojure.core, but it make confused.

01 (defn sort
02   "Returns a sorted sequence of the items in coll. If no comparator is
03   supplied, uses compare. comparator must
04   implement java.util.Comparator."
05   {:added "1.0"
06    :static true}
07   ([coll]
08    (sort compare coll))
09   ([^java.util.Comparator comp coll]
10    (if (seq coll)
11      (let [a (to-array coll)]
12        (. java.util.Arrays (sort a comp))
13        (seq a))
14      ())))

The only place where recursive happens is at line 12. It just swap the two input parameters! Could you please explain to me why this piece of code is runs?

score 2 · Accepted Answer · answered Jun 08 '12 at 07:27

2

(. java.util.Arrays (sort a comp)) this call is to Arrays sort function and not a recursive call to the clojure.core sort function.

Your code is slow because quick sort is a imperative algorithm i.e it is based on concepts of imperative programming like in place array mutation. Your code is fine but the problem is it traverse the collection many times and also many intermediate collections are created.

You can use array and in place array mutation to make your quick sort fast.

answered Jun 08 '12 at 07:27

Ankur

33,367
2
46
72

1

according to clojure doc on :http://clojure.org/java_interop#dot (. instance-expr (method-symbol args*)) and (. instance-expr method-symbol args*) are equivalent. I wonder why there are so many different form for the same thing – qiuxiafei Jun 08 '12 at 07:50
May be a result of legacy baggage :) – Ankur Jun 08 '12 at 07:57

score 2 · Answer 2 · answered Jun 08 '12 at 07:29

Clojure's sort function just uses Java's standard java.util.Arrays/sort method internally; it's not a 100% clojure implementation.

Quicksort isn't really a great match for idiomatic clojure, since it depends on a collection type that has fast O(1) swapping of elements. Also note that in your implementation, you're doing (last coll) and (count coll) every call, where coll is a lazy seq, so both are O(n) - you should be able to improve on the performance by taking that into account ~ probably by using a java Array instead of an immutable seq as the intermediate collection type.

@qiuxiafel - i imagine merge sort would make more sense - you might want to try that. — andrew cooke, Jun 08 '12 at 16:57

score 1 · Answer 3 · edited May 23 '17 at 11:51

The problem for the stack overflow is that you are putting lazy filters on filters recursively. That's explained well here:

Recursive function causing a stack overflow

Regarding your other question: In line 12, that's no call to the clojure sort function, but a call to the Arrays-sort function. In user-code, you'd normally write (java.util.Arrays/sort a comp) instead of the dot-syntax.

score 1 · Answer 4 · answered Jun 08 '12 at 07:31

your qsort is likely spending most of its time allocating objects.

the calls to filter allocate a lazy-cons instance for each number for each pass
the call to concatenation allocates another object for each number

though your version reads more nicely in my opinion

Slow 'quick sort' in clojure

4 Answers4