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

Discussion in 'Ruby' started by Vegard Sandengen, Feb 3, 2010.

  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/.
    Vegard Sandengen, Feb 3, 2010
    #1
    1. Advertising

  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/.
    Aldric Giacomoni, Feb 3, 2010
    #2
    1. Advertising

  3. 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, an_array[i+1] = an_array[i+1], an_array
    # 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, an_array[i+1] = an_array[i+1], an_array
    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/.
    Siep Korteling, Feb 3, 2010
    #3
  4. Vegard Sandengen

    Ryan Davis Guest

    On Feb 3, 2010, at 15:33 , Siep Korteling 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=20
    > another string.
    > Aldric Giacomoni adheres to the principle: go find it out for =

    yourself,=20
    > and he's right; that's the way to go. But if you are like me, a =

    relative=20
    > simple concept like recursion takes a long time to sink in, and a did=20=


    > not find (in my time) any resources which explained it in terms I=20
    > 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 =3D=3D __FILE__ then
    require 'test/unit'

    class TestSort < Test::Unit::TestCase
    def test_mysort
    input =3D ["xenophobia", "foo","baz", "aardvark","bezerk"]
    expect =3D %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.=
    Ryan Davis, Feb 4, 2010
    #4
  5. On 2/3/2010 5:53 PM, Ryan Davis wrote:
    >
    > On Feb 3, 2010, at 15:33 , Siep Korteling 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 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?


    >> 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.
    Michael W Ryder, Feb 4, 2010
    #5
  6. Vegard Sandengen

    Josh Cheek Guest

    [Note: parts of this message were removed to make it a legal post.]

    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 :)
    Josh Cheek, Feb 4, 2010
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Jan_K
    Replies:
    61
    Views:
    576
    Eleanor McHugh
    May 28, 2008
  2. Geoff
    Replies:
    9
    Views:
    112
  3. Replies:
    9
    Views:
    403
    whisperjim
    Nov 27, 2008
  4. Replies:
    0
    Views:
    252
  5. whisperjim
    Replies:
    9
    Views:
    156
    Sam Howes
    Aug 31, 2009
Loading...

Share This Page