Talk:Bubble sort

From Algorithmist
Jump to navigation Jump to search

Hmm. How is this fourth optimization any different from the third? It looks to be identical. I was reluctant to clean up RavenX86's edit because I wasn't sure what he was saying. I didn't want to rollback a potentially valid contribution. Sartak 15:56, 14 Apr 2006 (EDT)

RavenX86's version (or my somewhat polished one) is in fact linear for a sorted array. It is an improved version of the third optimization in that the part of the array that is left untouched can be longer. On the array { 5, 4, 3, 1, 2, 7, 8, 9 } already in the second pass we would iterate only over the first 3 pairs.

Of course, being bubblesort, it still sucks. But it is an improvement nevertheless ;) --Misof 17:52, 14 Apr 2006 (EDT)

Ah. Thanks. I'll include that bit in the article. Hey, the first optimization makes bubblesort linear for a sorted array too. ;) Sartak 16:57, 15 Apr 2006 (EDT)