I haven't tried to coded a sort with just one for loop - but with some "spaghetti code", it should be possible (to do a bubble sort with recursive calls are also possible - with only one for loop, but it wasn't what I was thinking about).
But then you are right - it will no longer be a bubble sort, if it is done with "spaghetti code"
Hunter McMillen wrote:Would that spaghetti code actually improve the performance of the sort? Or would the one-loop bubble sort still be O(n**2)?
Hunter
If you look in the java.util.Array.java source file - http://kickjava.com/src/java/util/Arrays.java.htm - you will see that there is not only one implementation of a sort - it depends on the size of the array to sort.
A small array where the size is < 7 - is a bubble sort.
My question was if you managed to implement bubble sort with one for loop wouldn't that make it O(n) instead of O(n**2) ? So shouldn't it be more effective at sorting.
Hunter
"If the facts don't fit the theory, get new facts" --Albert Einstein
If it really is bubble sort still, it will surely still run in quadratic time. I should be very interested to see how it is implemented with a single loop.