···@coolgroups.com writes:
> Suppose the only operators you may use is car, cdr and cons. How do
> you write a sorting algorithm?
You don't?
You need a comparison operator, some kind of conditional,
and some way of iterating or recursing through a structure - at a
minimum.
On Mon, 03 Apr 2006 08:54:10 -0400, Bill Atkins wrote:
> ···@coolgroups.com writes:
>
>> Suppose the only operators you may use is car, cdr and cons. How do
>> you write a sorting algorithm?
>
> You don't?
>
> You need a comparison operator, some kind of conditional,
> and some way of iterating or recursing through a structure - at a
> minimum.
Well, but the later two requirements are matched: one
can iterate/recurse over a structure (cons-build)
with car/cdr. The resulting (sorted) structure can
be build with cons. So what's missing is the sort
predicate and the conditional ...
cheers,
Ralf Mattes
P.S: Homework?
Bill Atkins <············@rpi.edu> writes:
> You need a comparison operator, some kind of conditional, and some
> way of iterating or recursing through a structure - at a minimum.
And then I recommend merge sort: guaranteed O(n log n), and can be
easily implemented on lists.
(There are two basic ways to split: in half of the length, or picking
odd and even elements. Odd/even is slightly easier to write, but
splitting in half allows to make sorting stable.)
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Assuming that you have a comparison operator and at least "if" also,
the basic algorithm would be to take the head of the input list and
then put it into the correct place in the output list, all of which can
be done with car, cdr and cons.
(defun sort (in out)
(if (not in) out)
(sort (cdr in) (insert-in-order (car in) out))))
(defun insert-in-order (element list)....)
insert-in-order just runs through a list and puts 'element' into the
right place.
This sort algorithm will have horrible O() though, I want to say it
will be something like O(n**2)
Brad
···@coolgroups.com wrote:
> Suppose the only operators you may use is car, cdr and cons. How do
> you write a sorting algorithm?
I don't know what you mean with "operators". car, cdr and cons are
functions and if you are allowed to use theses 3 functions, only, and no
other things, like the macro "defun" or "if", you can't write a sorting
algorithm.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> I don't know what you mean with "operators".
In the context of CL, this definition is appropriate:
http://clhs.lisp.se/Body/26_glo_o.htm#operato
Lars Brinkhoff wrote:
> In the context of CL, this definition is appropriate:
>
> http://clhs.lisp.se/Body/26_glo_o.htm#operato
Thanks, I didn't know that.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de