qsort.clj

#!/usr/bin/clojure
; Created: Mon Jul  6 21:45:57 EEST 2015
; encoding: utf-8
(defn qsort [[pivot & rest*]] 
  (when pivot
    (let [smaller #(< % pivot)]
      (lazy-cat (qsort (filter smaller rest*))
                [pivot]
                (qsort (remove smaller rest*))))))

(defn qsort2 [[pivot & rest*]]
  (when pivot
    (let [[l r] (->> rest*
                  (reduce (fn [[lt ge] i] (if (< i pivot)
                                          [(conj lt i) ge]
                                          [lt (conj ge i)]))
                          [[] []]))]
      (lazy-cat (qsort l) [pivot] (qsort r)))))

(defn qsort3 [[pivot & rest*]]
  (when pivot
    (let [smaller #(< % pivot)
          g (group-by smaller rest*)
          l (get g true)
          r (get g false)]
      (lazy-cat (qsort l) [pivot] (qsort r)))))


(defmacro measure [f]
  (let [before (System/currentTimeMillis)]
    ~f
    (let [after (System/currentTimeMillis)]
      (println (str (- after before))))))

(def a (shuffle (range (* 100 1000))))
(prn
  (time
    (qsort a)))


(prn
  (time
    (qsort2 a)))


(prn
  (time
    (qsort3 a)))