Re: LOGO-L> Mid-Value of Three Numbers

["Tom Lynn" <thl22@cam.ac.uk>]

Hi all.

Sorry that I'm a bit late with my response to this one.  It's another 
variant on the first solution ("sort the numbers and return the middle 
one") but generalised for more than three numbers.  The algorithm is a well-
known variant of "quicksort", but it doesn't sort any more of the list than 
it needs to.  It's the "textbook" solution to this problem which I was 
taught on my Computer Science course last year.


The basic algorithm is as follows:

Pick a random element of the list (I use the first element) to be your 
"pivot".  Go through the remaining elements and sort them to either side of 
the pivot, depending on whether they are larger or smaller than the pivot.  
As you do this, count how many you are sorting to each side.

If you have put less than half of the items to the left of the pivot, the 
median value which you are looking for must be more than the pivot.  If you 
have sorted more than half to the left, the median must be somewhere in 
that lefthand side, those less than the pivot.  Repeat the process on 
whichever side the median is in.  The range which you are searching will 
shrink at each stage until it contains only the median.


I have tried to keep it space efficient, so I have used arrays rather than 
lists (and also because I don't trust lists :) and I swap between two 
copies for which is being used as input and which as output.

If you want to find the median, use '(findnth :array)' with parentheses, 
otherwise use 'findnth :array :n'.  It's packed with print statements at 
the moment to show how it works, but these could be taken out without much 
difficulty if you had any need to use it in another program.

Tom Lynn
The following section of this message contains a file attachment
prepared for transmission using the Internet MIME message format.
If you are using Pegasus Mail, or any another MIME-compliant system,
you should be able to save it or view it from within your mailer.
If you cannot, please ask your system administrator for assistance.

   ---- File information -----------
     File:  findnth.lgo
     Date:  26 Aug 1998, 1:36
     Size:  2158 bytes.
     Type:  Text

findnth.lgo