------ 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--