Custom Sorting Method

Ruby
#1

Hey all,

I’m going through Chris P.‘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.
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.
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.

#2

On Thu, Feb 13, 2014 at 11:51 PM, Jay Ka [email protected] wrote:

http://pastebin.com/9p5fUbnL. The comments are my attempts to understand
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.

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.

#3

Yo,

don’t fret, I grew up on Pascal, and I was happy to code 1-2 years Ruby
in Pascal style, then slowly came iterators, I unlearned the using of
explicit return values (and let Ruby do it), and now I quite easily read
code. Writing however is harder, I can write functionally good code, but
I’m always in doubt I have written it the best - Ruby - way.

There is always something to learn, now I battle with metaclasses (not
that I see any real word usage, but it is interesting as a language
construct). Fanatics can go deeper, there is a book on the Ruby VM and
the virtual machine language, and finally there is the C source, yikes!

As for sorting methods, here is a visual aid:
http://www.sorting-algorithms.com/

And visit Hackerrank, you can solve algorithmic problems there, and they
have a specific sorting lesson (teaching insertion sort and counting
sort) and they take you step-by-step through the solution phases:
https://www.hackerrank.com/categories/algorithms/sorting

Looking at the code you linked, this is some kind of insertion sort. But
you are trying understand at least 3 problems at the same time: 1. the
sorting method, 2. the recursive process, 3. the optimized code.

I say choose one, and concentrate on it. Write inefficient, ugly code,
that does the job and you understand it well (the Hackerrank insertion
sort would be a good start). If you don’t understand #each and the
enumerators yet, don’t mix it into the problem, fall back to loops.
Then refactor, without losing functionality. And I suggest change the
strings to numbers, it will be much easier to see which is greater than
what.

As for your third question, what you might lack (as of now) is
algorithmic thinking, which does not depend on any language, but that
will come with practice (think of as a lot of “ahh! (facepalm)” along
the way).
That is exactly why I registered to sites like Hackerrank, Code Chef,
Project Euler, and some Codility.