I am implementing a custom sort. There is the spaceship operator <=>
to deal with sorting an array:
myArray.sort { |a, b| a <=> b }
a <=> b
returns 1
when b
is larger than a
, and the two elements are swapped.a <=> b
returns 0
when a
equals to b
, and the two elements stay in the original position.a <=> b
returns -1
when a
is less than b
, and the two element stay in the original position.So I tested with an example:
myArray = [2, 1, 7, 9, 3, 8, 0]
myArray.sort { |a, b| 1 <=> 1 } # making it always return 0
#=> [9, 1, 7, 2, 3, 8, 0]
The result is not what I expect. In my expectation, when the spaceship operator returns 0
, every element would stay in the original position. Since the spaceship operator always returns 0
in the example above, the array should remain as is. However, the result is different from the original array.
Is there something I misunderstand?
Updated:
Following was the idea where my question above came from.
Originally I was trying to order objects by their attributes(Let's assume the attribute is status
).
For example
myObjects = [obj1, obj2,..., objn] # the objects are ordered by create_time already
myObjects.sort{|a,b|
case a.status
when 'failed'
x = 1
when 'success'
x = 0
when 'pending'
x = -1
end
case b.status
when 'failed'
y = 1
when 'success'
y = 0
when 'pending'
y = -1
end
x <=> y # compare two objects (a and b) by the status
}
myObjects
is ordered by created_time
already, but I want to sort it again by each object's status
.
For instance,
Two objects with the same created time
(only taking hours and minutes into consideration here, just ignoring seconds) will be sorted again by their status, making objects with failed
status be put at the end of the array.
The x
and y
value in the code above will depend on the object's status,
and x
y
are compared to decide the order. If the statuses of two objects are equal (x == y
), the elements should stay in the same position because they are sorted by created_time
already, no needs to sort them again.
When the status of two objects are both success
, x <=> y
will return 0
.
But according to some comments, the comparison value 0
returned by the spaceship operator seems to output unpredictable order.
What if myObjects
contains elements all with the same status? It would cause the spaceship operator returns 0 all the time since x == y
.
In my expectation, myObjects
should remain the same order since the statuses are all the same, how should I correct when using the spaceship operator in my case?
Many thanks to everyone's help!
Your assumption about how the sorting works is incorrect. As per the documentation #sort
is not stable:
The result is not guaranteed to be stable. When the comparison of two elements returns 0, the order of the elements is unpredictable.
Array#sort
uses Quicksort algorithm, which is not stable and can produce this behaviour when elements are "equal".
Reason is in choosing and moving pivot element at every step, ruby implementation seems to choose pivot at middle for this case (but it can be chosen differently).
This is what happens in your example:
9
at middle of arraysorted_left + [pivot] + sorted_right
, left is empty thus pivot is movedRuby core documentation mentions this:
When the comparison of two elements returns 0, the order of the elements is unpredictable.
Also spaceship operator <=>
does not play any role here, you could just call myArray.sort{0}
for the same effect.
From updated question it's clear that you want to sort by two attributes, this can be done several ways:
Method1: you can invent a metric/key that takes both values into account and sort by it:
status_order = { 'success' => 1, 'failed' => 2, 'pending' => 3 }
myObjects.sort_by{|o| "#{status_order[o.status]}_#{o.created_time}" }
This is not very optimal in terms of extreme performance, but is shorter.
Method2: implicit composite key by writing comparison rule like this:
status_order = { 'success' => 1, 'failed' => 2, 'pending' => 3 }
status_order.default = 0
myObjects.sort{|a,b|
if a.status == b.status
a.created_time <=> b.created_time
else
status_order[a.status] <=> status_order[b.status]
end
}
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