0

I am new to Ruby and quite confused about the sorting method

For example:

person.sort{|x, y| x.age<=> y.age}

I know if I change it to y.age<=> x.age, It will reverse the sorting order.

I read this other question and all of them only say that x and y are two elements from the array, chosen by the sort algorithm.

But is x always the lesser object? I mean if I write it like the first way, will it always sort from youngest to oldest?

Thanks

Community
  • 1
  • 1
hrsetyono
  • 4,474
  • 13
  • 46
  • 80
  • Haha yeah, those answers are good but none of them state whether `x` is the lesser or greater – hrsetyono Mar 23 '13 at 06:50
  • 2
    But I don't see why the accepted answer in the duplicate doesn't answer this question as well. Are you familiar with the `<=>` operator? – JJJ Mar 23 '13 at 06:50
  • From what I read in that question, it returns `-1` if `x – hrsetyono Mar 23 '13 at 06:54
  • 1
    I don't quite understand the question. The sorting method is the one that determines which one is the lesser or greater. If you pass for example `5, 2` to the default sort it will return `1` which tells the sorting algorithm that x is greater than y. If you pass `4, 8` it returns -1 which tells that y is greater than x. If it already knew which one is greater and which one is lesser, the array would already be sorted. – JJJ Mar 23 '13 at 06:58
  • Thanks. So, is the passed element of `x` and `y` always different when we run the program? Or is it the same? – hrsetyono Mar 23 '13 at 07:00
  • 1
    `x` and `y` are just some elements of the array when the sorting algorithm goes through it. The method is called multiple times when the sorting takes place. – JJJ Mar 23 '13 at 07:01
  • Ah so that's how it works! I thought the method is only called once to decide whether it is from small-to-big to big-to-small. Thanks – hrsetyono Mar 23 '13 at 07:06

2 Answers2

2

Here's a way you can answer this question yourself, with a form of reductio ad absurdum: What if x were always the lesser object? If that were the case, then you wouldn't need to bother comparing it with y, would you? You could just write this:

person.sort { |x, y| 1 }

Or maybe I have that backwards, and you could just write this:

person.sort { |x, y| -1 }

But either way, that's kind of absurd, isn't it? Certainly if you try it, it won't work.

So this tells us that in the body of this sort block, we don't know whether x or y is the lesser object. In fact, x and y may be any two arbitrary elements from the person array. That's the entire reason we have to write out the comparison.

Does that help clarify it, or did I misunderstand your question?

Michael Geary
  • 28,450
  • 9
  • 65
  • 75
  • Yeah you do understand the question. So, when we write `x.age<=>y.age`, we don't know whether it is sorted from youngest-to-oldest or oldest-to-youngest? – hrsetyono Mar 23 '13 at 06:58
  • 1
    No. In that case it's sorted from yongest-to-oldest because if `x.age` is, say, 12 and `y.age` is 15 it will determine that 12 should be sorted before 15. – JJJ Mar 23 '13 at 06:59
  • But when we run it, we don't know whether `x` will be less than 15 right? It can be 25 which will order the array from oldest to youngest. – hrsetyono Mar 23 '13 at 07:03
  • 2
    When the sort block is called, either `x` or `y` may be the lesser value. That's why we write a comparison in the block, to determine which one is which. When you write `x.age<=>y.age`, you are saying "If x.age is less, return -1. If y.age is less, return 1. If they are equal, return 0." This is what a sort callback does: takes two values and makes a determination about which should sort first. If you reverse that comparison, you reverse the sort. – Michael Geary Mar 23 '13 at 07:03
  • 1
    "But when we run it, we don't know whether x will be less than 15 right? It can be 25." That's right! We don't know that! This is *why* we write a comparison in the sort block. It's our comparison that straightens it out. If x is greater than y, we'll return 1. If x is less than y, we'll return -1. Or 0 of they are equal. – Michael Geary Mar 23 '13 at 07:05
  • Thanks, I finally get it from Juhana answer saying that `sort` runs multiple times. I though that line is only run once. It all makes sense now. – hrsetyono Mar 23 '13 at 07:10
2

This is a simplification of what's happening and not the sorting algorithm Ruby uses (hopefully), but it might help understand what's happening.

Let's say you have this array of ages you want to sort:

[15, 25, 12]

Now the sorting algorithm starts going through the array to determine the correct ordering. First it picks the first two elements and compares them:

|15, 25|  15 <=> 25

The result is -1, so now it knows that 15 should be sorted before 25.

Next it takes 25 and 12.

|25, 12|  25 <=> 12

The result is 1. 12 should be sorted before 25 as well.

Now we know that 25 should be sorted after every other element. We only need to know the order between 15 and 12.

|15, 12|  15 <=> 12

The result is 1, so 12 should be sorted before 15. Now the final ordering is known:

[12, 15, 25]

As you see, the comparison algorithm is called multiple times. x and y in |x, y| are placeholders for array elements that are passed to the comparison method.

JJJ
  • 32,902
  • 20
  • 89
  • 102