6 ms·

When would you ever want bubblesort?

93 points by BerislavLopac 3y ago

david_allison 3y ago
It's O(n) if the array is already sorted, which is better than other n*log(n) CS101 algorithms (merge/heap/quicksort)
- dockd 3y ago
  That's my memory from college: bubble sort is fine when the data is almost completely sorted.
- GuB-42 3y ago
  Unless the element that should be at the start is at the end, everything else being sorted (ex: 2 3 4 5 6 1). Insertion sort is the best simple algorithm for almost sorted lists. In fact, it is generally considered the best O(n2) sorting algorithm.
Animats 3y ago
Bubble sorts are useful in broad-phase collision detection. Each object has an axis-aligned bounding box, and you want to sort those by X, Y, and Z values, then check for overlap in all dimensions. Only if the bounding boxes overlap in all three dimensions do you have to check the object pair's detailed geometry. Most objects aren't moving that much. The lists are thus almost in order. So running a bubble sort on each axis to check the ordering is not much worse than O(N). Startup has a transient. The very first sort will be O(N^2). If the number of objects is large enough it may be worthwhile to do something different at startup.
- phkahler 3y ago
  Funny, if I were doing that I'd use a spatial index using oct-trees since I have a fairly optimized one. You find all potential overlaps in O(logN), But to check them all would be O(NlogN). So by your approach it looks like bubble sort wins!
- indigo945 3y ago
  > Most objects aren't moving that much. [citation needed]. Even just one object moving from one end of an axis to the other end would incur catastrophic slowdown, and depending on what you are simulating, this might occur regularly (for example, consider teleporters in a video game). When that happens, you incur the full O(n^2) iterations until the axis is sorted again, even though only one object is actually out of order. There are certainly simulations where this approach is fine (if you can be absolutely confident that no object ever "skips" around, like when you're running a simulation that is configured with an explicit upper bound on velocity), but I think that this still requires this warning label.
harry8 3y ago
Bubble sort is just fantastic to wind up arrogant algo-nerd snobs because you can bust it out for anything that is likely to be already sorted or nearly so and it dominates. Algo-nerd snobs rarely seem to take into account that knowledge and understanding of the input is the most crucial part. Do it in job interviews only if you've already decided you're unlikely to want to work there and be sure to be smiling and humble as you demonstrate this to their peers, noting that the pure forms of the algo, selection sort is arguably better (Knuth!) but this is unlikely to be an interesting practical concern and totally dwarfed compared to readability of the code.
- minitech 3y ago
  > it dominates Not compared to insertion sort, which is the actual contender here. Weirdly aggressive comment.
deleted 3y ago
[deleted]
jbandela1 3y ago
For an N^2 sorting algorithm, I think insertion sort is superior to bubble sort when you want something simple: http://warp.povusers.org/grrr/bubblesort_misconceptions.html http://warp.povusers.org/grrr/bubblesort_misconceptions.html
- svachalek 3y ago
  That link seems to insist on defining bubble sort without a termination condition, which is not how I think of bubble sort and I suspect is not how anyone is defining it in the cases it argues against. Also the use case in this article isn't listed.
vandyswa 3y ago
When the bucket of things to sort drifts below count ~100, bubble sort will hammer it into order in an amount of time which is, for all intents and purposes, zero. Use the smallest hammer which drives the nail...
- kevin_thibedeau 3y ago
  Also a good time to shelve any binary search because linear search will beat it for short sequences. The threshold varies by platform.
- dekhn 3y ago
  This is also known as "hardware caches and branch prediction beat smart humans almost every time"
dxbydt 3y ago
Can I have Cheeky Retorts for $100 Alex. 1. If you have a very large (say 100 million elements ) array in descending order, you can use Bubblesort to sort it in the ascending order - the worst case complexity is kn^2, and this is literaly the worst case, so its the equivalent of a sleep(t) routine for a large t ( depending on how sow your system is). 2. If you have a very small array (say n < 10), you can create toy examples where kn^2 < m*nlogn, for carefully chosen values of k, m & n. Say n = 3, k = 1, m = 7.
dahart 3y ago
> On some very particular hardwares bubblesort stills ends up better, like in this NVIDIA study, but you probably don't have that hardware. The author might have misunderstood the hardware in question and the reasons why bubble sort works well here. You probably do have applicable hardware; it’s any GPU. The bubble sort wasn’t running on ray tracing hardware, it was just CUDA code. The reason bubble sort works well is because it’s running on a SIMD machine, and it’s better when all threads in a work unit (a “warp” in CUDA parlance) all do the same thing at all times. If you try to do insertion sort on a SIMD machine, you’re very likely to approach worst-case O(N^2) performance very quickly, even when each individual thread involved would have had average-case perf on it’s own. Bubble sort is good for the parallel SIMD machine because of it’s deterministic and regular evaluation order that is the same across all threads. Of course, it’s still true that for anything larger than very small arrays of data, bubble sort complexity is unacceptable on SIMD or parallel processors. There are better parallel sorting algorithms for that.
- lifthrasiir 3y ago
  In the other words, you are sorting lots of equally-sized slabs at once, and you can do the same operation to each slab efficiently. Algorithms with no data-dependent control flow would be optimal in this situation, and bubblesort is one of them. But there are even better algorithms, I think shellsort with a fixed gap sequence (since the slab size is known in advance) could've been a good alternative. On the other hands, if you are sorting a single huge list, you need a parallel sorting algorithm like bitonic sort.
Syzygies 3y ago
In college in the 1970's, I took a combinatorial algorithms class with Herb Wilf. He explained that choosing a subset of k distinct elements from 1..n uniformly at random was likely k log k, because you needed to detect collisions, and "sorting" k elements was k log k. (Always check your assumptions. Sorting has an k log k lower bound if all you can do is compare elements. With integers 1..n, one can do much more.) I showed up at 5pm at his office, as he was bracing himself for the drive from Swarthmore back to Philly, wondering why he ever took this gig. I proposed a linear algorithm: Break 1..n into k bins, and only sort to detect collisions within each bin. Bins would have an average occupancy of 1, so it didn't matter what sort you used. (I found this idea later in Knuth, and was briefly disillusioned that adults didn't read everything.) I looked like George Harrison post-Beatles, I probably smelled of pot smoke, and he dismissed my idea. Then my dorm hall phone rang at 10pm, a professor of mine relaying an apology. For that and other ideas, the second edition of his book opened with thanks to me. I'm surprised now that I realized then that bubble sort actually had the least overhead, in such an application. People don't use Strassen to multiple matrices unless the matrices are really big. For sorting, "really big" is 2 or 3 elements.
- hakuseki 3y ago
  I guess you mean k log k, not n log n.
  - Syzygies 3y ago
    yep, thanks. "n log n" is how one always says it, it becomes a local variable in its phrase. Oops.
- a1369209993 3y ago
  > Bins would have an average occupancy of 1, so it didn't matter what sort you used. That's not quite right, though - you only care about the average occupancy if your sorting algorithm is O(b) for b elements. If you're using a O(b^2) sort, you actually care about the root-mean-square occupancy (or in general just the average runtime, or just the total runtime since you'll multiply the average by the number of bins anyway). The k-bin approach is definitely much faster than O(k log k), but I'm fairly sure it's slightly slower than truely linear, asymptotically, since the runtime will be something like 1+0+4+1 in typical cases, where linear would have to be 1+0+2+1. Edit: on some cursory Monte Carlo testing, the sum of squares of occupancies actually seems to still converge on a constant factor (of two) times the sum of plain/linear occupancies, which I was not expecting but does make the above point rather moot. (Also, the sum of cubed occupancies seems to converge on a factor of five, which seems downright bizzare.) (Tangential edit: The factors seem to be 1 2 5 15 52±2 200±20, which might be https://oeis.org/A000110 https://oeis.org/A000110, though none of the interpretations there seem obviously related.)
glitchc 3y ago
Bubble-sort is great if you have many cores to spare but no extra memory. It parallelizes nicely and works in-place. Insertion sort is great if you don't have any cores or memory to spare. It uses one core and works in-place. Selection sort is much like insertion sort, runs in-place, single-threaded, but it will be faster if your CPU is much faster than your memory access as it uses more comparisons and fewer swaps.
doubloon 3y ago
Because in a certain company i couldnt use anything except a limited old language and there was no straightforward way to sort a list of custom types and internet searching was limited . You cannot just download your favorite open source library or whatever in a lot of environments, you are stuck with the tools you got.
JKCalhoun 3y ago
Bubblesort's big advantage is that it's the one sorting algorithm that I understand well enough to write from scratch in pinch.
whartung 3y ago
I've done this. In a production application. Why? It was the easiest sort I had memorized, I didn't have my college Data Structure 201 book handy. It did exactly what I wanted. And for my datasets, it was not impacting performance. Measurably? Probably. Noticeably from the user level? No. If it was slow, I would have changed it. I did it in BASIC. But it was never my bottle neck. We're talking 10 or less items here most of the time, my bottleneck was sucking rows from the ISAM database on our 10 user, 16Mhz 68020. I was doing best fit scheduling across a selection of resources. It was a very cool system.
jqpabc123 3y ago
Why bubble sort when a slight modification can create a still simple but much more respectable algorithm called "comb sort". https://www.delftstack.com/tutorial/algorithm/comb-sort/ https://www.delftstack.com/tutorial/algorithm/comb-sort/
- jqpabc123 3y ago
  Comb sort tip --- instead of dividing by 1.3 use 1.333 (repeating) instead. In practical terms using integers, this makes almost no difference *except* it can be performed using faster shift and add operations: gap = ((gap << 1) + gap) >> 2; For even more speed, I'd also recommend in-lining this to eliminate the function call. Properly implemented, respectable speed can be achieved from a really trivial implementation.
deleted 3y ago
[deleted]
globular-toast 3y ago
The game dev example is really cool. I've never encountered a situation where "more sorted" is better for performance but completely sorted doesn't really matter (or maybe I have, but didn't know it). When you read Knuth's The Art of Computer Programming he challenges you to come up with your own sorting algorithm. I feel really fortunate that I was able to do this without knowing any algorithms already. I came up with bubblesort. I think it was the intuition of thinking about it becoming "more sorted" on each pass that led me there.
thecleaner 3y ago
Bubble sort's true complexity is O(n+d) where d is the number of inversions in the array. So if an array is almost sorted better to use bubble sort.
Quimoniz 3y ago
[dead]
forgotmypw17 3y ago
I used bubble sort for sorting an HTML table, because, as others say, it is easy to write quickly. It stayed that way until I asked gpt to rewrite it for me.
cyco130 3y ago
Before I knew anything about sorting algorithms, I invented my own algorithm to sort the high score list in my little BASIC game. It was very simple: Find the highest score, swap it to the top and continue, this time starting with the second item, until done. I imagine that if I ever find myself in need of writing a sorting algorithm from memory, I'll still go with this one.
- plingbang 3y ago
  Sounds like Selection sort[1]. It was probably the first sorting algorithm I ever implemented. I don't know why bubble sort is usually taught first. Selection sort seems more obvious. Perhaps the implementation is slightly harder due to the need to keep track of two indexes. 1. https://en.wikipedia.org/wiki/Selection_sort https://en.wikipedia.org/wiki/Selection_sort
jfengel 3y ago
I've written a sort perhaps a handful of times in the last 40 years. Each of those was a bubble sort. I was nearly-always sorting <4 elements (and often just 1, or even 0). These were rare cases where I didn't have a sort algorithm in a library -- perhaps because I needed to pass in a comparator that wasn't easily supported in the language. So I banged out whatever was easiest to get me moving on to the actual problem. If the sort became a noticeable part of the running time, I'd deal with that when I had performance numbers. Bubble sort was easy to remember and quick to bang out. For all I know I really was writing an insertion sort; all O(n^2) sorts look pretty much the same. I haven't written any sorts at all in well over a decade, since all languages have substantial support. If I'm writing a sort, something has gone very wrong.
- JohnFen 3y ago
  > I was nearly-always sorting <4 elements (and often just 1, or even 0). In my opinion, a bubble sort is a solid choice for that sort of use case.
  - Trufa 3y ago
    Are you being cheeky? Cause I would think insertion sort would be a more than reasonable alternative
    - JohnFen 3y ago
      No, I'm serious. With datasets that small, there's very little performance difference between the two methods, so a bubble sort isn't unreasonable at all. Depending on the circumstances, a bubble sort can be the better choice due to other considerations becoming relatively more important.
    - bastawhiz 3y ago
      In what way?
    - usefulcat 3y ago
      Especially if there’s little or no performance difference, may as well minimize code size.
aappleby 3y ago
Can confirm, have used bubble sort in a production game engine to keep transparent objects mostly sorted. You do the compare-and-swap when you're iterating over the objects to do some other render pass, so it adds almost nothing to the CPU time.
- phkahler 3y ago
  >> bubble sort in a production game engine to keep transparent objects mostly sorted. A single pass of bubble sort per frame is often enough to keep things in order. And if something glitches because it takes 2 passes it's just a single frame glitch!
- jcalvinowens 3y ago
  > so it adds almost nothing to the CPU time. If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant?
  - pengaru 3y ago
    > > so it adds almost nothing to the CPU time. > If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant? I think it's apparent they didn't mean the CAS atomic instruction, just the compare-and-swap operation in bubblesort. Nothing in their comment suggested this was a multi-threaded situation.
    - jcalvinowens 3y ago
      >> You do the compare-and-swap when you're iterating over the objects to do some other render pass OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? That seems kind of wild to me but I don't know why else you add the words "some other". Sometimes sorting is an optimization and isn't necessary for correctness. The idea of two threads concurrently bubblesorting the same array with CAS is hilarious and intriguing. On x86 the double-wide CAS requires double wide alignment so I guess it couldn't actually work without extra trouble...
jcalvinowens 3y ago
Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.
- lifthrasiir 3y ago
  Unless you have a thousand of sorting routines it wouldn't matter much. And compilers generally produce a much larger code than actually possible, you can implement bubblesort in 16 bytes of x86-32 assembly [1] for example. [1] https://gist.github.com/jibsen/8afc36995aadb896b649 https://gist.github.com/jibsen/8afc36995aadb896b649
  - jcalvinowens 3y ago
    It matters a great deal if you have 1KB of flash to fit the whole firmware in :)
    - lifthrasiir 3y ago
      Oh, if you are already writing an assembly my comment doesn't apply ;-)
- acdha 3y ago
  I was expecting that, too. The one person I’ve heard say they’d implemented bubble sort in the current century worked on automotive controllers where they had absurdly tight memory budgets and the data he had to sort was relatively small so they quite happily traded a few cycles for the smaller executable.
- padf 3y ago
  Yes. Ignorant question: if you use bubble sort but go through the array in alternating senses, could it not improve locality and speed? Array v with N elements: First pass: go from v[0] to v[N-1] comparing v[i] with v[i+i] Second pass: go from v[N-1] to v[0] comparing v[i] with v[i+i] This is so obvious that it should have a name...
  - 3y ago
neverartful 3y ago
It would likely be handy during your exams in CS 101.
- ErikBjare 3y ago
  This blog post would make a fantastic addition to the sorting part of a CS101.

93 points by BerislavLopac 3y ago

david_allison 3y ago

It's O(n) if the array is already sorted, which is better than other n*log(n) CS101 algorithms (merge/heap/quicksort)

dockd 3y ago
That's my memory from college: bubble sort is fine when the data is almost completely sorted.
GuB-42 3y ago
Unless the element that should be at the start is at the end, everything else being sorted (ex: 2 3 4 5 6 1). Insertion sort is the best simple algorithm for almost sorted lists. In fact, it is generally considered the best O(n2) sorting algorithm.

Animats 3y ago

Bubble sorts are useful in broad-phase collision detection. Each object has an axis-aligned bounding box, and you want to sort those by X, Y, and Z values, then check for overlap in all dimensions. Only if the bounding boxes overlap in all three dimensions do you have to check the object pair's detailed geometry. Most objects aren't moving that much. The lists are thus almost in order. So running a bubble sort on each axis to check the ordering is not much worse than O(N). Startup has a transient. The very first sort will be O(N^2). If the number of objects is large enough it may be worthwhile to do something different at startup.

phkahler 3y ago
Funny, if I were doing that I'd use a spatial index using oct-trees since I have a fairly optimized one. You find all potential overlaps in O(logN), But to check them all would be O(NlogN). So by your approach it looks like bubble sort wins!
indigo945 3y ago
> Most objects aren't moving that much. [citation needed]. Even just one object moving from one end of an axis to the other end would incur catastrophic slowdown, and depending on what you are simulating, this might occur regularly (for example, consider teleporters in a video game). When that happens, you incur the full O(n^2) iterations until the axis is sorted again, even though only one object is actually out of order. There are certainly simulations where this approach is fine (if you can be absolutely confident that no object ever "skips" around, like when you're running a simulation that is configured with an explicit upper bound on velocity), but I think that this still requires this warning label.

harry8 3y ago

Bubble sort is just fantastic to wind up arrogant algo-nerd snobs because you can bust it out for anything that is likely to be already sorted or nearly so and it dominates. Algo-nerd snobs rarely seem to take into account that knowledge and understanding of the input is the most crucial part. Do it in job interviews only if you've already decided you're unlikely to want to work there and be sure to be smiling and humble as you demonstrate this to their peers, noting that the pure forms of the algo, selection sort is arguably better (Knuth!) but this is unlikely to be an interesting practical concern and totally dwarfed compared to readability of the code.

minitech 3y ago
> it dominates Not compared to insertion sort, which is the actual contender here. Weirdly aggressive comment.

deleted 3y ago

[deleted]

jbandela1 3y ago

For an N^2 sorting algorithm, I think insertion sort is superior to bubble sort when you want something simple: http://warp.povusers.org/grrr/bubblesort_misconceptions.html http://warp.povusers.org/grrr/bubblesort_misconceptions.html

svachalek 3y ago
That link seems to insist on defining bubble sort without a termination condition, which is not how I think of bubble sort and I suspect is not how anyone is defining it in the cases it argues against. Also the use case in this article isn't listed.

vandyswa 3y ago

When the bucket of things to sort drifts below count ~100, bubble sort will hammer it into order in an amount of time which is, for all intents and purposes, zero. Use the smallest hammer which drives the nail...

kevin_thibedeau 3y ago
Also a good time to shelve any binary search because linear search will beat it for short sequences. The threshold varies by platform.
dekhn 3y ago
This is also known as "hardware caches and branch prediction beat smart humans almost every time"

dxbydt 3y ago

Can I have Cheeky Retorts for $100 Alex. 1. If you have a very large (say 100 million elements ) array in descending order, you can use Bubblesort to sort it in the ascending order - the worst case complexity is kn^2, and this is literaly the worst case, so its the equivalent of a sleep(t) routine for a large t ( depending on how sow your system is). 2. If you have a very small array (say n < 10), you can create toy examples where kn^2 < m*nlogn, for carefully chosen values of k, m & n. Say n = 3, k = 1, m = 7.

dahart 3y ago

> On some very particular hardwares bubblesort stills ends up better, like in this NVIDIA study, but you probably don't have that hardware. The author might have misunderstood the hardware in question and the reasons why bubble sort works well here. You probably do have applicable hardware; it’s any GPU. The bubble sort wasn’t running on ray tracing hardware, it was just CUDA code. The reason bubble sort works well is because it’s running on a SIMD machine, and it’s better when all threads in a work unit (a “warp” in CUDA parlance) all do the same thing at all times. If you try to do insertion sort on a SIMD machine, you’re very likely to approach worst-case O(N^2) performance very quickly, even when each individual thread involved would have had average-case perf on it’s own. Bubble sort is good for the parallel SIMD machine because of it’s deterministic and regular evaluation order that is the same across all threads. Of course, it’s still true that for anything larger than very small arrays of data, bubble sort complexity is unacceptable on SIMD or parallel processors. There are better parallel sorting algorithms for that.

lifthrasiir 3y ago
In the other words, you are sorting lots of equally-sized slabs at once, and you can do the same operation to each slab efficiently. Algorithms with no data-dependent control flow would be optimal in this situation, and bubblesort is one of them. But there are even better algorithms, I think shellsort with a fixed gap sequence (since the slab size is known in advance) could've been a good alternative. On the other hands, if you are sorting a single huge list, you need a parallel sorting algorithm like bitonic sort.

Syzygies 3y ago

In college in the 1970's, I took a combinatorial algorithms class with Herb Wilf. He explained that choosing a subset of k distinct elements from 1..n uniformly at random was likely k log k, because you needed to detect collisions, and "sorting" k elements was k log k. (Always check your assumptions. Sorting has an k log k lower bound if all you can do is compare elements. With integers 1..n, one can do much more.) I showed up at 5pm at his office, as he was bracing himself for the drive from Swarthmore back to Philly, wondering why he ever took this gig. I proposed a linear algorithm: Break 1..n into k bins, and only sort to detect collisions within each bin. Bins would have an average occupancy of 1, so it didn't matter what sort you used. (I found this idea later in Knuth, and was briefly disillusioned that adults didn't read everything.) I looked like George Harrison post-Beatles, I probably smelled of pot smoke, and he dismissed my idea. Then my dorm hall phone rang at 10pm, a professor of mine relaying an apology. For that and other ideas, the second edition of his book opened with thanks to me. I'm surprised now that I realized then that bubble sort actually had the least overhead, in such an application. People don't use Strassen to multiple matrices unless the matrices are really big. For sorting, "really big" is 2 or 3 elements.

hakuseki 3y ago
I guess you mean k log k, not n log n.
- Syzygies 3y ago
  yep, thanks. "n log n" is how one always says it, it becomes a local variable in its phrase. Oops.
a1369209993 3y ago
> Bins would have an average occupancy of 1, so it didn't matter what sort you used. That's not quite right, though - you only care about the average occupancy if your sorting algorithm is O(b) for b elements. If you're using a O(b^2) sort, you actually care about the root-mean-square occupancy (or in general just the average runtime, or just the total runtime since you'll multiply the average by the number of bins anyway). The k-bin approach is definitely much faster than O(k log k), but I'm fairly sure it's slightly slower than truely linear, asymptotically, since the runtime will be something like 1+0+4+1 in typical cases, where linear would have to be 1+0+2+1. Edit: on some cursory Monte Carlo testing, the sum of squares of occupancies actually seems to still converge on a constant factor (of two) times the sum of plain/linear occupancies, which I was not expecting but does make the above point rather moot. (Also, the sum of cubed occupancies seems to converge on a factor of five, which seems downright bizzare.) (Tangential edit: The factors seem to be 1 2 5 15 52±2 200±20, which might be https://oeis.org/A000110 https://oeis.org/A000110, though none of the interpretations there seem obviously related.)

glitchc 3y ago

Bubble-sort is great if you have many cores to spare but no extra memory. It parallelizes nicely and works in-place. Insertion sort is great if you don't have any cores or memory to spare. It uses one core and works in-place. Selection sort is much like insertion sort, runs in-place, single-threaded, but it will be faster if your CPU is much faster than your memory access as it uses more comparisons and fewer swaps.

doubloon 3y ago

Because in a certain company i couldnt use anything except a limited old language and there was no straightforward way to sort a list of custom types and internet searching was limited . You cannot just download your favorite open source library or whatever in a lot of environments, you are stuck with the tools you got.

JKCalhoun 3y ago

Bubblesort's big advantage is that it's the one sorting algorithm that I understand well enough to write from scratch in pinch.

whartung 3y ago

I've done this. In a production application. Why? It was the easiest sort I had memorized, I didn't have my college Data Structure 201 book handy. It did exactly what I wanted. And for my datasets, it was not impacting performance. Measurably? Probably. Noticeably from the user level? No. If it was slow, I would have changed it. I did it in BASIC. But it was never my bottle neck. We're talking 10 or less items here most of the time, my bottleneck was sucking rows from the ISAM database on our 10 user, 16Mhz 68020. I was doing best fit scheduling across a selection of resources. It was a very cool system.

jqpabc123 3y ago

Why bubble sort when a slight modification can create a still simple but much more respectable algorithm called "comb sort". https://www.delftstack.com/tutorial/algorithm/comb-sort/ https://www.delftstack.com/tutorial/algorithm/comb-sort/

jqpabc123 3y ago
Comb sort tip --- instead of dividing by 1.3 use 1.333 (repeating) instead. In practical terms using integers, this makes almost no difference *except* it can be performed using faster shift and add operations: gap = ((gap << 1) + gap) >> 2; For even more speed, I'd also recommend in-lining this to eliminate the function call. Properly implemented, respectable speed can be achieved from a really trivial implementation.

deleted 3y ago

[deleted]

globular-toast 3y ago

The game dev example is really cool. I've never encountered a situation where "more sorted" is better for performance but completely sorted doesn't really matter (or maybe I have, but didn't know it). When you read Knuth's The Art of Computer Programming he challenges you to come up with your own sorting algorithm. I feel really fortunate that I was able to do this without knowing any algorithms already. I came up with bubblesort. I think it was the intuition of thinking about it becoming "more sorted" on each pass that led me there.

thecleaner 3y ago

Bubble sort's true complexity is O(n+d) where d is the number of inversions in the array. So if an array is almost sorted better to use bubble sort.

Quimoniz 3y ago

[dead]

forgotmypw17 3y ago

I used bubble sort for sorting an HTML table, because, as others say, it is easy to write quickly. It stayed that way until I asked gpt to rewrite it for me.

cyco130 3y ago

Before I knew anything about sorting algorithms, I invented my own algorithm to sort the high score list in my little BASIC game. It was very simple: Find the highest score, swap it to the top and continue, this time starting with the second item, until done. I imagine that if I ever find myself in need of writing a sorting algorithm from memory, I'll still go with this one.

plingbang 3y ago
Sounds like Selection sort[1]. It was probably the first sorting algorithm I ever implemented. I don't know why bubble sort is usually taught first. Selection sort seems more obvious. Perhaps the implementation is slightly harder due to the need to keep track of two indexes. 1. https://en.wikipedia.org/wiki/Selection_sort https://en.wikipedia.org/wiki/Selection_sort

jfengel 3y ago

I've written a sort perhaps a handful of times in the last 40 years. Each of those was a bubble sort. I was nearly-always sorting <4 elements (and often just 1, or even 0). These were rare cases where I didn't have a sort algorithm in a library -- perhaps because I needed to pass in a comparator that wasn't easily supported in the language. So I banged out whatever was easiest to get me moving on to the actual problem. If the sort became a noticeable part of the running time, I'd deal with that when I had performance numbers. Bubble sort was easy to remember and quick to bang out. For all I know I really was writing an insertion sort; all O(n^2) sorts look pretty much the same. I haven't written any sorts at all in well over a decade, since all languages have substantial support. If I'm writing a sort, something has gone very wrong.

JohnFen 3y ago
> I was nearly-always sorting <4 elements (and often just 1, or even 0). In my opinion, a bubble sort is a solid choice for that sort of use case.
- Trufa 3y ago
  Are you being cheeky? Cause I would think insertion sort would be a more than reasonable alternative
  - JohnFen 3y ago
    No, I'm serious. With datasets that small, there's very little performance difference between the two methods, so a bubble sort isn't unreasonable at all. Depending on the circumstances, a bubble sort can be the better choice due to other considerations becoming relatively more important.
  - bastawhiz 3y ago
    In what way?
  - usefulcat 3y ago
    Especially if there’s little or no performance difference, may as well minimize code size.

aappleby 3y ago

Can confirm, have used bubble sort in a production game engine to keep transparent objects mostly sorted. You do the compare-and-swap when you're iterating over the objects to do some other render pass, so it adds almost nothing to the CPU time.

phkahler 3y ago
>> bubble sort in a production game engine to keep transparent objects mostly sorted. A single pass of bubble sort per frame is often enough to keep things in order. And if something glitches because it takes 2 passes it's just a single frame glitch!
jcalvinowens 3y ago
> so it adds almost nothing to the CPU time. If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant?
- pengaru 3y ago
  > > so it adds almost nothing to the CPU time. > If two threads go to CAS-sort at the same time, the cache coherency overhead would be apocalyptically bad. I'm assuming that's not what you meant? I think it's apparent they didn't mean the CAS atomic instruction, just the compare-and-swap operation in bubblesort. Nothing in their comment suggested this was a multi-threaded situation.
  - jcalvinowens 3y ago
    >> You do the compare-and-swap when you're iterating over the objects to do some other render pass OP is describing using CAS to bubblesort an array while it is concurrently read by another thread rendering something based on its contents? That seems kind of wild to me but I don't know why else you add the words "some other". Sometimes sorting is an optimization and isn't necessary for correctness. The idea of two threads concurrently bubblesorting the same array with CAS is hilarious and intriguing. On x86 the double-wide CAS requires double wide alignment so I guess it couldn't actually work without extra trouble...

jcalvinowens 3y ago

Bubblesort is hard to beat if you're optimizing for object code size. I'm surprised that wasn't mentioned.

lifthrasiir 3y ago
Unless you have a thousand of sorting routines it wouldn't matter much. And compilers generally produce a much larger code than actually possible, you can implement bubblesort in 16 bytes of x86-32 assembly [1] for example. [1] https://gist.github.com/jibsen/8afc36995aadb896b649 https://gist.github.com/jibsen/8afc36995aadb896b649
- jcalvinowens 3y ago
  It matters a great deal if you have 1KB of flash to fit the whole firmware in :)
  - lifthrasiir 3y ago
    Oh, if you are already writing an assembly my comment doesn't apply ;-)
acdha 3y ago
I was expecting that, too. The one person I’ve heard say they’d implemented bubble sort in the current century worked on automotive controllers where they had absurdly tight memory budgets and the data he had to sort was relatively small so they quite happily traded a few cycles for the smaller executable.
padf 3y ago
Yes. Ignorant question: if you use bubble sort but go through the array in alternating senses, could it not improve locality and speed? Array v with N elements: First pass: go from v[0] to v[N-1] comparing v[i] with v[i+i] Second pass: go from v[N-1] to v[0] comparing v[i] with v[i+i] This is so obvious that it should have a name...
- 3y ago

neverartful 3y ago

It would likely be handy during your exams in CS 101.

ErikBjare 3y ago
This blog post would make a fantastic addition to the sorting part of a CS101.