Insertion Sort in Clojure

In Insertion Sort, insert means search and find the position of current element in partially sorted array and insert it to there, all the elements after that position move forward by one element.

In Clojure, we can implement it using filter to find the elements that less than current element and all the elements that greater than that.

Initial condition of the loop: partial sorted array is empty, the rest part of the list is the whole list. The current element is the second element of the list.

In each loop, partially sorted value contains currently sorted array and the rest is unsorted part.

To observe the contents of them uncomment the debug statements.

The code is listed as below.

 
(defn insertion-sort [a]
  (loop [rest-part a  partial-sorted []]
    ;;(pprint ["rest-part" rest-part])
    ;;(pprint ["partial-sorted" partial-sorted])
    (if (= 1 (count rest-part))
      (concat partial-sorted rest-part)
      (let [before (conj (vec partial-sorted) (first rest-part))
            ;;_ (pprint ["before" before])
            A (second rest-part)
            lesser (filter #(<= % A) before)
            ;;_ (pprint ["lesser" lesser])
            greater (filter #(> % A) before)
      ]
        (recur (cons (last (cons A greater)) (rest (rest rest-part)) )
               (drop-last (concat lesser (cons A greater)))
        )
      )
    )
  )
)
 
(insertion-sort '( 1 4 223 3 2 4 23  45 5  43 3 12 113 1))
 

The output.

 
user> (insertion-sort '( 1 4 223 3 2 4 23  45 5  43 3 12 113 1))
["rest-part" (1 4 223 3 2 4 23 45 5 43 3 12 113 1)]
["partial-sorted" []]
["before" [1]]
["lesser" (1)]
["rest-part" (4 223 3 2 4 23 45 5 43 3 12 113 1)]
["partial-sorted" (1)]
["before" [1 4]]
["lesser" (1 4)]
["rest-part" (223 3 2 4 23 45 5 43 3 12 113 1)]
["partial-sorted" (1 4)]
["before" [1 4 223]]
["lesser" (1)]
["rest-part" (223 2 4 23 45 5 43 3 12 113 1)]
["partial-sorted" (1 3 4)]
["before" [1 3 4 223]]
["lesser" (1)]
["rest-part" (223 4 23 45 5 43 3 12 113 1)]
["partial-sorted" (1 2 3 4)]
["before" [1 2 3 4 223]]
["lesser" (1 2 3 4)]
["rest-part" (223 23 45 5 43 3 12 113 1)]
["partial-sorted" (1 2 3 4 4)]
["before" [1 2 3 4 4 223]]
["lesser" (1 2 3 4 4)]
["rest-part" (223 45 5 43 3 12 113 1)]
["partial-sorted" (1 2 3 4 4 23)]
["before" [1 2 3 4 4 23 223]]
["lesser" (1 2 3 4 4 23)]
["rest-part" (223 5 43 3 12 113 1)]
["partial-sorted" (1 2 3 4 4 23 45)]
["before" [1 2 3 4 4 23 45 223]]
["lesser" (1 2 3 4 4)]
["rest-part" (223 43 3 12 113 1)]
["partial-sorted" (1 2 3 4 4 5 23 45)]
["before" [1 2 3 4 4 5 23 45 223]]
["lesser" (1 2 3 4 4 5 23)]
["rest-part" (223 3 12 113 1)]
["partial-sorted" (1 2 3 4 4 5 23 43 45)]
["before" [1 2 3 4 4 5 23 43 45 223]]
["lesser" (1 2 3)]
["rest-part" (223 12 113 1)]
["partial-sorted" (1 2 3 3 4 4 5 23 43 45)]
["before" [1 2 3 3 4 4 5 23 43 45 223]]
["lesser" (1 2 3 3 4 4 5)]
["rest-part" (223 113 1)]
["partial-sorted" (1 2 3 3 4 4 5 12 23 43 45)]
["before" [1 2 3 3 4 4 5 12 23 43 45 223]]
["lesser" (1 2 3 3 4 4 5 12 23 43 45)]
["rest-part" (223 1)]
["partial-sorted" (1 2 3 3 4 4 5 12 23 43 45 113)]
["before" [1 2 3 3 4 4 5 12 23 43 45 113 223]]
["lesser" (1)]
["rest-part" (223)]
["partial-sorted" (1 1 2 3 3 4 4 5 12 23 43 45 113)]
(1 1 2 3 3 4 4 5 12 23 43 45 113 223)