Menu
Beginning programmer here, just wanting to understand the process behind Ruby's sort method when using the spaceship operator <=>. Hope someone can help.
In the following:
array = [1, 2, 3]
array.sort { |a, b| a <=> b }
... I understand that sort is comparing a pair of numbers at a time and then returning -1 if a belongs before b, 0 if they're equal, or 1 if a should follow b.
But in the case of sorting in descending order, like so:
array.sort { |a, b| b <=> a }
... what exactly is happening? Does sort still compare a <=> b and then flip the result? Or is it interpreting the returns of -1, 0 and 1 with reversed behavior?
In other words, why does placing the variables in the block like so:
array.sort { |b, a| b <=> a }
...result in the same sorting pattern as in the first example?
905
If you aren't familiar with Ruby's spaceship operator, <=>, it compares two objects and returns 1 if the first object's value is larger, 0 if both values are equal, and -1 if the second object's value is larger. In our first example it compared 7 to 1 and returned 1 because 7 has a larger value.
The Ruby sort method works by comparing elements of a collection using their <=> operator (more about that in a second), using the quicksort algorithm. You can also pass it an optional block if you want to do some custom sorting. The block receives two parameters for you to specify how they should be compared.
The Array#sort method in Ruby uses the venerable Quicksort algorithm. In its best case, Quicksort has time complexity O(n log n), but in cases where the data to be sorted is already ordered, the complexity can grow to O(n2).
It's a general comparison operator. It returns either a -1, 0, or +1 depending on whether its receiver is less than, equal to, or greater than its argument.
a <=> b will return -1 if a belongs before b, 0 if they're equal, or 1 if a should follow b.b <=> a will return -1 if b belongs before a, 0 if they're equal, or 1 if b should follow a.
Since you are reversing the order, the output should be reversed, just like the - operator, for example. 3-5 is -2, and 5-3 is 2.
array.sort { |b, a| b <=> a } is equal to array.sort { |a, b| a <=> b } because the first argument is before the spaceship, and the second is after. Ruby doesn't care what the name of the variable is.
134
Sort just does this:
comparison_block.call(elem[i],elem[j])
It doesn't know or care what your block looks like internally, but it knows which element it passed in as the first argument and which as the second, and that's what the result is based on. In a normal numeric ascending sort, calling the block with (1,0) should return 1; calling it with (0,1) should return -1. Order matters.
27
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
