> Depends on what kinds of mistakes the almost-correct approach makes. If it just puts elements in the wrong order, your suggestion works. But if it makes mistakes like duplicating elements, or dropping them, or completely making up new entries, no post-processing will help.
The algorithm modifies the original list only by swapping entries. As such, it's guaranteed to result in a permutation.
Yes, in that case the post-processing would work.
But it also limits their system to in-place algorithms only.
Why is this limitation? Do you think the algorithm can be improved if it was doing a copy to a new location?
Re:Neural programmer better than Quicksort
by im3w1l-alt on Friday July 10, 2020 @10:58AM
(#23792122)
If you let the number of objects to sort go to infinity while keeping size of objects in bits capped, then they will behave like integers.
I thought more of being able to do bit manipulation or hashing etc on your keys. Those things don't necessarily require a fixed key length. (And in some languages, even integers don't have a fixed length.)
You are right in some sense, but you'd still have trouble implementing something like bucket sort in your setting, if all you have are comparisons.
Depends on what kinds of mistakes the almost-correct approach makes. If it just puts elements in the wrong order, your suggestion works. But if it makes mistakes like duplicating elements, or dropping them, or completely making up new entries, no post-processing will help.
> OTOH the standard library sort can be improved if you know the distribution of the numbers you're sorting (e.g., small numbers can bucket sort, small lists can use a sorting network, etc).
Even better: the standard library sort usually assumes only comparison. For special cases like sorting on integer keys you can conceivably do better.