Rite of Passage: Sorting

Learn to Program, Third Edition — by Chris Pine (88 / 116)

👈 A Method So Easy, It Calls Itself | TOC | Progress Checkpoint 👉

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 their own lightsaber, you’ll demonstrate a deeper mastery if you write your own sorting method. It’s not easy, but this kind of problem solving is part of nearly every program you’ll write. We’ve all done it, and now you will, too.

But where do you begin? Much like with continent_size, it’s probably best to try to solve the problem in English first. You can then translate it into Ruby after you’ve wrapped your head around it.

So, you want to sort an array of words, and you know how to find out which of two words comes first in the dictionary (using <).

For this exercise, you’re going to use the “quicksort” algorithm, which goes something like this:

1. Pick one element out of the array, which we’ll call the pivot.
2. Now split everything else in the array into two piles (arrays): stuff that’s smaller than the pivot, and stuff that’s larger.
3. Recursively sort each of those piles, using this same quicksort algorithm.
4. Return the fully sorted array, which is the sorted pile of…