What does the Ruby sort function do, exactly?

Question

Let me preface this by saying I'm a newbie to Ruby (pretty obvious). I'm learning Ruby on Codecademy and I'm confused by the sort function. To use as an example:

list = [3,2,1,4]
list.sort { |a,b| b <=> a }

I know that this will return the array in descending order - [4, 3, 2, 1]. What I don't understand is why, exactly. I know that when the sort function is called, the numbers from the array are passed into the function and compared, which then returns either -1, 0, or 1 - but then what? For instance, I'm guessing this is what would be compared first:

[3 <=> 2] = 1

But what does it do with the 1 that is returned? And what would the array look like after it gets the 1?

I'm confused because I don't understand how reversing the comparison (a <=> b vs. b <=> a) changes the direction in which the array is sorted. Unless I'm mistaken, doesn't "1 <=> 2" essentially return "1 comes before 2", whereas "2 <=> 1" returns "2 comes after 1"? Which is more or less the same thing, yet the results are obviously different.

Answer 1

Unless I'm mistaken, doesn't "1 <=> 2" essentially return "1 comes before 2", whereas "2 <=> 1" returns "2 comes after 1"? Which is more or less the same thing, yet the results are obviously different.

No and yes. The question that is asked of the block is: "does the left element come before or after the right?" And by swapping left and right, you swap the order.

So, the answer is: you aren't reversing the comparison per se, but you are reversing the sort method's idea of which is left and which is right.

The return value of the block is interpreted by sort like this:

• 0: order doesn't matter
• 1: the elements are already in the right order
• -1: the elements are in the wrong order

By swapping left and right, you swap whether the block tells sort that the elements are in the right or wrong order.

Note that Quicksort is completely irrelevant here. What matters is the contract of the comparator block. Whether that block is then used by Quicksort, Shellsort, Insertion Sort, Bubblesort, Bogosort, Timsort or whatever other comparison-based sort doesn't really matter.

Answer 2

The "spaceship" operator, <=> doesn't return something so English as "a comes before b". It returns what sort needs to know: where two elements are in relation to each other. Specifically, it returns the -1, 0, or 1 value you mentioned.

In a <=> b, if a is less than b (via whatever comparison method is used for the class of which a is an instance), the return is -1. If they're equal, return is 0; and if a is greater than b, the return is 1.

When you do b <=> a, the returned value is based on b rather than a, so if a is smaller, you'll get 1, whereas you got -1 when doing a <=> b.

So while the English meaning is the same, the devil is in the details: that -1, 0, or 1 return value. That value tells Ruby precisely how two elements fit into a sorted array.

The magic with those three numbers is in the quicksort algorithm used by Ruby. It's out of scope to try and explain precisely how that algorithm works, but you can basically look at it as a simple comparison on many values. For each item in an array, <=> is called with another item in the array in order to determine where the two items fall relative to each other. Once enough comparisons have been made, the positions of all those individual items is known and the sorting is done.

As a simple (and not really technically accurate, but close enough) example, consider the array [3, 2, 7, 1]. You can grab a value to compare others to in order to start the sorting. We'll pick 3. Running a comparison of 3 with all other numbers gives us:

• 3 <=> 2 == 1: 3 is greater than 2, so 2 must be to the left of 3. Our array might look like this now: [2, 3, 7, 1]
• 3 <=> 7 == -1: 3 is less than 7, so 7 must be the the right of 3. Our array continues to look as it did before, as the 7 was already on the right.
• 3 <=> 1 == 1: 3 is greater than 1, so the 1 must be on the left of 3. Our array looks like this now: [2, 1, 3, 7]

We know the 7 must be correct since it's the only element on the "greater than 3" side. So we just need to figure out the sort order for everything before the 3: 1 and 2. Running a similar comparison as above, we obviously swap the 1 and 2 to get [1, 2, 3, 7].

I hope this helps!

Answer 3

The comparison gets two arguments and returns -1 if the first argument is less than the second argument, 0 if the two arguments are equal, and 1 if the second argument is greater than the first argument. When you swap the two, it inverts the result. <=> doesn’t care about where its operands came from, so although the change doesn’t add any extra information about the relationship between a and b, it does invert the result of <=>, and that inverts the sorting order.

(1 <=> 2) == -1
(2 <=> 1) == 1

As the sorting function, you don’t get 1 <=> 2 or 2 <=> 1; you get -1 or 1. From whichever number, you decide which argument you passed to the comparison should come later in the result.