Naive quick sort in Clojure

I'm learning clojure and wanted to crate my naive quick sort. This implementation cuts array (vector) in half and process them recursively. Issue is that this code happens to throw NullPointerException when array (vector) is of size 1 just at the end of recursion. Why is that ?

(ns qsort)

(defn qsort [arr] 
(println "arr" arr)
(def cnt (count arr))
(def pivotidx (if (> cnt 1)
  (int (/ cnt 2))
  -1
))

(print "pivotidx:" pivotidx " ")
(if (> pivotidx -1)
  ((def pivotval (nth arr pivotidx))
  (println "pivotval:" pivotval " ")
  (def right (filter #(> % pivotval ) arr))
  (def left (filter #(< % pivotval) arr))
  (println "left" left "right" right)
  (concat (qsort left) [pivot开发者_Go百科] (qsort right))
  )
  arr
)
) 


(defn sortme [] (qsort [3 5 8 9 1 7 12 13 2 14 0]))

---

Other answers have already done a good job of describing the "right" way of doing things, which coincidentally also fix your issue. However, your NPE is caused by

((def pivotval (nth arr pivotidx))
 ...more stuff...)

You cannot simply use () to group elements: (foo) in lisp denotes calling the function foo; likewise, ((bar) (foo)) means:

1. Call bar, saving the result as x
2. Call foo. saving the result as y
3. Call the function x with argument y

Because def does not return a function, calling its result with six or seven arguments will cause a problem.

Instead, if you want to group things, you should use the do special form. (do (foo) (bar)) means "call foo, then return the result of calling bar".

---

Just using let instead of def properly does the right thing:

(defn qsort [arr]
(println "arr" arr)
(let 
 [
  cnt (count arr)
  pivotidx (if (> cnt 1) (int (/ cnt 2)) -1)
 ]
(print "pivotidx:" pivotidx " ")

(if (> pivotidx -1) 
 (let
   [
    pivotval (nth arr pivotidx)
    right (filter #(> % pivotval ) arr)
    left (filter #(< % pivotval) arr)
   ] 
 (println "pivotval:" pivotval " ")
 (println "left" left "right" right)
 (concat (qsort left) [pivotval] (qsort right))
 )
 arr) ))

And then

(qsort [3 5 8 9 1 7 12 13 2 14 0])

returns:

(0 1 2 3 5 7 8 9 12 13 14)

---

(defn qsort
  [l]
  (cond
    (empty? l) '()
    :else (let [f (first l)
                smaller (filter #(<= % f) (rest l))
                bigger (filter #(> % f) (rest l))]
            (concat (qsort smaller) [f] (qsort bigger)))))

---

It looks like if array is length 1 then:

• pivotidx will be 0
• pivotval will be the first (only) item
• right and left will therefore both be empty (nil)
• hence you get a null pointer exception on the next recursion (probably when you try to count the length of nil....)

Some tips / other bugs to fix

• Put the test for nil or empty lists at the beginning of the function
• Don't use def inside a function - use (let [name value] ...) instead
• I think your partitioning logic will miss out duplicates of the pivot - woth checking this case!
• Not sure why you are taking the pivot value to be in the middle of the array, it's usually easiest just to use (first arr) as the pivot. The obnly case you want to pick the middle value is where you know the data is already nearly sorted....