Rite of Passage: Sorting
Remember the sorting program you wrote here where you asked for a list of words, sorted it, and then displayed the sorted list? The program was made much easier because you used the array’s sort method. But, like the Jedi who constructs his own lightsaber, you’ll exhibit a greater mastery if you write your own sorting method. Hey, we’ve all done it. It’s not easy, but this kind of problem solving is part of nearly every program you’ll write, so you’d best get your practice now.
But where do you begin? Much like with continent_size, it’s probably best to try to solve the problem in English first. Then translate it into Ruby when you’ve wrapped your head around it.
So, we want to sort an array of words, and we know how to find out which of two words comes first in the dictionary (using <).
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.
That doesn’t sound too bad, but it’s keeping all of the details straight that makes it so tricky. Go ahead and try it, and see how it looks. In fact, try it twice: once using recursion and once without. With the recursion, you might need a wrapper method, a tiny method that wraps up another method into a cute little package, like this:
def sort some_array # This "wraps" recursive_sort. |
recursive_sort some_array, [] |
end |
|
def recursive_sort unsorted_array, sorted_array |
# Your fabulous code goes here. |
end |
What was the point of the wrapper method? Well, recursive_sort took two parameters, but if you were just trying to sort an array, you would always have to pass in an empty array as the second parameter. This is a silly thing to have to remember. Here, the wrapper method passes it in for us, so we never have to think about it again.
When you’re done, make sure to test your code! Type in duplicate words and things like that. A great way to test would be to use the built-in sort method to get a sorted version of your list right away. Then, after you have sorted it for yourself, make sure the two lists are equal.