Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Is Bubble Sort the slowest sorting algorithm? If the answer is no, then what is the slowest one?

share|improve this question

closed as not constructive by MichaelT, 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.

14  
As long as your algorithm terminates, you can always make a slower algorithm (by a constant factor, or asymptotically) by adding redundant work. To make the algorithm asymptotically (big O) slower, the redundant work has to grow faster (as the data grows) than the growth of the original algorithm. –  Steve314 May 28 '11 at 6:17
1  
The fact is that giving a precise definition of "reasonable", and so making this question answerable at all, would be a rather difficult task. By far harder than answering most questions on SO. –  Andrea May 28 '11 at 9:31
1  
@Andrea: I am satisfied with CoolBeans' answer. –  xport May 28 '11 at 9:42
3  
This is fine. If the question is just "What are some fun ways to sort slowly?", CoolBeans' is a perfectly good answer. On the other hand, it may have been the case that you thought that your question admitted a rigorous answer, like the similar-sounding, but actually very different, question "What is the fastest way to sort an array?". In this case, it would have been good to clarify that looking for the slowest algorithm is an ill-posed problem. –  Andrea May 28 '11 at 10:09
1  
Bubble Sort is a very slow bathing algorithm for n (number of babies) > 1. –  Jerry May 28 '11 at 10:18

5 Answers 5

up vote 34 down vote accepted

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.

share|improve this answer
2  
+1 for knowing me this funny algo :) –  xport May 28 '11 at 3:59
1  
@xport - Who says developers are just a bunch of nerds - we have our sense of humor too ;-). –  CoolBeans May 28 '11 at 4:00
2  
Of course,of course.. O(∞)?! No,thank you :D –  abhiii5459 May 28 '11 at 4:13
2  
Even Mr. Obama did not know this algorithm. youtube.com/watch?v=k4RRi_ntQc8 –  xport May 28 '11 at 4:25
2  
BogoBogoSort is even better. Apparently it has a complexity of O(N!^n) or similar. Looky here: dangermouse.net/esoteric/bogobogosort.html –  evgeny May 28 '11 at 4:48

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.

share|improve this answer
    
+1 for several points, but I don't see how bubble sort can be considered asymptotically as fast as mergesort or heapsort, both of which are worst case O(n log n), whereas bubblesort is worst case O(n^2). In practical performance, randomized quicksort is often the real winner, despite also being O(n^2) worst case, but that's not really about asymptotic performance. True, quicksorts is O(n log n) expected, but so are some other sorts - the real-world performance gains relative to e.g. heapsort are due to cache-friendliness and simplicity. –  Steve314 May 28 '11 at 6:23
15  
@Steve314: The restriction is basically a machine with drum memory that restricts you to access to two adjacent items at a time, with the window constantly moving in one direction (and when you reach the end, you can re-start at the beginning reasonably cheaply, but random access is really expensive). Heapsort basically requires random access. Mergesort is fine with sequential access, but requires non-adjacent sequences. –  Jerry Coffin May 28 '11 at 7:34
    
@Jerry - interesting restriction. –  Steve314 May 28 '11 at 8:57
3  
@Mason: I can see people inventing either insertion or selection sort, and when they figured out the problem with O(N*N) algorithms, probably merge sort. Bubble sort strikes as much less intuitive than any of the above. –  Jerry Coffin Jun 3 '11 at 18:59
1  
@JerryCoffin I think a catchy name has a lot to do with popularity of the method: a sort by any other name would not smell as sweet :) –  dasblinkenlight Aug 16 '12 at 18:13

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:

http://www.sorting-algorithms.com/

share|improve this answer
    
+1 for the link, unfortunately my response time is so slow to determine which one finishes first. –  xport May 28 '11 at 5:50

Bozo sort is O(n!)! It is done by randomly picking two elements swapping them and checking whether the list is sorted.

share|improve this answer

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.

share|improve this answer
1  
That's true of cocktail sort, but not bubble sort. Bubble sort only runs in one direction, so one out of place element is potentially enough to make it run in O(n^2). –  Brian Mar 19 '13 at 15:10
    
If you only have 1 out of place element, bubble sort will put it in place in O(n) time. –  Kevin Hsu Apr 8 at 21:41
    
That is incorrect. For example, suppose your list of n elements was almost sorted, with only one out of place element. Specifically, with the first element incorrectly placed at the end. Then, there will be O(n) iterations of bubble sort, each of which will read the entire n elements of the list, resulting in O(n^2) time. Iteration 0: 2,3,4,...,n-1,n,1, Iteration 1: 2,3,4,...,n-1,1,n, Iteration 2: 2,3,4,...,1,n-1,n, etc. Cocktail sort, on the other hand, would only require one iteration, and thus is O(n). –  Brian Apr 9 at 4:09
    
Ah, I understand your point now that I've read up on it. I imagined an intelligent version of bubble sort to be bidirectional, and that such a thing would still be called bubble sort, so thank you for clarifying that such an optimization has a different name. –  Kevin Hsu Apr 9 at 9:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.