Re: rosettacode 500 milestone passed
- Posted by Spock 1 week ago
- 180 views
That seems pretty good, not that I've analysed it in any detail.
I have to ask, are you quite certain there are no data sets that might ever need a treble or quadruple (etc) swap?
I am quietly confident that swapping just 1 or 2 elements is enough to eventually reach the optimal choice. But having a pathological data set (rather than some Rosetta Code toy..) to experiment with would be prudent.
I am now not so sure the algorithm is finding the global maximum because dropping the initial sort produces a sub-optimal (though still good) result.
A more rigorous investigation would be to compare the algorithm against a brute force solver to find any pathological cases..