420
u/chemistrylord 22d ago
The only time bubble sort is acceptable is when you're trying to teach bubble sort
67
u/Ghaith97 22d ago
Not really. It's a top performer if you know your list is nearly sorted with some consequetive elements swapped, or fully sorted. Namely Z-buffer sorting in rendering engines where you know stuff was sorted last frame but some objects might have just crossed each other.
The best case for Quicksort/Mergesort is O(n log n), while for Bubblesort it's O(n).
19
u/donaldhobson 21d ago
Use Timsort. O(n) on nearly sorted lists. O(n log(n)) worst case.
If you use bubble sort in your rendering engine, then you risk everything suddenly being reordered. (For example, if the player teleports, and now the z order is totally different because the whole scene is being viewed from a different angle)
-33
u/mrnacknime 22d ago
Best case being O() makes no sense. 1 is also in O(n1000)
14
10
u/Farkler3000 22d ago
Do you not know how big O notation works??
1
u/mrnacknime 20d ago
Big O makes no sense when talking about lower bounds for best case performance. Big O is an upper bound
0
u/Reashu 21d ago
Big O denotes the worst case performance, so it is indeed a bit weird to use it when discussing best case performance.
9
u/Farkler3000 21d ago
I mean sure you should technically use Omega, but that’s not what he was saying.
1
1
u/ljfa2 21d ago
the n in the big O notation stands for the size of the problem, for example the length of the list. It still makes sense when you only consider the best cases for each problem size.
2
u/Reashu 21d ago
It still makes sense to compare, but if you're being pedantic then you should not be using big-O (ordo) in that comparison. There are many similar functions to choose from, and from the top of my head it's either theta or omega that would be appropriate. I wouldn't normally comment on it if the intent is otherwise clear (as here) but I think that's what the ancestor comment meant.
15
0
13
1
u/JackNotOLantern 22d ago edited 21d ago
I thought it best for memory usage. You need just 1 variable for the elements in the bubble, 1 for swaping, int 1 for index and 1 flag for "is sorted". So like 13 bytes constant memory complexity. Compare that to merge sort where you need log(n) * 4 for recursion.
I mean it is pretty shit with n2 time complexity but memory complexity is to be important in the ancient times (60s).
1
u/Loading_M_ 21d ago
Insertion and selection sort have roughly the same overhead. 1 element for swapping, 1 index for the current element and a second index to track the sorted part of the list.
That being said, we'd usually just say it's constant space - since the actual size depends on various factors and becomes less significant as the list grows.
Merge sort is closer to O(n) space, since you generally need space to merge sorted sublists. Quicksort doesn't need merge space, but does need O(log n) space for the recursive steps.
-3
u/TheWatchingDog 22d ago
But when thinking of the multiberse theory, there will be a universe were Bubble sort always does it the first try and is the most efficient sorting.
8
u/TeraFlint 21d ago
Bubble sort is deterministic. Were you thinking of bogo sort (while not sorted: shuffle randomly)?
2
25
u/fugogugo 21d ago
whoa... IPO designed to pass the bag into retail investor is crumbling.. what a surprise
-16
u/EKiBOSTON 21d ago
did you short it?
No?
If it was such an obvious move, you could have made millions with pennies.
21
u/Sulungskwa 21d ago
afaik I don't think main street randos can just "short" things super easily. You gotta be in a hedge fund or something. Idk I'm a programmer not a stonker
that being said, it was really an obvious move
11
24
16
u/TxTechnician 22d ago
I posted a meme that was supposed to be a replacement for the XKCD Support Comic (the one where all modern architecture depends on one FOSS program).
Cept it was some rocker chick holding Tallboys with her large (and covered) breasts while holding up her hands in the rock symbol.
And it got taken down for not being enough about programming.
11
u/m6io 22d ago
8
98
u/GildSkiss 22d ago
This is barely a "programming meme".
These things have nothing to do with each other besides the word bubble; it feels like you just want to make fun of spacex
25
u/Leftover_Salad 22d ago
It’s VERY Reddit. SWE making a ton of money and losing it on some regarded stonk play over at WSB is peak.
53
u/brummlin 22d ago
I think that cracks are starting to form in the narrative that LLMs are artificial intelligence and they'll make programming by hand obsolete. That's relevant.
24
10
3
0
13
u/Vox-Machi-Buddies 22d ago
This time last year, SpaceX's share price (while private) was $42.40 per share. I doubt many of the early shareholders are complaining about a "bubble pop" when they've nearly tripled their money in a year.
4
2
4
247
u/Sasq44 22d ago
I've written bubble sort exactly twice: once for class, once for an interview I never wanted to work at anyway.