Last active
December 25, 2015 13:09
-
-
Save podviaznikov/6981645 to your computer and use it in GitHub Desktop.
Bubble sort implementation in Clojure.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defn bubble-step [coll was-changed less?] | |
(if (second coll) | |
(let [[x1 x2 & xs] coll | |
is-less-than (less? x1 x2) | |
smaller (if is-less-than x1 x2) | |
larger (if is-less-than x2 x1) | |
is-changed (or was-changed (not is-less-than)) | |
[sorted is-sorted] (bubble-step (cons larger xs) is-changed less?)] | |
[(cons smaller sorted) is-sorted]) | |
[coll (not was-changed)])) | |
(defn bubble-sort [coll less?] | |
(loop [[coll is-sorted] [coll false]] | |
(if is-sorted | |
coll | |
(recur (bubble-step coll is-sorted less?))))) | |
(bubble-step [40 32 1 300] false <) | |
(bubble-step [1 2 3] false <) | |
(bubble-sort [40 32 1 300] <) | |
(bubble-sort [1 2 3 4 5 6] <) | |
(comment | |
;step1 | |
[40 32 1 300] | |
smaller 32 | |
larger 40 | |
xs [1 300] | |
was-changed true | |
;step2 | |
[40 1 300] | |
smaller 1 | |
larger 40 | |
xs [300] | |
was-changed true | |
;step3 | |
[40 300] | |
smaller 40 | |
larger 300 | |
xs [] | |
was-changed false | |
[40 300] false | |
[1 40 300] true | |
[32 1 40 300] true | |
) | |
(comment | |
;step1 | |
[1 2 3 4] | |
smaller 1 | |
larger 2 | |
xs [3 4] | |
was-changed false | |
;step2 | |
[2 3 4] | |
smaller 2 | |
larger 3 | |
xs [4] | |
was-changed false | |
;step3 | |
[3 4] | |
smaller 3 | |
larger 4 | |
xs [] | |
was-changed false | |
[3 4] false | |
[2 3 4] false | |
[1 2 3 4] false | |
) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment