Re:Is this the simplest (and most surprising) sorting algori...
by SamBam on Tuesday October 05, 2021 @10:51PM
(#28768620)
> What’s non-intuitive
Well, for me what's non-intuitive is that if we started with a fairly-well ordered array:
[ 1, 2, 3, 5, 8, 4, 9 ]
The very first thing the algorithm would do would be to swap 1 and 2, even though they are already in the right order. The next thing it would do would be to swap 2 and 3, making it even worse. And so on, all the way down the line. It takes six swaps to put 1 finally back to where it belongs, and the rest of the array is hopelessly out of order.
It does work, yes, and you can eventually grok it, but I feel like you're not being honest to call this a completely intuitive algorithm to new CS students.
Well, for me what's non-intuitive is that if we started with a fairly-well ordered array:
[ 1, 2, 3, 5, 8, 4, 9 ]
The very first thing the algorithm would do would be to swap 1 and 2, even though they are already in the right order. The next thing it would do would be to swap 2 and 3, making it even worse. And so on, all the way down the line. It takes six swaps to put 1 finally back to where it belongs, and the rest of the array is hopelessly out of order.
It does work, yes, and you can eventually grok it, but I feel like you're not being honest to call this a completely intuitive algorithm to new CS students.