In article <··········@aplcenmp.apl.jhu.edu> ····@aplcenmp.apl.jhu.edu (Marty Hall) writes:
>Actually, IMHO it is not quite that trivial, especially for beginners,
>to write a quicksort algorithm on *lists* in Lisp. Unfortunately many
>people forget to account for the O(N) time required to access the Nth
>entry of the list or to APPEND when there are N entries in the first
>list, and end out with an O(N^2 lg N) average case algorithm (O(N^3)
>worst case). Hardly an achievement in sorting :-).
>
>Some solutions involve using an intermediate tree structure where you
>don't append the pieces, then making one sweep (O(N)) through at the
>end to put it all together, or simply copying the list to an array,
>sorting the array, and copying it back. But, especially on shorter
>lists, this reduces the main advantage of Quicksort, which is that it
>has low constant factors as compared to most other O(N lg N) sorting
>algorithms. I would in fact be interested in seeing some good
>implementations if anybody had them lying around.
Both vector and list versions of Quicksort in Lisp are discussed in:
"A 'Linear Logic' Quicksort". ACM Sigplan Notices 29,2 (Feb. 1994), 13-18.
Also available in my ftp directory in compressed Postscript (.ps.Z) form.
Henry Baker
Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.
In article <················@netcom.com> ······@netcom.com (Henry G. Baker) writes:
>Both vector and list versions of Quicksort in Lisp are discussed in:
>
>"A 'Linear Logic' Quicksort". ACM Sigplan Notices 29,2 (Feb. 1994), 13-18.
>
>Also available in my ftp directory in compressed Postscript (.ps.Z) form.
>
> Henry Baker
> Read ftp.netcom.com:/pub/hbaker/README for info on ftp-able papers.
I hadn't gotten to that paper yet, but I want to reiterate what an
earlier poster said, that the papers here are a great resource. I
highly recommend them. (Thanks!)
- Marty
(proclaim '(inline skates))
····@aplcenmp.apl.jhu.edu