-
-
Notifications
You must be signed in to change notification settings - Fork 1.6k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Use a stable sort algorithm (Was: Sort order of Array#sort(&block)) #2350
Comments
I inquired about this a few days ago. Ultimately this is not a bug, but should perhaps be reconsidered. The term you're looking for is stable sort. Indeed, many languages' built-in sorting algorithms are stable, even though this property slightly limits the performance of sorting. C++, on the other hand, made a separate I think the most popular sorting method is Timsort, used in Java and Python, and it is stable. Quicksort, which Crystal uses, does not have this property. |
bcardiff shared this example code https://gist.github.com/5395bfaef35ac1d14a1a This adds the original indices of the items to the key tuples to keep the original order. |
We just have a hand-made quicksort to be able to sort stuff, but we didn't actually though a lot about which algorithm to use and if we want it to be stable. So asking this here is a good chance to start the discussion 😸 |
(that is, because we wanted to bootstrap the compiler and it uses sort...) |
It seems that after 53be65d sorting Array is stable: Before
After
I suspect this issue is resolved then and we can close it? |
Maybe it's worth checking more thoroughly, seeing as 2 different algorithms are used... |
@BlaXpirit Of course, good point! %) |
@BlaXpirit You are right. It's stable until a size of 16:
So, it's not stable enough ;) |
@splattael
|
@c910335 So, Ruby's behaviour has changed in a patch level 😱 In Ruby 2.3.1 it is stable:
The sentence TBH: I wish it was stable ;) |
On my machine Ruby 2.3.2 is still stable 😮
(╯°□°)╯︵ ┻━┻ Computering is hard. Let's go shopping. |
I did some research which I have should done before submitting this issue. Ruby's sort is not stable. It never was. (Maybe it was stable by accident).
I am closing this issue. Sorry for the repetitive noise :-( |
@splattael nice work 👍 |
Go for example provides two https://golang.org/pkg/sort/#Sort |
Whoa, I always assumed ruby's sort was stable. I've even always used it as if it was stable Even just tried it:
Weird. Appears it just calls the C level qsort_r function: https://linux.die.net/man/3/qsort Which is different on OS's. I think java avoids confusion by sorting "natives" (like ints) using quicksort (since reordering is not detectable), and sorts class objects using timsort, so in the end everything "looks" stable, by default. Also wonder if Timsort is faster than the workarounds that people propose on ruby-core (#with_index etc.) which don't seem very fast in some benchmarks I saw: https://bugs.ruby-lang.org/issues/1089 ("5x slower") |
Hi,
today I've stumbled across the sort order of arrays using a block.
I would expected that
[1, 2] == [1, 2].sort { 0 }
to betrue
.It is
true
for at least Ruby and Java. In Crystal it'sfalse
.Is it a bug or just an undefined behaviour of quicksort?
Kind regards,
Peter
The text was updated successfully, but these errors were encountered: