Quick Sort in LISP?
Jake Vogelaar
sorts it using quick sort and spits the answer to stdout?
thanks,
-jake
--
/////////////////////////////-----Jake Vogelaar-----\\\\\\\\\\\\\\\\\\\\\\\\\\
| jxv...@hertz.njit.edu - New Jersey Institute of Technology, Newark NJ |
| jake.v...@basf-corp.com - TDG, BASF Corporation, Parsippany NJ |
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\///////////////////////////////////////
Barry Margolin
>Does anyone have/or know of some lisp source that takes a text file,
>sorts it using quick sort and spits the answer to stdout?
Does it really have to be quicksort? Common Lisp has a built-in SORT
function, but it's not required to use any particular sorting algorithm.
(defun sort-file (filename)
(let ((lines
(with-open-file (s filename)
(loop for line = (read-line s nil nil)
while line collect line))))
(setq lines (sort lines #'string-<))
(mapc #'write-line lines)))
--
Barry Margolin
BBN Internet Services Corp.
bar...@near.net
Jake Vogelaar
Barry Margolin <bar...@nic.near.net> wrote:
>In article <36p2vv$h...@basfigw.basf-corp.com> vog...@nntp.basf-corp.com (Jake Vogelaar) writes:
>>Does anyone have/or know of some lisp source that takes a text file,
>>sorts it using quick sort and spits the answer to stdout?
>
>Does it really have to be quicksort? Common Lisp has a built-in SORT
>function, but it's not required to use any particular sorting algorithm.
>
sort with chopping and recursion and such. Is this possible?
-jv
--
/////////////////////////////-----Jake Vogelaar-----\\\\\\\\\\\\\\\\\\\\\\\\\\
| jxv...@hertz.njit.edu - New Jersey Institute of Technology, Newark NJ |
| jake.v...@basf-corp.com - TDG, BASF Corporation, Parsippany NJ |
| http://hertz.njit.edu/~jxv3790 - My Place on the Web |
Marco Antoniotti
Newsgroups: comp.lang.lisp
From: jxv...@hertz.njit.edu (Jake Vogelaar)
Sender: ne...@njit.edu
Nntp-Posting-Host: hertz.njit.edu
Organization: New Jersey Institute of Technology, Newark, New Jersey
References: <36p2vv$h...@basfigw.basf-corp.com> <36pc4q$1...@tools.near.net>
Date: Tue, 4 Oct 1994 14:00:04 GMT
Lines: 19
In article <36pc4q$1...@tools.near.net>,
Barry Margolin <bar...@nic.near.net> wrote:
>In article <36p2vv$h...@basfigw.basf-corp.com> vog...@nntp.basf-corp.com (Jake Vogelaar) writes:
>>Does anyone have/or know of some lisp source that takes a text file,
>>sorts it using quick sort and spits the answer to stdout?
>
>Does it really have to be quicksort? Common Lisp has a built-in SORT
>function, but it's not required to use any particular sorting algorithm.
>
Thanks .. but my intention is to see a lisp routine that does the quick
sort with chopping and recursion and such. Is this possible?
-jv
Barry gave the best answer in Common Lisp. If you wan to rewrite it is
just a trivial adaptation of any Algorithm book.
--
Marco Antoniotti - Resistente Umano
-------------------------------------------------------------------------------
Robotics Lab | room: 1220 - tel. #: (212) 998 3370
Courant Institute NYU | e-mail: mar...@cs.nyu.edu
...e` la semplicita` che e` difficile a farsi.
...it is simplicity that is difficult to make.
Bertholdt Brecht
Marty Hall
> jxv...@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))
Mark S. Riggle
In article <Cx79r...@aplcenmp.apl.jhu.edu>, ha...@aplcenmp.apl.jhu.edu (Marty Hall) writes:
|> mar...@mosaic.nyu.edu (Marco Antoniotti) writes:
|> > jxv...@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.
|>
An aside here. The internal implementation of the sort function
in Common Lisp cannot be a quicksort since it is an unstable sort
and a stable sort is specified.
--
=========================================================
Mark Riggle | "Give me LAMBDA or
sas...@unx.sas.com | give me death"
SAS Institute Inc., |
SAS Campus Drive, Cary, NC, 27513 |
(919) 677-8000 |
Cyber Surfer
bar...@nic.near.net "Barry Margolin" writes:
> (defun sort-file (filename)
> (let ((lines
> (with-open-file (s filename)
> (loop for line = (read-line s nil nil)
> while line collect line))))
> (setq lines (sort lines #'string-<))
> (mapc #'write-line lines)))
It could also be done using the series functions:
(defun sort-file (filename)
(let ((lines (collect (scan-file filename #'read-line))))
(mapc #'write-line (sort lines #'string-<))))
The series functions aren't a part of CL, of course, but they
can be found in the Lisp Repository.
--
"Internet? What's that?" -- Simon "CompuServe" Bates
http://cyber.sfgate.com/examiner/people/surfer.html
Fernando Mato Mira
> The series functions aren't a part of CL, of course, but they
> can be found in the Lisp Repository.
Of course? I don't know why they have not been included, given:
>>>>
;Copyright Massachusetts Institute of Technology, Cambridge, Massachusetts.
;Permission to use, copy, modify, and distribute this software and its
;documentation for any purpose and without fee is hereby granted,
;provided that this copyright and permission notice appear in all
;copies and supporting documentation, and that the name of M.I.T. not
;be used in advertising or publicity pertaining to distribution of the
;software without specific, written prior permission. M.I.T. makes no
;representations about the suitability of this software for any
;purpose. It is provided "as is" without express or implied warranty.
>>>>
So SERIES would not be a barrier for somebody trying to implement
a compliant CL compiler.
As of now, chances are SERIES will end up dying, as:
a. CL implementors do not maintain, or try to improve the package.
b. Few people care about taking the time to learn how to use it.
a) and the fact that it is an add-on are probably the greatest
reasons for this.
--
F.D. Mato Mira
Computer Graphics Lab mato...@epfl.ch
EPFL FAX: +41 (21) 693-5328
Barry Margolin
>An aside here. The internal implementation of the sort function
>in Common Lisp cannot be a quicksort since it is an unstable sort
>and a stable sort is specified.
Common Lisp has two functions, SORT and STABLE-SORT. Only the latter is
required to be stable.
Scott D. Anderson
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
ande...@cs.umass.edu
Henry G. Baker
>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.
Marty Hall
>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))
Barry Margolin
>In article <781370...@wildcard.demon.co.uk>, cyber_...@wildcard.demon.co.uk (Cyber Surfer) writes:
>> The series functions aren't a part of CL, of course, but they
>> can be found in the Lisp Repository.
>Of course? I don't know why they have not been included, given:
...
>So SERIES would not be a barrier for somebody trying to implement
>a compliant CL compiler.
It had nothing to do with implementation ease. The Series facility wasn't
included in pANS CL for various reasons:
1) It wasn't in widespread use, so we weren't sure it was appropriate to
standardize it at the time that it was proposed to us. To the extent
possible, a standards committee's job is to codify common practice, not
introduce major new functionality (CLOS and the condition system were
exceptions, explicitly identified in the X3J13 charter).
2) The specification was in flux, as it was being merged with the
Iterate/Gather facility.
>As of now, chances are SERIES will end up dying, as:
> a. CL implementors do not maintain, or try to improve the package.
> b. Few people care about taking the time to learn how to use it.
> a) and the fact that it is an add-on are probably the greatest
> reasons for this.
Documentation of Series was included in CLtL2 *specifically* to encourage
people to use it. There are lots of things in many CL implementations that
aren't in the pANS. The standard should not be viewed as *limiting*
implementors.
Furthermore, the availability of a free, portable implementation means that
users aren't dependent on the vendors to provide this facility.
J W Dalton
a homework exercise or something?
Jens Kilian
Marty> to write a quicksort algorithm on *lists* in Lisp.
Who would *want* to use quicksort on lists, when he knows about merge sort?
Marty> Some solutions involve using an intermediate tree structure where you
Marty> don't append the pieces, then making one sweep (O(N)) through at the
Marty> end to put it all together, [...]
How big are the space requirements for that solution?
Greetings,
Jens.
--
Internet: je...@hpbbn.bbn.hp.com | Phone: (0|+49)7031-14-4785 (TELNET 778-4785)
MausNet: Jens Kilian @ BB | Fax : (0|+49)7031-14-2049
---------------------------------+---------------------------------------------
As the air to a bird, or the sea to a fish, so is contempt to the contemptible.
Fernando Mato Mira
> Documentation of Series was included in CLtL2 *specifically* to encourage
> people to use it. There are lots of things in many CL implementations that
> aren't in the pANS. The standard should not be viewed as *limiting*
> implementors.
>
> Furthermore, the availability of a free, portable implementation means that
> users aren't dependent on the vendors to provide this facility.
I know, but I recall somebody talking about an application written using
SERIES that was `a dog to optimize'. Have you looked at the source code?
If somebody here could explain all that frag stuff that would be most useful.
--
F.D. Mato Mira http://ligwww.epfl.ch/matomira.html
Cyber Surfer
mato...@di.epfl.ch "Fernando Mato Mira" writes:
> Of course? I don't know why they have not been included, given:
I don't know either, but that's what I recall reading in c.l.l.
> So SERIES would not be a barrier for somebody trying to implement
> a compliant CL compiler.
I know. That's why I was plugging the series functions. ;-)
> As of now, chances are SERIES will end up dying, as:
> a. CL implementors do not maintain, or try to improve the package.
> b. Few people care about taking the time to learn how to use it.
> a) and the fact that it is an add-on are probably the greatest
> reasons for this.
Yet another reason for me plugging them. I'd much rather SCAN and
COLLECT than LOOP. I hope we've sparked a little more interest in
series functions.