Skip to content

Instantly share code, notes, and snippets.

@podviaznikov
Last active December 26, 2015 06:49
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save podviaznikov/7110626 to your computer and use it in GitHub Desktop.
Save podviaznikov/7110626 to your computer and use it in GitHub Desktop.
Quicksort implemented in Clojure
(defn qpart [data p]
(reduce (fn [acc item]
(cond
(< item p) (assoc acc :left (conj (:left acc) item))
(> item p) (assoc acc :right (conj (:right acc) item))
:else (assoc acc :ps (conj (:ps acc) item))))
{:left [] :right [] :ps []} data))
(defn quicksort [data]
(if (< (count data) 2)
data
(let [pindex (rand-int (count data))
p (nth data pindex)
partitions (qpart data p)
left (quicksort (:left partitions))
right (quicksort (:right partitions))
result (concat left (:ps partitions) right)]
result)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment