------art_125210_10684408.1152407055802
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 7/8/06, Matthew Smillie <M.B.Smillie / sms.ed.ac.uk> wrote:
> On Jul 8, 2006, at 22:41, Dark Ambient wrote:
>
> > I have a question on the code below that James shared with me.  While
> > he might be best to answer if anyone has an idea please feel free to
> > reply.
> >
> > I'm looking in particular , def recursive_sort.  The list is first
> > passed into def sort which immediately puts it into the
> > recursive_sort. The two parameters are unsorted (which I understand)
> > and the [] which I don't understand.   I think *maybe* this is taking
> > the first element of the unsorted array and putting it into sorted.
> > Is that correct ?  TIA
> > Stuart
>
> [James' code below]
>
> First, the formal to the recursive_sort method are an unsorted array
> (named 'unsorted'), and an array that's in sorted order (named
> 'sorted').
>
> The call in sort uses actual parameters of the array being sorted
> ('array') and an empty array (that's what [] means).  An empty array
> is in sorted order by definition.
>
> So, starting off with an empty sorted array, recursive_sort finds the
> *lowest* element (not the first element) in the unsorted array, adds
> it to the sorted array, and removes it from the unsorted array.
>
> At this point, the method has a sorted array with one element, and an
> unsorted array where every element is > verything in the sorted
> array (since we took out the lowest element).
>
> The key thing to note here is that these two arrays are exactly the
> sort of thing you could pass into recursive_sort: an unsorted array,
> and a sorted array.

Are you saying to use these two types of arrays it must be done with a
recursive method ?


> So that's exactly what we do, pass those two arrays as the parameters
> to another call of recursive_sort.  The next call has one small
> wrinkle, are we *sure* that when we move the lowest element from the
> unsorted array to the sorted array, that the sorted array is still
> sorted?
>
> The answer's yes, because in the first call, we moved the lowest
> element.  In the second call, we're moving the next-lowest element,
> and we're using 'push' to put it on the end of the list.  So, we're
> going to pushing the lowest, then the next-lowest, then the next-next-
> lowest, and so on, and that ensure that the sorted array is always in
> sorted order.  This is basically the same strategy you used before in
> your loop, just done using recursion.
>
> Here's a walk-through of the array values for each call for James'
> example:
>
>     -- unsorted array -- sorted array
> 0. -- ['zeta', 'beta', 'alpha', 'beta'] -- []
> 1. -- ['zeta', 'beta', 'beta'] -- ['alpha']
> 2. -- ['zeta', 'beta'] -- ['alpha', 'beta']
> 3. -- ['zeta'] -- ['alpha', 'beta', 'beta']
>
> 0 is the parameters from the first call to #recursive_sort made from
> #sort.  1 is the parameters to the next call of recursive_sort (which
> is made inside the first call).  2 is the parameters to the next call
> of recursive_sort, and so on.
>
> When you get to 3, though, things are a little different.  The method
> finds the lowest element in the sorted array ('zeta' at this point),
> does the push, and creates a new unsorted list, they'll look like this:
>    new_unsorted: []
>          sorted: ['alpha', 'beta', 'beta', 'zeta']
> If you look at the if statemetn at the bottom of the method, you'll
> see that rather than making another call to recursive_sort, when the
> new_unsorted list is empty the method returns the sorted array.
>
> Note that this is the first value returned in any of the calls so far!
>
> It's important to remember when you're debugging recursive methods
> that they generally consist of a large chain of method calls until
> some termination condition is met, followed by a large chain of
> returns.  In this case, the calls and returns are structured
> something like this:
>
> call #0 asks for the result of call #1
> call #1 asks for the result of call #2
> call #2 asks for the result of call #3
>
> call #3 returns a result: the sorted array
>
> call #2 returns the result of call #3
> call #1 returns the result of call #2
> call #0 returns the result of call #1
>
> And you end up with the sorted array.
>
> Hope that helps a bit,
> matthew smillie.
>

You explained it with great detail so I hope over time it starts to sink
in.  Much obliged!
Stuart

> >
> > On 6/29/06, James Edward Gray II <james / grayproductions.net> wrote:
> >
> >> def sort(array)
> >>    recursive_sort(array, [])
> >> end
> >>
> >> def recursive_sort(unsorted, sorted)
> >>    # find the lowest element
> >>    lowest  il
> >>    unsorted.each do |item|
> >>      if lowest nil || item < lowest
> >>        lowest  tem
> >>      end
> >>    end
> >>
> >>    # add it to our sorted list
> >>    sorted.push(lowest)
> >>
> >>    # make a new unsorted list, minus the low guy
> >>    new_unsorted   ]
> >>    added         alse
> >>    unsorted.each do |item|
> >>      if added false and item lowest
> >>        added  rue
> >>      else
> >>        new_unsorted.push(item)
> >>      end
> >>    end
> >>
> >>    # return sorted list if we are done, or recurse to keep sorting
> >>    if new_unsorted.size 0
> >>      sorted
> >>    else
> >>      recursive_sort(new_unsorted, sorted)
> >>    end
> >> end
> >>
> >> list  'zeta', 'beta', 'alpha', 'beta']
> >> puts sort(list)
> >>
> >> __END__
> >>
> >> Hope that helps.
> >>
> >> James Edward Gray II
> >>
> >>
> >>
> >>
> >
>
>
>

------art_125210_10684408.1152407055802--