Hi,
I am trying to learn lisp but I am having problems. My biggest one
is I have no idea on how to do recursive sorting algorithms.
I am working on (but failing miserably at) writing a recursive Merge Sort
algortihm and a Quicsort (also recursive) If anyone has examples of this
sort of thing or has any pointers or explanations, PLEASE send them to me
Thanx
James
From: Jeff Dalton
Subject: Re: I need lisp examples
Date:
Message-ID: <7963@skye.ed.ac.uk>
In article <············@lester.appstate.edu> ···@sc (James F. Jarrett) writes:
>I am working on (but failing miserably at) writing a recursive Merge Sort
>algortihm and a Quicsort (also recursive) If anyone has examples of this
>sort of thing or has any pointers or explanations, PLEASE send them to me
For merge-sort, start by writing a merge. (Common Lisp already
has something called "merge", so you should pick a different name.)
Something like this:
(defun list-merge (list1 list2 lessp-fn)
;; The lists are already in order.
(cond ((null list1)
...)
((null list2)
...)
...))
To fill in the "..."s, think of some examples. E.g.:
(merge '() '(2 4 6) #'<) ==> ??
(merge '(1 3 5) '() #'<) ==> ??
(merge '(1 3 5) '(2 3 4) #'<) ==> ??
Now try to get the result of the last example by first doing
(merge '(3 5) '(2 3 4) #'<)
Look for a similar "previous problem" for (merge '(3 5) '(2 3 4) #'<).
And so on.
For merge-sort, you have to
1. Divide the list in halves of equal length
(or off by one if the length of the list is odd).
2. Sort the halves.
3. Merge the results.
except when the list is sufficiently small, when you can just
return the sorted version directly.
Dividing the list in 1/2 is the tricky part. A somewhat inefficient
way of doing it that will nonetheless get you off the ground would
be to write one function that returns the 1st half (however the helf
is selected -- every other element, perhaps) and another function
that returns the 2nd half.
-- jeff