CODEWITHSUNDEEP
rubysortingoperator-keyword
user3544994
user3544994

Reputation: 43

Ruby combined comparison operator sorting

The following code sorts the array in ascending order.

my_array = [2, 3, 1, 5, 4]
my_array.sort! { |n1, n2| n1 <=> n2 }

I read that the <=> operator returns -1 if the first object is less than the second object and 0 if first object is equal to second object and 1 if first object is greater than second object.

How could this information lead to sorting the list? I want to know how the given code works.

If we swap the items around the <=> operator the array gets sorted in descending order. But how?

Upvotes: 0

Views: 1034

Answers (3)

Uri Agassi
Uri Agassi

Reputation: 37409

There are many sorting algorithms out there (ruby uses quicksort), but all of them have one acceptance test: for every element a[n] in array a a[n] <= a[n+1].

What the block in the sort! method should return is what does <= mean. If that's known - sorting can happen - that is all that is needed to be known to the algorithm, since it can compare any two elements in the array and know whether they should be swapped or not.

When you swap n1 with n2, you simply say that for this call you want <= to actually mean >=, which reverses the eventual order of the array...

Ruby needs the elaborate <=> since operators like < return one of two possible results - true and false.

If we used <, for example, for [5, 5] the algorithm may ask a[0] < a[1] which will return false, so the algorithm will swap them, but then again a[0] < a[1] will return false, and the algorithm might fail.

In the best case scenario - there will be an excess of operations and the performance will suffer, in the worst case - the algorithm may never finish...

Upvotes: 1

sawa
sawa

Reputation: 168139

Sorting is done according to the value of the block evaluated with each pair of elements of the array. If you have a <=> statement inside the block, the value will be either -1, 0, or 1 as you know. There is a natural sorting order defined on some class. In case of numerals, they follow the inequality order in the conventional mathematical sense, that is -1 comes before 0, which is before 1.

Upvotes: 1

zwippie
zwippie

Reputation: 15515

Take a look at all the different Sorting Algorithms and you will begin to understand how the comparison of two elements can be used to implement a sorting algorithm for a list of elements.

These visualisations might help to better comprehend the differences between the algorithms.

Upvotes: 0

Related Questions