Matthew Smillie
7/8/2006 11:07:00 PM
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 >= everything 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.
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.
>
> 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 = nil
>> unsorted.each do |item|
>> if lowest == nil || item < lowest
>> lowest = item
>> end
>> end
>>
>> # add it to our sorted list
>> sorted.push(lowest)
>>
>> # make a new unsorted list, minus the low guy
>> new_unsorted = [ ]
>> added = false
>> unsorted.each do |item|
>> if added == false and item == lowest
>> added = true
>> 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
>>
>>
>>
>>
>