Is bubble sort the least Big-O efficient? If the answer is no, then what is the least efficient sorting algorithm?
closed as not constructive by user40980, Martijn Pieters, gnat, Joris Timmermans, Jimmy Hoffa Mar 19 '13 at 17:15
As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. If this question can be reworded to fit the rules in the help center, please edit the question.
I vote for BogoSort to be the worst if you are comparing based on worst case performance only!
Visit this wiki link to get a general idea of run time comparisons of different sorts. The sort performance is always highly dependent on your data and scenario. It's hard to say one to be the worst always.
Short of the intentionally perverse, there is still one that's slower than bubble sort, but has a real reason to exist (sort of, anyway). Knuth V3 (in one of the exercises) shows an algorithm optimized to minimize code size. It does produce extremely small code -- at the oh-so-minor expense of O(N3) complexity.
Although the chances of actually encountering it with modern hardware are nonexistent, it's also worth mentioning that under precisely the correct set of circumstances Bubble sort isn't really such a terrible algorithm at all -- rather the contrary, within the exactly correct set of constraints on the hardware it's provably not only as good as anything else, but asymptotically approaches the best performance of any possible algorithm.
In fact, that proof appears to be the primary reason it became reasonably widely known -- it's virtually the first algorithm for which any such formal proof was ever published. OTOH, that's almost lost in the mists of time, and most of the people who teach it have no idea why it originally became known. Instead, as far as I can tell, people teach it solely because they learned it, and for some reason think it's important for the next generation to learn about it even though the reason for its existence disappeared long before most of them were born.
If you are going to include intentionally perverse algorithms, then the bogobogosort is much worse than the plain bogosort. A plain bogosort has a complexity of approximately O(N * N!). The bogobogosort has a complexity of approximately O(NN-k). To put this in perspective, bogosort can sort 10 items in a matter of only a few minutes (or so). The number of operations needed for a bogobogosort grow so fast that to the best of my knowledge, the largest number of items anybody has ever sorted with it is 6 (attempts have been made at 7, but, at least to my knowledge, all such attempts have been terminated before completion (though, admittedly, that's usually after only a day or two).
The speed of any particular sorting algorithm depends on a few different factors such as input order and key distribution. In many cases bubble sort is pretty slow, but there are some conditions under which it's very fast.
There's a great sorting algorithm comparison animation at this site:
Bozo sort is O(n!)! It is done by randomly picking two elements swapping them and checking whether the list is sorted.
If you know that your data is almost sorted already, and that only a few elements are out of place, bubble sort becomes about O(c*N) time, where c is the number of out of place elements. In that instance it will actually be faster than most other sorts. Bad worst case, good best case.