From: dblack@...
Date: 2006-07-09T22:31:14+09:00
Subject: Re: Sorting arrays

Hi --

On Sun, 9 Jul 2006, Dark Ambient wrote:

> On 7/8/06, Matthew Smillie <M.B.Smillie@sms.ed.ac.uk> wrote:
>
>> > 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.
>
>
> I'm trying to take this in one step at a time. Only I can't grasp, the
> mechanics of the first step. In theory I follow what's supposed to be going
> on but that's not helping my understanding. I re-created the first step
> slightly and dropped the recursion.
>
> def sort(list)
>   sorted = []
>   unsorted = []
>
> lowest = nil
>  list.each do |item|
>     if lowest == nil || item < lowest
>        lowest = item
>     end
>  end
>
>  sorted.push(lowest)
>  puts sorted
>
> end
> mylist = ['five', 'three', 'one', 'ten', 'eight']
> sort mylist
>
> Amazingly :), 'eight' is pushed into the first element of the sorted array.
> When I asked some posts back through about the elements being compared to
> nil I was told that wasn't the case.  However, lowest is being set to nil.
> Then the statement lowest is equal to nil, or item smaller then lowest (or
> nil).  I believe nil has a value, which is 0 or false.  However how can any
> item be smaller then it.  Bottom line is I'm not seeing the magic here in
> the comparison to find the correct element.
> My apologies for my density with this code.

I haven't been following this thread but let me try to explain.

nil's value is nil.  nil is an object.  It has a Boolean value of
false, but it is, itself, just the object nil.

There's no issue of nil being smaller or larger than anything.  The
first time through your loop, lowest is nil -- which means that the
item < lowest comparison is never evaluated.  The next time through,
lowest is "five", so item < lowest is evaluated.  It's false, so the
next statement (lowest = item) is not executed.

And so forth, with the rest of the comparisons: five/three, five/one,
five/ten, five/eight.  On the last one, the comparison item < lowest
is true.  So lowest = item gets executed, and lowest is now "eight".

Then you push lowest (i.e., "eight") onto the empty array sorted.
Therefore, sorted now looks like this:

   ["eight"]

Then you print it out.

That's about it :-)


David

-- 
http://www.rubypowerandlight.com => Ruby/Rails training & consultancy
http://www.manning.com/black     => RUBY FOR RAILS, the Ruby book for
                                                     Rails developers
http://dablog.rubypal.com        => D[avid ]A[. ]B[lack's][ Web]log
dblack@wobblini.net              => me