Menu
How do I stably sort an array? The value I want to sort by can have a lot of duplicates, and I'm not sure which sort algorithm ruby uses. I'm thinking insertion sort would have worked best for me.
Example:
a = [[:a, 0], [:b, 1], [:c, 0], [:d, 0]]
a.sort_by { |x, y| y } # => [[:a, 0], [:d, 0], [:c, 0], [:b, 1]]
Looking for
[[:a, 0], [:c, 0], [:d, 0], [:b, 1]]
537
Some in-place unstable sorting algorithms can be made stable by altering their implementation to use extra space. If you use this kind of alteration, the algorithm's implementation will become stable, but it will no longer be in-place.
What is a stable sorting algorithm? A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input data set. Formally stability may be defined as, how the algorithm treats equal elements.
Several common sorting algorithms are stable by nature, such as Merge Sort, Timsort, Counting Sort, Insertion Sort, and Bubble Sort. Others such as Quicksort, Heapsort and Selection Sort are unstable.
sort() function usually uses Introsort. Therefore, sort() may preserve the physical order of semantically equivalent values but can't be guaranteed. stable_sort() function usually uses mergesort. Therefore, stable_sort() preserve the physical order of semantically equivalent values and its guaranteed.
Put the key that you originally wanted to sort by and the index into an array, and sort by that.
a.sort_by.with_index { |(x, y), i| [y, i] }
# => [[:a, 0], [:c, 0], [:d, 0], [:b, 1]]
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
