On Wed, Dec 29, 2010 at 11:14 AM, Andreas Kostler
<[email protected]> wrote:
> Hi all,
> I've implemented a recursive version of insertion sort as a bit of an warm up
> with clojure. For some reason it just doesn't "feel" right. The recursion
> feels forced on poor old insertion sort. This might be inherent to insertion
> sort.
> My poor clojure skills are more likely to blame, though.
> Can I please get some feedback on how to address the problem in a more
> idiomatic way?
>
> ; Inserts element into a sorted vector
> (defn insert-into [sorted-vec element]
> (loop [i (count sorted-vec)]
> (if (and (> i 0) (> (nth sorted-vec (dec i)) element))
> (recur (dec i))
> (into (conj (subvec sorted-vec 0 i) element) (subvec
> sorted-vec i)))))
>
>
> (defn insertion-sort [vector]
> (loop [i 0
> _vec vector]
> (if (< i (count _vec))
> (recur (inc i)
> (into (insert-into (subvec _vec 0 i) (nth _vec i))
> (subvec _vec (inc i))))
> _vec)))
>
> Kind Regards
> Andreas
Vectors are actually rather poorly designed for that sort of thing
(insertion in the middle) and loop is generally to be resorted to only
if there isn't a higher-order function that will do the job. How
about:
(defn insert-into [s x]
(let [[low high] (split-with #(< % x) s)]
(concat low [x] high)))
(defn insertion-sort [s]
(reduce insert-into [] s))
Here, split-with and reduce are the HOFs that obviate the need for loop.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
