[Chris Pine] Chapter 7 - Sorting Arrays without .sort

ruby-talk
1

Greetings,

I have set myself out on the great task to understand computer
programming, and i concluded to start my journy with Ruby. It seems like
a the easier to learn program etc.

I have followed Chris Pines online turtorial and now crashed into the
Chapter 7 task of sorting strings by alfabetic order, i quote;

"Let's write a program which asks us to type in as many words as we want
(one word per line, continuing until we just press Enter on an empty
line), and which then repeats the words back to us in alphabetical
order.
Try writing the above program without using the sort method."

I saw through alot of old threads, including the big Chris Pine thread
(/topic/60005) that ran a few years back. Did not want to stir up a old
thread that was non spesified for this problem.

Now if anyone could please explain to me just how you go forth
determining what size and order you sort an array. And do so as if i was
a kindergarden kid, because the solutions i've seen so far goes a small
way in explaining the way you get forth to the answer.

In advance, many thanks Vegard Sandengen.

···

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

2

Vegard Sandengen wrote:

Greetings,

I have set myself out on the great task to understand computer
programming, and i concluded to start my journey with Ruby. It seems like
a the easier to learn program etc.

I have followed Chris Pines online tutorial and now crashed into the
Chapter 7 task of sorting strings by alphabetic order [...]

Well, you need to understand what an array is, and what the element of
an array is.
Then you need to understand what an algorithm is (hint: so far, google
seaches are good).
Finally, Chris Pine says you need to write a sorting algorithm. This is
where it gets tough if you haven't been introduced to any algorithms, or
sorting, yet. Start by doing some reading on Wikipedia about sorting
algorithms, or just plain sorting. Then you can look up "bubble sort",
"quicksort", "tsort" or "turbosort" to get you started.

Thankfully, in Ruby, you can just add to an array and make it bigger and
bigger, without ever determining a size ahead of time, and you can loop
through an array.
Supposing you were allowed to use the "sort" method, and that everything
in the array is a string, you could do this:

array.sort.each { |word| puts word }

Sadly, you can't -- so you need to sort it yourself. Good luck!

···

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

3

One thing that can be helpful when thinking about algorithms, is to think
how you would do it personally.

Try getting ten cards, shuffle them up, and then put them into order.

What did you do when you put them into order?
How did you decide what went where?

Perhaps you had cards in your hand, then took the top one off, and put it on
the table, then one by one took the next consecutive card from your hand,
and added it to the ones on the table, in the place that it would belong in
that list of cards.

Perhaps you looked at the cards, and found the smallest one, then put that
one on the table, then took the next smallest and put that one on the table,
and so on until there were none left.

Think about the steps that you are performing, can you break them down into
a set of instructions? Can you write a "recipe" that if you were to follow
it, the cards would end up sorted?

1. put unsorted cards in hand
2. sorted cards will go on the table
3. take first card, do this or that
4. ...
...

Try to write a set of instructions like this, in English, that reflect what
you do when you sort the cards. Then think about what it would take to
translate that into something that a computer language would be able to
understand and execute. We are using strings (text) instead of cards, but
the basic set of instructions is still the same, and if you can explain how
to sort cards in clearly defined steps, then you can program a string
sorter.

Once you have this, think about what types of containers do you need to
implement your instructions?
What kind of logic do you need to have written, and how can you write it in
such a way that it makes sense to the computer?

Try thinking about these questions, you already know how to sort cards, you
just need to figure out how to tell the computer to do what you are already
doing.

Good luck :slight_smile:

4

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/\.

5

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

I'd disagree in principal with Aldric's advice. For starters, your original instructions say:

"Let's write a program which asks us to type in as many words as we want
(one word per line, continuing until we just press Enter on an empty
line), and which then repeats the words back to us in alphabetical
order.
Try writing the above program without using the sort method."

Start smaller. First write the program using Array#sort. So:

+ take user input until an empty line
+ add each user input to an array
+ print it back out sorted (for starters, using Array#sort).

Once you have that down, THEN work on replacing the call to Array#sort with Array#mysort (or whatever).

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

Make this easier by doing the following:

if $0 == __FILE__ then
  require 'test/unit'

  class TestSort < Test::Unit::TestCase
    def test_mysort
      input = ["xenophobia", "foo","baz", "aardvark","bezerk"]
      expect = %w(aardvark baz bezerk foo xenophobia) # prettier, no?

      assert_equal expect, input.mysort
    end
  end
end

add that to the bottom of your sort algorithm, or in a separate file (exclude the surrounding if, and be sure to require your sort algorithm). When you run it, you'll get a failure... now make it pass.

···

On Feb 3, 2010, at 15:33 , Siep Korteling wrote:

6

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

I'd disagree in principal with Aldric's advice. For starters, your original instructions say:

"Let's write a program which asks us to type in as many words as we want
(one word per line, continuing until we just press Enter on an empty
line), and which then repeats the words back to us in alphabetical
order.
Try writing the above program without using the sort method."

Start smaller. First write the program using Array#sort. So:

+ take user input until an empty line
+ add each user input to an array
+ print it back out sorted (for starters, using Array#sort).

Once you have that down, THEN work on replacing the call to Array#sort with Array#mysort (or whatever).

Wouldn't it be easier to just sort the data as it is input, a simple insert sort?

···

On 2/3/2010 5:53 PM, Ryan Davis wrote:

On Feb 3, 2010, at 15:33 , Siep Korteling wrote:

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

Make this easier by doing the following:

if $0 == __FILE__ then
   require 'test/unit'

   class TestSort< Test::Unit::TestCase
     def test_mysort
       input = ["xenophobia", "foo","baz", "aardvark","bezerk"]
       expect = %w(aardvark baz bezerk foo xenophobia) # prettier, no?

       assert_equal expect, input.mysort
     end
   end
end

add that to the bottom of your sort algorithm, or in a separate file (exclude the surrounding if, and be sure to require your sort algorithm). When you run it, you'll get a failure... now make it pass.