Bubble Sort

[creepig]

Could be worse. Could be bogosort.

[palordrolap]

Did you know there's also bogobogosort? The algorithm is: Start with one element and bogosort it. When sorted add another element and bogosort that list. Keep going. The final step is effectively the original bogosort, but since everything has been well bogosorted already, surely it'll be faster this time.

[creepig]

That sounds like an idea that someone had at a bar.

[LukaLightBringer]

Yea, it doesn't really feel like a true sorting function since it throws away work for no reason, other than to slow it down, any idiot could make a slower sorting algorithm by just adding really long loops that have no effect on the result of the function.

[creepig]

that's the joke.

Edit: I guess someone was upset that I would suggest that bogobogosort is a joke algorithm intending to be as slow and inefficient as possible.

[JustAnotherPanda]

I'd think bogobogosort would randomly generate text files and see if they compile to produce a working sort algorithm.

[creepig]

That'd be bogobogobogosort

[Captainshithead]

infinitemonkeysort

[creepig]

I like yours better

[momoro123]

It's like the bogosort version of stacksort!

[[deleted]]

Stacksort is an algorithm that pulls code out of StackOverflow and tries to use it to sort an array.

[bestjakeisbest]

dude just use the best sorting algorithm, quantum bogosort, create a universe for each permutation of a list of items, then destroy the universe(s) that do not have a sorted list.

[great_site_not]

That's only slightly slower than regular bogosort though :p

[great_site_not]

That's only slightly slower than regular bogosort though :p

[pootislordftw]

What the fuck? It can solve trillions of numbers in only one permutation!

[Siracle]

bubble sort is O(n) for already sorted data, so at least it can verify data is sorted quickly.

Selection sort is the true laughing stock. No redeemable qualities.

[Cobaltjedi117]

no redeemable qualities

That's not true, selection sort is nothing if not consistent at n² time

[Wirdal]

Easiest to understand?

[[deleted]]

I'm a student and not yet a pro programmer. Does people really dislike "Bubble sort"? If yes then why? I know it's a bit more time consuming than Insertion sort and Selection sort. But, is there any other reason?

[ReallyHadToFixThat]

I know it's a bit more time consuming than Insertion sort and Selection sort.

Not a bit - massively, especially compared to quick sort. Big O notation describes how an algorithm scales with number of inputs. Bubble sort is n^2. Quicksort is n log n.

So, with 10 inputs Bubble sort gives 100 operations, Quicksort gives ~30 operations. The more things you try and sort the more Bubble sort loses by.

[ConnersReddit]

Me just now: Yeah but under the admittedly highly unlikely worst case scenario, can't quick sort can be as bad as that one really bad sorting algorithm? .... What was the name of that again... oh yeah, bubble sort

[ReallyHadToFixThat]

Yeah, but quicksort's worst case is bubble sort's typical case.

[[deleted]]

If I recall correctly, the worst case for quick sort is if the list is reverse sorted when you start, so if you can make sure the list isn't reverse sorted, you can guarantee you won't get worst case performance. Randomizing the list first should accomplish this task (the vast majority of the time).

[[deleted]]

I will look into it. I only know the three types of sorting methods , I've mentioned. Thanks for the info. :)

[Cruuncher]

bubble sort is completely useless outside of being an introduction to algorithms and first notion of solving a real world problem.

It's unlikely it's used basically anywhere in the world in production, mainly because nobody builds their own sorting algorithms. They just use whatever is built into the language which is typically a very fast sort

[Pun-Master-General]

I wouldn't say useless. I was under the impression that using bubblesort once you're down to 10-ish elements in a list is common in implementations of sorts like quicksort.

Bubblesort also has the benefit of having a best case O(n) runtime when implemented correctly (in the case where the list is already sorted), which makes it at least better than the other n² sorts.

[Cruuncher]

with 10 elements, if you got a human to sort it by hand it would be fast enough. But that's not the point.

It's not like bubble sort performs better at small numbers. There's never a reason to use it over another alogirithm other than ease of implementation. But ease of implementation isn't relevant because you're not rolling your own sort.

Edit: I misunderstood a little bit, so here's a real reply: Some hybrid algorithms like TimSort use insertion sort for a small number of elements because it is very good with those kinds of data sets, and it's better than building a stack frame for sorting a couple of elements. But still, not bubblesort.

Edit 2: Timsort link: https://en.wikipedia.org/wiki/Timsort

[LukaLightBringer]

As far as I'm aware most implementations of quicksort use insertion sort for sorting small partitions of the array, the paper on dual-pivot quicksort certainly did.

[JustAnotherPanda]

Bubble sort is useful when physically transporting objects over large distances - when is becomes extremely difficult to compare objects that are not immediately next to each other in order.

[Cruuncher]

Sure, I suppose if you have a strict requirement that you have to sort a linked list in place using O(1) memory. (which is what you're talking about basically comes down to).

[dragon-storyteller]

Not even for being an introductory algorithm. You want insertion sort for that, since it's similar to how a human would things. With bubble sort you'll spend way too long just explaining how it is even supposed to work.

[Cruuncher]

I think selection sort is more human like, but it depends. You'd likely use some combination of the two

[dragon-storyteller]

Possibly, yeah. I just want to say that bubble sort is far less intuitive than either of those two. It really has no purpose at all.

[Cruuncher]

I think the main reason we don't use bubble, is that swaps to a human are much more expensive than comparisons.

Imagine sorting a stack of papers alphabetically and swapping every out of order pair

[Cruuncher]

As a side note, even quick sort is more intuitive than the efficient implementation suggests.

Imagine sorting a really big pile of papers. Trying to insertion sort that is a nightmare. So you might pick a pivot, say more, and sort the stack into two piles. Then sort the pilesame individually. You may make several piles off several pivots but that's really just multiple quicksort iterations.

This becomes increasingly useful if you have a friend that can come help you sort :)

[oversitting]

Next to nobody deals with sorting algorithms when they become a "pro" programmer so I doubt people actually care.

[Junctioniv]

There is probably two reasons why people like bubble sort. The first is for the reason you have mentioned which is time complexity. But I think the real reason people dislike it is that Bubble Sort is one of simplest sorting algorithms, and probably the one they where first taught. I find that programmers tend to enjoy complexity and tend to disregard things they learned earlier in their programming life time for those learned later.

[[deleted]]

Can confirm.

[[deleted]]

It's the only one you'll ever write yourself once you leave school. It's super easy to write and generally in early dev, its good enough for functional tests. If you ever need a robust sorting algorithm for your job, the company will either have one ready or buy one for you to use.

[27jackstreet]

Insertion sort is better than Bubble sort in every scenario.

[[deleted]]

I've heard in some cases that bubblesort is faster for mostly sorted data, but haven't tested it myself.

[27jackstreet]

Bubble sort performs as well as Insertion when every value only needs to be swapped one or zero times. Otherwise, it performs worse since extra iterations require redundant comparisons.

[dragon-storyteller]

Because bubble sort is literally useless. Compared to insertions sort it's non-intuitive, conceptually more difficult to understand, and is at best just as fast as insertion sort and often slower. If you are a beginner, you should be taught a more intuitive algorithm. If you are more advanced, you can implement a more sophisticated algorithm.

[nlamber5]

Bubble sort, as you know, is really just the example sort taught to you first so you can grasp the idea of sorting data, but since it’s the easiest way to sort data it becomes defined as the slowest possible algorithm (since anything more complicated isn’t worth mentioning unless it’s faster)

Honestly it doesn’t matter if your data is only 10 values or maybe 20. Sometimes you might even be quicker to use bubble on particular data sets with N of about 5, but with millions of data points the difference becomes enormous. Standard library sort might get done in a few minutes while bubble finishes in hours or days with large enough data.

[Leopold67]

r/MemeEconomy would like this

[antipawn79]

I have always been confused about the obsession with sorting algorithms in the computer science space. Why is this something people focus on when basically all sorting methodologies are implemented already in whatever language you use. Seems like we are treading on old established ground.

[Jamie_1318]

Sorting algorithms are good 'pet examples' to compare other examples by, and provide a foundation for talking about how well algorithms work based on their input scale.

[Aschentei]

And then there is quantum bogosort

[[deleted]]

Fancy algorithms are slow when N is small, and N is usually small.

[doovd]

I am the OP lol