Ken, I agree with your analysis, and of course, you are right that
this is only interesting as an exercise, because obviously there are
better ways to sort.
I agree:
1. reducing with the reverse of the list is one way to get a stable
sort. Another possibility is to alter the insert method so that an
equal item gets inserted at the end of a batch of equal items.
2. Your new insertion function is a reasonable way to get rid of the
laziness that breaks the function for large inputs.
Another, slightly clearer and faster way:
(defn insert [n alon]
(loop [alon alon, result []]
(cond
(empty? alon) (conj result n)
(<= n (first alon)) (into result (cons n alon))
:else (recur (rest alon) (conj result (first alon))))))
(Also, as you point out, the above could be further sped up with transients).
However, it should be pointed out that even this latest version
doesn't share all the performance characteristics of the classic
functional insertion sort given at the Htdp link. Specifically, one
of the (few) great things about insertion sort is that it is blazingly
fast on input lists that are already sorted, or nearly sorted. As a
challenge (to you or Andreas, or anyone who is interested in this
thread), figure out why the original insertion sort works so quickly
on sorted lists, why the above code does not, and then try to
duplicate that performance characteristic with an insertion sort
algorithm in Clojure.
One lesson here: Sometimes Clojure/Java's stack limitations hurt, a
lot. It's a lot harder to transform this algorithm than it ideally
should be.
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
