From: Siep Korteling <s.korteling@...>
Date: 2010-02-04T08:33:48+09:00
Subject: Re: [Chris Pine] Chapter 7 - Sorting Arrays without .sort

Aldric Giacomoni wrote:
> Vegard Sandengen wrote:

> 
> array.sort.each { |word| puts word }
> 
> Sadly, you can't -- so you need to sort it yourself. Good luck!
"how you go forth determining what size and order you sort an array."

Don't worry about the size of the array, ruby does take care of that.
Don't worry about the order, strings know if they are "bigger" than 
another string.
Aldric Giacomoni adheres to the principle: go find it out for yourself, 
and he's right; that's the way to go. But if you are like me, a relative 
simple concept like recursion takes a long time to sink in, and a did 
not find (in my time) any resources which explained it in terms I 
understood. Here's my take at explaining (in code):


def test_sort!( an_array )
  an_array[0...-1].each_with_index do |el, i|
  # Meaning: I want each element of the array exept the last element
  # and I want the position in the array as well.
  # In this method the element will be called "el"
  # and the position will be known as "i".
     if el > an_array[i+1] then
    # If the current element is greater than the next one...
       an_array[i], an_array[i+1] = an_array[i+1], an_array[i]
    # then switch their positions.
     end
   end

 # Almost done. Let's politely give back to the user of this method
 # what's probably expected: the sorted array.
  an_array
  # Hurray!
end

# Now test it.
ar=["xenophobia", "foo","baz", "aardvark","bezerk"]
p test_sort!(ar)

# Hmm. That did not work out very well. Of course it didn't - this 
test_sort method
# must be repeated until nothing in the array changes.
# Okay...
p test_sort!(ar)
p test_sort!(ar)
p test_sort!(ar)

# Yes.
# But this is stupid.
# Smartness is called for, perhaps in the form of the dreaded 
recursion...
# Fear not, it is not hard in this case. We are keeping all the goodness
# we created thus far (leaving out the comments), but we'll make a new 
method.

puts "Now for real..."
def recursive_sort!(an_array)
  something_changed = false
  # Remember: the method must be repeated until nothing in the array 
changes.
  # Something_changed is for bookkeeping. Until now, the array is not 
changed
  an_array[0...-1].each_with_index do |el, i|

     if el > an_array[i+1] then
       an_array[i], an_array[i+1] = an_array[i+1], an_array[i]
       something_changed = true
       # The array has changed, so we're not done yet
     end
   end

  recursive_sort!(an_array) if something_changed
  #This is the smart, recursive thingy. Now act like a computer:
  #Form a mental picture of what "an_array" looks like now and go back 
to
  # "def recursive_sort!(an_array)" and start processing.
  # You'll  have to do it several times, untill something_changed == 
false
  #
  # Oh well, your computer will.
  # Inside a method you can use other methods, which, in ruby, you'll do 
all the time.
  # But for a computer it's just as easy to use the same method you're 
using now.
  # However, there has to be a mechanism to stop the whole thing from 
going on forever.
  # That's why  "someting_changed" was made. The process stops if it is 
false.
  # Once it's done( when something_changed remains false),  we'll still 
return:"
  an_array
end

p recursive_sort!(["xenophobia", "foo","baz", "aardvark","bezerk"])


hth,

Siep
-- 
Posted via http://www.ruby-forum.com/.