Skip to content

Instantly share code, notes, and snippets.

@silverprize
Last active August 29, 2015 14:11
Show Gist options
  • Save silverprize/9ffdc1a2dc08ff63c429 to your computer and use it in GitHub Desktop.
Save silverprize/9ffdc1a2dc08ff63c429 to your computer and use it in GitHub Desktop.
Heapsort with clojure
(defn- round [idx]
(int (+ idx 0.5)))
(defn- get-parent-idx [idx]
(dec (round (* idx 0.5))))
(defn- get-left-child-idx [idx]
(inc (* idx 2)))
(defn- get-right-child-idx [idx]
(inc (inc (* idx 2))))
(defn- swap [source idx0 idx1]
(let [tmp (nth source idx0)]
(aset source idx0 (nth source idx1))
(aset source idx1 tmp)))
(defn- move-up [source idx]
(let [parentIdx (get-parent-idx idx)]
(if (> parentIdx -1)
(if (> (nth source idx) (nth source parentIdx))
(do (swap source idx parentIdx) (move-up source parentIdx))))))
(defn- move-down [source len idx]
(let [leftChildIdx (get-left-child-idx idx) rightChildIdx (get-right-child-idx idx)]
(if
(and
(< rightChildIdx len)
(< (nth source leftChildIdx) (nth source rightChildIdx))
(< (nth source idx) (nth source rightChildIdx)))
(do (swap source idx rightChildIdx) (move-down source len rightChildIdx))
; else if
(if
(and
(< leftChildIdx len)
(< (nth source idx) (nth source leftChildIdx)))
(do (swap source idx leftChildIdx) (move-down source len leftChildIdx))))))
(defn- build-heap [source]
(loop [idx 0]
(when (< idx (alength source))
(move-up source idx)
(recur (inc idx)))))
(defn- line-up [source]
(let [end (alength source)]
(loop [idx 1]
(when (< idx end)
(let [len (- end idx)]
(swap source 0 len)
(move-down source len 0)
(recur (inc idx)))))))
(defn heapsort [source]
(if (> (alength source) 1)
(do (build-heap source) (line-up source))))
(load "heapsort")
(defn- make-source [len maxVal]
(let [dest (int-array len)]
(loop [idx 0 end len]
(when (< idx end)
(aset dest idx (rand-int maxVal))
(recur (inc idx) end)))
dest))
(let [source (make-source 10 10)]
(doseq [elem source] (print (str elem ", ")))
(heapsort source)
(println)
(doseq [elem source] (print (str elem ", "))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment