In article <··········@aplcenmp.apl.jhu.edu> ····@aplcenmp.apl.jhu.edu (Marty Hall) writes:
·······@mosaic.nyu.edu (Marco Antoniotti) writes:
> ·······@hertz.njit.edu (Jake Vogelaar) writes:
[...]
> Thanks .. but my intention is to see a lisp routine that does the quick
> sort with chopping and recursion and such. Is this possible?
[...]
>Barry gave the best answer in Common Lisp. If you wan to rewrite it is
>just a trivial adaptation of any Algorithm book.
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.
I agree that if the original poster was talking about sorting arrays
then it is indeed an trivial adaptation of what's in YFAT (Your
Favorite Algorithms Text).
- Marty
(proclaim '(inline skates))
Marty Hall is correct, of course, that using Quicksort on lists is not easy.
The Quicksort described in YFAT moves through the array (it's always an array)
simultaneously from front to back and from back to front. Clearly, this is
difficult with lists.
I don't understand the suggestion in Marty's second paragraph. Here's my idea:
adapt the Quicksort algorithm to go through the array in only one direction,
moving elements to one of two new lists, depending on whether they are bigger or
small than the pivot. This would be true to the Quicksort algorithm and would
result in the right complexity, but would cons a lot. Each item would get moved
roughly \log n times, so the algorithm would cons roughly n\log n new cells.
Clearly, quite a burden on the garbage collector.
Fortunately, we don't need to throw away the cons cells of the original list
while making the two new sublists; we can recycle them right away. This results
in an O(n\log n) Quicksort on lists that does no consing, using a slightly
different algorithm than the one on YFAT.
Even better, IMHO, is Mergesort, which is as efficient on lists as Quicksort,
can also recycle cons cells, so that it does no consing, and has the advantage
that its worst-case performance is O(n\log n), while worst-case performance for
Quicksort is O(n^2). Unfortunately, in the timings I've done, the best case
performance for Quicksort (randomly ordered input) is slightly better.
I have code for both Quicksort and Mergesort, both with and without consing, if
people would like it.
I don't know whether the poster needed lists or arrays. If arrays are
acceptable, it seems to me the best solution is this minor modification of Barry
Margolin's original solution:
(defun sort-file (filename)
(let ((line-array (make-array 100 :fill-pointer 0)))
(with-open-file (s filename)
(loop for line = (read-line s nil nil)
while line
do (vector-push-extend line line-array)))
(setq lines (quicksort line-array #'string-<))
(mapc #'write-line lines)))
(defun quicksort (array &optional (lessp #'<))
;; Fill in from YFAT
)
Scott D. Anderson
········@cs.umass.edu