On Thu, Feb 13, 2014 at 11:51 PM, Jay Ka <lists / ruby-forum.com> wrote:
> Hey all,
>
> I'm going through Chris Pine's Learning to Program book, and there's
> a problem in Chapter 10 that asks you to write your own sorting method
> without using #sort. I had initially attempted to do this using two
> arrays and iterating through one of them, attempting to compare the
> words inside the array, find the smallest word, and pass it to another
> array (we'll call it sorted_words). This failed, however. I've been
> working on it for the better part of a day, and it's not working. I took
> a peek at Chris' solution. Here is the pastebin link with my comments:
> http://pastebin.com/9p5fUbnL. The comments are my attempts to understand
> Chris' thought process, which he describes here:
>
> "What strikes me as probably the easiest way to do this is to keep two
> more lists around: one will be our list of already-sorted words, and the
> other will be our list of still-unsorted words. We'll take our list of
> words,find the "smallest" word (that is, the word that would come first
> in the dictionary), and stick it at the end of the already-sorted list.
> All of the other words go into the still-unsorted list. Then you do the
> same thing again but using the still-unsorted list instead of your
> original list: find the smallest word, move it to the sorted list, and
> move the rest to the unsorted list. Keep going until your still-unsorted
> list is empty."
>
> I have a few questions. First, what is the point of the first method
> (def sort)? What is its function? I don't get why it's necessary.

It's just an entry point, so that when you want to sort an array you
call this method. It, in turn, calls the real method with the real
parameters required: the original array and an initial empty array.

The point of the method is that the requirement of a second, empty
array, is just an implementation detail of the specific algorithm he
chose. If tomorrow you want to change the algorithm to a different one
that doesn't require this empty array or that requires two arrays or
something completely different, you don't want to go changing all the
places where you called sort.
You can call it the  "public interface" of the sort functionality.
When you learn about classes this should become more apparent, as in
my opinion it is one of the most important concepts of Object Oriented
Programming: encapsulation.

> Second, although I tried to work through the iteration of unsorted.each
> (as noted in my comments), it's just not clear to me what is going on.

For sorting algorithms I find it very useful to think in terms of
sorting cards in my hand (maybe because I like card games a lot :)).
Imagine you are dealt a bunch of cards face down. The algorithm then:

- Takes the first card. Nominate it as the smallest seen until now,
set it aside in the spot named "smallest" on the table
- For each of the cards in the bunch:
  - Take the next one
  - Is it smaller than the card in "smallest"?
    - If so, place it there, take the one that was previously there
and put it in another place at the table, named "still_unsorted"
    - If not, place it in the "still_unsorted" spot.

- When you finish, you have the smallest card in the "smallest" spot
on the table. Take it and place it in the "sorted" spot, on top of any
card already there.

- Now, start again, this time taking the "still_unsorted" stack of
cards as your initial bunch of cards.

As you can see, this is a recursive algorithm, that applies the same
steps against an array that gets smaller, and smaller, since every
time you go through it you take out one of the elements, the smallest.


> My third question is a bit more abstract. When I first looked at this
> problem at no point did it occur to me to do anything Chris did in his
> solution. This worries me. I've been teaching myself Ruby for about 6-7
> months and I know I will always be learning new things even years from
> now. But the solution that Chris came up with did cross my mind for a
> second. Does this kind of thinking eventually come with exposure / more
> study? I'm a little deflated with how much I worked on this problem
> fruitlessly, and how far away I was from the actual solution. Granted I
> know there are many solutions to problems in Ruby, but the fact that I
> still can't grasp exactly what this program is doing is making me doubt
> myself.

Well, it takes practice, study and so on, but specially it takes
patience. There's no single solution to the sorting problem, there are
a lot of sorting algorithms. As I showed above, it helps (at least it
does for me) if you try to think of how you'd go about doing it with a
bunch of cards, trying to translate your actual line of thinking
during the process to the program.

Don't despair and keep working at it. With practice you will get
better. But my advice: try to gather a good foundation of concepts.
Everything will fall into place.

Jesus.