Also, Bubble sort always swaps two adjacent elements, while this algorithm swaps elements that are arbitrarily far apart! A Rust playground, if anyone wants to play around with it. (It seems to make the same number of swaps as Bubble Sort. And ~twice as many comparisons, of course, since it does exactly n*n comparisons and Bubble Sort does exactly n*(n-1)/2 comparisons.)
I was going to say it looks to me like a less-efficient insertion sort… but I just skimmed the linked PDF, and the author admits that about halfway through, so they knew that too.
I bet many undergraduates “discovered” this sorting algo when doing their CS101 homework, only to be told by their study buddy they were wrong.
It seems like an extremely trivial algorithm to me? It’s just bubblesort without the bail-out, no?
Note that the condition for whether the swap should occur is, intuitively, completely backwards!
Also, Bubble sort always swaps two adjacent elements, while this algorithm swaps elements that are arbitrarily far apart! A Rust playground, if anyone wants to play around with it. (It seems to make the same number of swaps as Bubble Sort. And ~twice as many comparisons, of course, since it does exactly
n*ncomparisons and Bubble Sort does exactlyn*(n-1)/2comparisons.)https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=c72e58050b15bf76da23144685caefe4
Missed both differences completely, thanks both!
I was going to say it looks to me like a less-efficient insertion sort… but I just skimmed the linked PDF, and the author admits that about halfway through, so they knew that too.