# \[Chris Pine\] Chapter 7 - Sorting Arrays without .sort **URL:** \ **Category:** ruby-talk\ **Created:** [3 February 2010 20:31 UTC](https://rubytalk.org/t/chris-pine-chapter-7-sorting-arrays-without-sort/57258 "2010-02-03T20:31:14Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![Vegard\_Sandengen](https://avatars.discourse-cdn.com/v4/letter/v/bc79bd/32.png) [@Vegard\_Sandengen](https://rubytalk.org/u/Vegard_Sandengen)\ **Post date:** [3 February 2010 20:31 UTC](https://rubytalk.org/t/chris-pine-chapter-7-sorting-arrays-without-sort/57258/1 "2010-02-03T20:31:14Z")
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/](http://www.ruby-forum.com/). ---
**Author:** ![Aldric\_Giacomoni2](https://avatars.discourse-cdn.com/v4/letter/a/91b2a8/32.png) [@Aldric\_Giacomoni2](https://rubytalk.org/u/Aldric_Giacomoni2)\ **Post date:** [3 February 2010 20:57 UTC](https://rubytalk.org/t/chris-pine-chapter-7-sorting-arrays-without-sort/57258/2 "2010-02-03T20:57:44Z")
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/\](http://www.ruby-forum.com/%5C). ---
**Author:** ![Josh\_Cheek](https://avatars.discourse-cdn.com/v4/letter/j/e79b87/32.png) [@Josh\_Cheek](https://rubytalk.org/u/Josh_Cheek)\ **Post date:** [4 February 2010 04:49 UTC](https://rubytalk.org/t/chris-pine-chapter-7-sorting-arrays-without-sort/57258/3 "2010-02-04T04:49:27Z")
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 🙂 ---
**Author:** ![Siep\_Korteling](https://avatars.discourse-cdn.com/v4/letter/s/41988e/32.png) [@Siep\_Korteling](https://rubytalk.org/u/Siep_Korteling)\ **Post date:** [3 February 2010 23:33 UTC](https://rubytalk.org/t/chris-pine-chapter-7-sorting-arrays-without-sort/57258/4 "2010-02-03T23:33:48Z")
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/\](http://www.ruby-forum.com/%5C). ---
**Author:** ![Ryan\_Davis1](https://yyz1.discourse-cdn.com/flex029/user_avatar/rubytalk.org/ryan_davis1/32/1848_2.png) [@Ryan\_Davis1](https://rubytalk.org/u/Ryan_Davis1)\ **Post date:** [4 February 2010 01:53 UTC](https://rubytalk.org/t/chris-pine-chapter-7-sorting-arrays-without-sort/57258/5 "2010-02-04T01:53:21Z")
> 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: ---
**Author:** ![Michael\_W\_Ryder2](https://avatars.discourse-cdn.com/v4/letter/m/e99b99/32.png) [@Michael\_W\_Ryder2](https://rubytalk.org/u/Michael_W_Ryder2)\ **Post date:** [4 February 2010 04:22 UTC](https://rubytalk.org/t/chris-pine-chapter-7-sorting-arrays-without-sort/57258/6 "2010-02-04T04:22:15Z")
> > 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.