What does Ruby's sort function do?
Let me preface this by saying that I'm new to Ruby (pretty obvious). I am learning Ruby on Codecademy and I am confused about the sort function. To use as an example:
list = [3,2,1,4]
list.sort { |a,b| b <=> a }
I know this will return the array in descending order - [4, 3, 2, 1]. I don't understand exactly why. I know that when the sort function is called, the numbers from the array are passed to the function and compared, and then it returns either -1, 0, or 1 - but then what? For example, I assume this is what will be compared in the first place:
[3 <=> 2] = 1
But what does it do with the returned 1? And what would the array look like after it got 1?
I'm confused because I don't understand how the inverse comparison (a <=> b vs. b <=> a) reverses the sorting direction of the array. If I'm not mistaken, does "1 <=> 2" essentially return "1 comes before 2", whereas "2 <=> 1" returns "2 comes after 1"? Which is more or less the same, but the results are clearly different.
source to share
The operator "spaceship" <=>
does not return something that is English like "a to b". It returns what it needs to know sort
: where the two elements are related to each other. Specifically, it returns the specified value -1, 0, or 1.
B a <=> b
, if a
less b
(using any comparison method for the class for which it a
is an instance), -1 is returned. If they are equal, 0 is returned; and if a
greater than b
, 1 is returned.
When you execute b <=> a
, the return value is based on b
, not on a
, so if a is less than you get 1, whereas you got -1 on execution a <=> b
.
So, while the English meaning is the same, the devil is in the details: it's a -1, 0, or 1 return value. This value tells Ruby exactly how the two elements fit into the sorted array.
The magic with these three numbers is in the quicksort algorithm used by Ruby. Because of the ability to try and explain exactly how this algorithm works, but you can basically view it as a simple comparison over many values. For each element in the array, it <=>
is called with another element in the array to determine where the two elements fall in relation to each other. After sufficient comparisons have been made, the positions of all these individual items are known and the sorting is done.
As a simple (and not quite technically accurate, but close enough) example, consider an array [3, 2, 7, 1]
. You can get the value to compare others to start sorting. We'll choose 3. Performing comparison 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:[2, 3, 7, 1]
-
3 <=> 7 == -1
: 3 is less than 7, so 7 must be to the right of 3. Our array continues to look like it did before, since 7 was already on the right. -
3 <=> 1 == 1
: 3 is greater than 1, so 1 must be to the left of 3. Our array looks like this:[2, 1, 3, 7]
We know that 7 must be correct because it is the only item on the "greater than 3" side. So we just need to figure out the sort order for everything up to 3: 1 and 2. By doing a similar comparison as above, we obviously swap 1 and 2 to get [1, 2, 3, 7]
.
Hope this helps!
source to share
The comparison takes two arguments and returns -1
if the first argument is less than the second argument 0
, if both arguments are equal, and 1
if the second argument is greater than the first argument. When you change them, it inverts the result. <=>
doesn't care where its operands came from, so while the change adds no additional information about the relationship between a
and b
, it inverts the result <=>
and inverts the sort order.
(1 <=> 2) == -1
(2 <=> 1) == 1
As a sorting function, you don't get 1 <=> 2
or 2 <=> 1
; you will receive -1
or 1
. From any number, you determine which argument you passed to the comparison should come later in the result.
source to share
If I'm not mistaken, does "1 <=> 2" essentially return "1 comes before 2", whereas "2 <=> 1" returns "2 comes after 1"? Which is more or less the same, but the results are clearly different.
No and yes. The question asked by the block is "does the left element do before or after the right?" And by swapping left and right, you change the order.
So the answer is, you are not changing the comparison as such, but you are changing the method of the method sort
that remains on the left and which is right.
The return value of the block is interpreted sort
as follows:
-
0
: order doesn't matter -
1
: the elements are already in the correct order -
-1
: the elements are in the wrong order
By swapping left and right, you change whether the block reports sort
that the elements are in the correct or wrong order.
Note that Quicksort is completely irrelevant here. What's important is the comparator block contract. Whether this block is used by Quicksort, Shellsort, Insertion Sort, Bubblesort, Bogosort, Timsort, or some other comparative variety doesn't really matter.
source to share