Is Bubble sort slow?

Hello Everyone, Can anyone explain to me, Is bubble sort is slower than the other O(n2) sorting algorithms? If yes, Can anyone give me some examples?

O notation represents relative complexity. So if algorithm A is O(n^2) and algorithm B is also O(n^2), one of them can still be slower than another, if base operations used are slower.

Typically, most of the time you wonâ€™t be implementing sorting algorithms yourself, unless you have specific needs and unique circumstances, and instead youâ€™d use the library version.

A comparison can be found here:
https://en.wikipedia.org/wiki/Sorting_algorithm

That said, currently it seems there are two versions of bubble sort right now, as highlighted, here:
https://stackoverflow.com/a/45645853
And the shorter one has worse performance, as it always hav O(n^2) complexity, while modern bubble sort has best case O(n) complexity.

Thanks I have also checked this on Wikipedia and Interviewbit that shows It has good best case behavior, but is impractically slow on almost all real world data sets and is not considered for implementation in real applications.

If your source says something like that, then the writer needs to improve their programming skills.

Improved modern bubble sort, like insertion sort can perform better than many more efficient algorithms, when it is applied to partially sorted data.

Basically having O(n) for best case may be more desirable than having O(n log n) worst case.

As a rule of the thumb, O(n log n) worst case algorithms do not have O(n) best case performance. And thus they will be slower on sorted or partially sorted data than bubble sort.

Whatâ€™s more on very small arrays performance implication do not matter. If youâ€™re sorting six elements, using heap sort instead of bubble or insertion wonâ€™t yield massive benefits.

Yeah â€¦ that StackOverFlow reply about the â€śoldâ€ť bubblesort is junk. Bubblesort has always used a flag to check if weâ€™re done and give best-case O(n). Weâ€™re not idiots â€“ without that it would be strictly worse than other O(n^2) sorts and no one would ever talk about it or waste time giving it a name.

Notice how the top answers all say its best case is O(n), with no qualifications. That one guy learned it wrong as a kid, recently learned the correct version, and thinks it was just invented.

1 Like

Itâ€™s not junk and it didnâ€™t always use the flag, and the guy in SO answer is right.

The old version of the algorithm is the one youâ€™d know if you learned programming, say, 20 years ago. It looked like this:

Or this:

``````// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n-1; i++)

// Last i elements are already in place
for (j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
swap(&arr[j], &arr[j+1]);
}
``````

It is literally the first algorithm youâ€™d normally learn.

4 Likes

Clearly youâ€™ve forgotten the early days. Borlandâ€™s and Microsoftâ€™s DOS and Windows 3.x era compilers came with bubble sort examples and they were very much the slow variants. In fact Iâ€™m searching right now and I have yet to find the one used by Wikipedia anywhere else.

I donâ€™t doubt that someone, somewhere learned a simplified version of bubble sort. But colleges in the 1980â€™s were definitely teaching bubble-sort with the flag. Weâ€™d teach 3 in-place O(n^2) sorts (in-place: donâ€™t need any extra arrays). They were interesting for different reasons:

Selection is the fastest, making 1 swap per item. Itâ€™s also not â€śstableâ€ť (two items with equal values may be flipped out-of-order, which matters it you have other data). Insertion is slower, doing about n slides per item, but it can quit each pass early, making it faster on almost sorted lists (itâ€™s also O(n) best case). Bubble sort is the slowest, making n swaps per item, but also best case O(n) and only examining adjacent items makes it interesting (this was almost back to when magnetic tape was used for memory â€“ all sorts of funny tricks were needed).

I saw shell sort years ago, which is a really cool sort-of O(n^2). I donâ€™t know how it works, which is probably why it wasnâ€™t taught much.

Without knowing your use case, recommending a sort algorithm or judging one isnâ€™t terribly easy. Why do you need to sort so many things so frequently that any other way wonâ€™t do?

1 Like

This wouldnâ€™t happen to be a question youâ€™ve been asked as a part of some study youâ€™re doing, would itâ€¦?

Very much this. I canâ€™t say I remember clearly, but I believe that back when I was studying we were taught the simplest possible Bubble Sort not to use it, but because it was a simple algorithm to learn and analyse and, indeed, start improving upon immediately.

Does Unity have any sort routines built in?

As with itâ€™s DOTS and Jobs systems surely this is a low hanging fruit that could make sorting a no brainer with Unity?

What about a Timsort â†’ This is the fastest sorting algorithm ever | by Practicus AI | Medium

No, the only sorting functionality built in in any real user accessible way is the same stuff you find in the C# spec.

I think by now we can all safely say that thereâ€™s no such thing as a no-brainer, but ultimately this falls into the same sort of situation as object pooling, but with less game-specific applicability, making it even less likely/reasonable to include as a default feature. Different situations can all require dramatically different sorting algorithms, so the best option for Unity is to stick with stuff like Array.Sort and LINQ as they cover the broadest use cases.

1 Like

I personally used Unity for years, including building a program I used academically, before taking any programming classes (and I only ever took one first-year class), and programming in general is frequently self-taught. Just because it was taught in college doesnâ€™t make it common knowledge.

1 Like

Say someone wrote that we just discovered black holes shrink. Then another person said weâ€™ve known that for almost 40 years. I assume you wouldnâ€™t reply â€śbut there are lots of amateur physicists, so itâ€™s not common knowledgeâ€ť. The important thing for self-taught programmers is there will be lot of holes in what you know, and skimming a decent book will fill in so many basic tricks. I donâ€™t see how wondering which of them is â€ścommon knowledgeâ€ť will be useful. What matters is the trade-off in â€śhow easy is it to learn?â€ť and â€śhow often will I use it?â€ť, which is usually â€śveryâ€ť and â€śa lotâ€ť.

But bubble sort isnâ€™t useful by itself. Itâ€™s mostly an exercise. Itâ€™s a nested loop which actually accomplishes something. Thatâ€™s pretty cool. Itâ€™s a nice example of using a â€śwhile not doneâ€ť style loop with a flag and also a backstop. The middle part is a nice index loop. It also uses the A and A[i+1] indexing tricks, which are more complicated than A and A[j] (doing math inside of the [ ]'s, and working more not to go off the end). Itâ€™s good practice to rewrite them using A[i-1] and A*. But, again, not important to actually know bubble sort. The built-in sort works fine, and Iâ€™ve never solved a programming problem by thinking â€śoh, I can modify a bubble sortâ€ť.*

1 Like

Exactly. I attended a few community college programming classes and one of them covered sorting techniques. We used the base version of the bubble sort because it was an introduction to sorting techniques but then rather than optimize it to be faster we simply moved to alternative techniques.

In the real world youâ€™re just going to shove all of your data into a collection and then ask the collection to sort using whichever algorithm it has implemented. If you need additional performance in Unity you can use DOTS.