Does anyone have any ideas on how to sort a list of 10 numbers using
only recursion? We are not permitted to use loops or the built in sort
functions of lisp.
In article <················@linuxfreemail.com>,
Denzil Kelly <·······@earthlink.net> wrote:
>Does anyone have any ideas on how to sort a list of 10 numbers using
>only recursion? We are not permitted to use loops or the built in sort
>functions of lisp.
The quicksort algorithm is recursive. Look it up in any algorithms
textbook.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
"Barry Margolin" <······@genuity.net> wrote in message
·····················@paloalto-snr1.gtei.net...
> In article <················@linuxfreemail.com>,
> Denzil Kelly <·······@earthlink.net> wrote:
> >Does anyone have any ideas on how to sort a list of 10 numbers using
> >only recursion? We are not permitted to use loops or the built in sort
> >functions of lisp.
>
> The quicksort algorithm is recursive. Look it up in any algorithms
> textbook.
Sorry, Barry, I think the quicksort algorithm uses comparison and
conditional transposition as well as recursion and the original
poster wanted `only recursion'.
Denzil Kelly wrote:
>
> Does anyone have any ideas on how to sort a list of 10 numbers using
> only recursion?
Yes. :)
> We are not permitted to use loops or the built in sort
> functions of lisp.
Just think a little about it.
You have to use recursion, so you need to decide what to recurse on.
Since you operate on lists, that will probably be an element of the
list. Many recursive algorithms on lists recurse on the CAR of the list,
but for a sort that doesn't seem very easy. The element you choose needs
to be of useful for a sort, and not many elements fulfill that
condition...
Feel free to post any further reflexion you have about that. It should
be quite easy to arrive to a simple (i.e. inefficient :) solution (mine
takes 4 lines and is very straightforward).
--Matthieu
Here is what I came up with, but it doesn't seem to work fully.
;;the following 2 functions are used to find the largest value on the
;;list.. the second
;;function assumes that all the values on the list are positive. it
;;seems to work well
(defun findmax(l) (max1 l 0))
(defun max1(l candidate)
(cond((null l) candidate)
(((car l) candidate)(max1(cdr l) (car l)))
(t (max1 (cdr l) candidate))))
;;this function removes the largest value off of a given list and
;;returns the list
(defun findandremove(candidate list)
(cond((null list)nil)
((= candidate (car list))(findandremove candidate (cdr list)))
(t (cons(car list)
(findandremove candidate (cdr list))))))
;;this is where is progam falls apart. this function should move the
;;largest value to the front
;;of a list, but it doesn't work
(defun maxtofront(list)
(cons (largest list) (findandremove (largest list) list)))
;;I dont' understand why this works and the function immediately above
;;doesnt
;(cons (largest '(1 2 3 4 5 6)) (findandremove (findmax '(1 2 3 4 5 6))
;'(1 2 3 4 5 6)))
;;I had hoped to use this function to give the sorted list(in descending
;;order).
(defun sortalist(list)
(cond((null list) nil)
(t (cons (car (maxtofront list) (sortalist (cadr (maxtofront
list)))))))
Matthieu Villeneuve wrote:
>Denzil Kelly wrote:
>
>>Does anyone have any ideas on how to sort a list of 10 numbers using
>>only recursion?
>>
>
>Yes. :)
>
>>We are not permitted to use loops or the built in sort
>>functions of lisp.
>>
>
>Just think a little about it.
>You have to use recursion, so you need to decide what to recurse on.
>Since you operate on lists, that will probably be an element of the
>list. Many recursive algorithms on lists recurse on the CAR of the list,
>but for a sort that doesn't seem very easy. The element you choose needs
>to be of useful for a sort, and not many elements fulfill that
>condition...
>
>Feel free to post any further reflexion you have about that. It should
>be quite easy to arrive to a simple (i.e. inefficient :) solution (mine
>takes 4 lines and is very straightforward).
>
>
>--Matthieu
>
"Denzil L. Kelly" <·······@earthlink.net> writes:
> Here is what I came up with, but it doesn't seem to work fully.
> ;;the following 2 functions are used to find the largest value on the
> ;;list.. the second
> ;;function assumes that all the values on the list are positive. it
> ;;seems to work well
> (defun findmax(l) (max1 l 0))
Actually, I assume that this function simply assumes that at least one
member of the list is >= 0. You can easily remove this restriction by
using the first element of the list instead of hard-coding the zero.
Then the only assumptions are that elements are numeric and that there
is at least one element.
(defun findmax (l) (max1 l (first l)))
> (defun max1(l candidate)
> (cond((null l) candidate)
> (((car l) candidate)(max1(cdr l) (car l)))
^^^^^^^^^^^^^^^^^^^
This is a malformed expression. I presume it should be
(> (car l) candidate)
> (t (max1 (cdr l) candidate))))
>
> ;;this function removes the largest value off of a given list and
> ;;returns the list
>
> (defun findandremove(candidate list)
> (cond((null list)nil)
> ((= candidate (car list))(findandremove candidate (cdr list)))
> (t (cons(car list)
> (findandremove candidate (cdr list))))))
>
> ;;this is where is progam falls apart. this function should move the
> ;;largest value to the front
> ;;of a list, but it doesn't work
How does it fail to work? What are the symptoms?
> (defun maxtofront(list)
> (cons (largest list) (findandremove (largest list) list)))
Is LARGEST the same as FINDMAX ?
> ;;I dont' understand why this works and the function immediately above
> ;;doesnt
>
> ;(cons (largest '(1 2 3 4 5 6)) (findandremove (findmax '(1 2 3 4 5 6))
> ;'(1 2 3 4 5 6)))
>
> ;;I had hoped to use this function to give the sorted list(in descending
> ;;order).
> (defun sortalist(list)
> (cond((null list) nil)
> (t (cons (car (maxtofront list) (sortalist (cadr (maxtofront
> list)))))))
You can make this a bit less complicated by combining the MAXTOFRONT
logic with the recursion in this function. It will eliminate the need
to cons a return value and then take it apart. (It will also make it
less likely that you will take the return value apart incorrectly and
have an error in your program.)
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu
In article <················@earthlink.net>,
Denzil L. Kelly <·······@earthlink.net> wrote:
>Here is what I came up with, but it doesn't seem to work fully.
>;;the following 2 functions are used to find the largest value on the
>;;list.. the second
>;;function assumes that all the values on the list are positive. it
>;;seems to work well
>(defun findmax(l) (max1 l 0))
>
>(defun max1(l candidate)
> (cond((null l) candidate)
> (((car l) candidate)(max1(cdr l) (car l)))
The above line seems to be missing a function call. Shouldn't it be:
((> (car l) candidate) (max1(cdr l) (car l)))
> (t (max1 (cdr l) candidate))))
>
>;;this function removes the largest value off of a given list and
>;;returns the list
>
>(defun findandremove(candidate list)
> (cond((null list)nil)
> ((= candidate (car list))(findandremove candidate (cdr list)))
> (t (cons(car list)
> (findandremove candidate (cdr list))))))
>
>;;this is where is progam falls apart. this function should move the
>;;largest value to the front
>;;of a list, but it doesn't work
>
>(defun maxtofront(list)
> (cons (largest list) (findandremove (largest list) list)))
>
>;;I dont' understand why this works and the function immediately above
>;;doesnt
You haven't posted the definition of LARGEST. How does it differ from
FINDMAX?
>;(cons (largest '(1 2 3 4 5 6)) (findandremove (findmax '(1 2 3 4 5 6))
>;'(1 2 3 4 5 6)))
>
>;;I had hoped to use this function to give the sorted list(in descending
>;;order).
>(defun sortalist(list)
> (cond((null list) nil)
> (t (cons (car (maxtofront list) (sortalist (cadr (maxtofront
>list)))))))
The function CADR just returns the second element of the list. If you want
the rest of the list, you must use CDR.
--
Barry Margolin, ······@genuity.net
Genuity, Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
You are very close to the solution. The comments from Barry should get
you there.
A little remark though: Common Lisp already has a lot of utilities, you
should look at them before writing your own version (takes less time,
generally better written, easier to understand). For your problem, you
should probably use MAX and REMOVE (they are not 'sort functions' so I
don't think they go against the terms of the problem).
Note that MAX returns the max of the arguments, not of a list, but you
can use APPLY to make it work for you.
--Matthieu
"Denzil L. Kelly" wrote:
>
> Here is what I came up with, but it doesn't seem to work fully.
> ;;the following 2 functions are used to find the largest value on the
> ;;list.. the second
> ;;function assumes that all the values on the list are positive. it
> ;;seems to work well
> (defun findmax(l) (max1 l 0))
>
> (defun max1(l candidate)
> (cond((null l) candidate)
> (((car l) candidate)(max1(cdr l) (car l)))
> (t (max1 (cdr l) candidate))))
>
> ;;this function removes the largest value off of a given list and
> ;;returns the list
>
> (defun findandremove(candidate list)
> (cond((null list)nil)
> ((= candidate (car list))(findandremove candidate (cdr list)))
> (t (cons(car list)
> (findandremove candidate (cdr list))))))
>
> ;;this is where is progam falls apart. this function should move the
> ;;largest value to the front
> ;;of a list, but it doesn't work
>
> (defun maxtofront(list)
> (cons (largest list) (findandremove (largest list) list)))
>
> ;;I dont' understand why this works and the function immediately above
> ;;doesnt
>
> ;(cons (largest '(1 2 3 4 5 6)) (findandremove (findmax '(1 2 3 4 5 6))
> ;'(1 2 3 4 5 6)))
>
> ;;I had hoped to use this function to give the sorted list(in descending
> ;;order).
> (defun sortalist(list)
> (cond((null list) nil)
> (t (cons (car (maxtofront list) (sortalist (cadr (maxtofront
> list)))))))
>
> Matthieu Villeneuve wrote:
>
> >Denzil Kelly wrote:
> >
> >>Does anyone have any ideas on how to sort a list of 10 numbers using
> >>only recursion?
> >>
> >
> >Yes. :)
> >
> >>We are not permitted to use loops or the built in sort
> >>functions of lisp.
> >>
> >
> >Just think a little about it.
> >You have to use recursion, so you need to decide what to recurse on.
> >Since you operate on lists, that will probably be an element of the
> >list. Many recursive algorithms on lists recurse on the CAR of the list,
> >but for a sort that doesn't seem very easy. The element you choose needs
> >to be of useful for a sort, and not many elements fulfill that
> >condition...
> >
> >Feel free to post any further reflexion you have about that. It should
> >be quite easy to arrive to a simple (i.e. inefficient :) solution (mine
> >takes 4 lines and is very straightforward).
> >
> >
> >--Matthieu
> >
Denzil Kelly wrote:
> Does anyone have any ideas on how to sort a list of 10 numbers using
> only recursion? We are not permitted to use loops or the built in sort
> functions of lisp.
Pick one element of the list and set it aside for a moment.
Sort the remaining 9 elements. (This is where the recursion
comes in.) Combine the 10th element with the sorted 9-element
list.
Divide the list into two portions. Sort each of them. Combine
the two sorted sublists. (If you do the division in such a way
as to make the last step as easy as possible, you get the
sorting algorithm called "quicksort". If you do the division
in the easiest way possible and do more work at the last stage,
you get the algorithm called "merge sort". Both are good.)
--
Gareth McCaughan ················@pobox.com
.sig under construc
Denzil Kelly wrote:
> Does anyone have any ideas on how to sort a list of 10 numbers using
> only recursion? We are not permitted to use loops or the built in sort
> functions of lisp.
················@pobox.com (Gareth McCaughan) writes:
> Pick one element of the list and set it aside for a moment.
> Sort the remaining 9 elements. (This is where the recursion
> comes in.) Combine the 10th element with the sorted 9-element
> list.
A tribute to the intrinsic beauty and elegace of recursively ascending bubbles.
(defun sort (bubbles smallerp)
(labels ((ascend (bleb bubbles)
(if (and bubbles (funcall smallerp (first bubbles) bleb))
(cons (first bubbles) (ascend bleb (rest bubbles)))
(cons bleb bubbles))))
(and bubbles (ascend (first bubbles) (sort (rest bubbles) smallerp)))))
--
Students doen't cheat. They know their instructors read c.l.l.