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

vladwow · February 3, 2010, 9:30pm

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 P.s 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 P. 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.

vladwow · February 3, 2010, 9:54pm

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 P.s 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 P. 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!

vladwow · February 4, 2010, 12:33am

Aldric G. 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 G. 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

vladwow · February 4, 2010, 2:54am

On Feb 3, 2010, at 15:33 , Siep K. wrote:

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

vladwow · February 4, 2010, 5:51am

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?

put unsorted cards in hand
sorted cards will go on the table
take first card, do this or that
…
…

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

vladwow · February 4, 2010, 5:30am

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

understood. Here’s my take at explaining (in code):

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?