What would be a good way to implement quicksort in clojure (or any persistent language)? I mean, not just something that works or has the right theoretical runtime. I've thought about just looking to see how sort was implemented in clojure, but I don't know if it would get to my point once I found out -- for all I know heapsort is way better in such pointer-machine-like environments (that's how I think of it, at least).
So I know about the way Haskell intros do it: *recursively concatenate the quicksort of everything less than a pivot with the pivot, and append the quicksort of everything greater than the pivot to the end of that. That gets you the right answer, but it is pointed out (for example here: http://augustss.blogspot.com/2007/08/quicksort-in-haskell-quicksort-is.html) that the preferred, elegant, in place partition algorithm (that I think I read Knuth came up with?) is noteworthy, starting from both ends and walking toward the middle, swapping as you go. I admire Lennart Augustsson for doing that exercise -- whatever the controversy surrounding it might be (did he show Haskell can be just as serious as C, or did he defeat the point of high-level languages? . . . .etc, etc.) Now in clojure, I could just use var-set and var-get, like folks helped me (on my stubbornness) to get going here, but what should I do, short of * above? One interesting answer I came up with was to step back and say, "HOLD IT. This language was built with concurrency in mind. You don't make your money doing it the single threaded way. just use C for that." So I'm even considering (but not limiting the challenge to) parallel approaches. In such an environment it might be ok to do a little extra work . . . maybe make some extra copies, etc., because of the speedups. Step one could start with one thread that spawns a thread (agent here?) for each partition (those in turn doing the same thing) and when those answers come back, the sort it done. I may do the parallel route to understand the thread model, but is there something simple, also, as to the best way to think about quicksort in clojure? I could see something like this adding to Tim's examples page. Thanks. --~--~---------~--~----~------------~-------~--~----~ 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 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 -~----------~----~----~----~------~----~------~--~---
