Skip to content

Instantly share code, notes, and snippets.

@jethrokuan
Created November 26, 2015 11:45
Show Gist options
  • Save jethrokuan/2a18238012521e0edc30 to your computer and use it in GitHub Desktop.
Save jethrokuan/2a18238012521e0edc30 to your computer and use it in GitHub Desktop.
Clojure lazy QS
(defn sort-parts
"Lazy, tail-recursive, incremental quicksort. Works against
and creates partitions based on the pivot, defined as 'work'."
[work]
(lazy-seq
(loop [[part & parts] work]
(if-let [[pivot & xs] (seq part)]
(let [smaller? #(< % pivot)]
(recur (list*
(filter smaller? xs)
pivot
(remove smaller? xs)
parts)))
(when-let [[x & parts] parts]
(cons x (sort-parts parts)))))))
(defn qsort [xs]
(sort-parts (list xs)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment