On Thu, Dec 30, 2010 at 12:51 AM, Andreas Kostler
<[email protected]> wrote:
> Now the discussion evolved around vectors not being suitable for this task.
> Can someone explain why this holds in this context? In my understanding
> subvec is a constant time operation. So maybe vector is not that unsuitable
> for this task after all?
I agree. vector seems like a perfectly reasonable choice, especially
in light of the difficulties that sequences present in implementing
this algorithm. Your implementation of insert-into looks okay to me.
I was mainly balking at your implementation of insertion-sort, which
still seems a bit strange to me, but you can probably mix something
like Ken's reduce technique with your vector-based insert-into with
good results.
So combining the two, you get something like:
(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 [s]
(reduce insert-into [] s))
which is a perfectly reasonable implementation. By my benchmarking,
it's slightly slower than my complicated sequence-based version, but
it's in the same ballpark. It's easy to understand and furthermore,
it doesn't blow the stack and it's quick on already sorted lists.
--
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
