Re:Bubblesort, rocksort, and cocktail-shaker sort
by KMag on Wednesday December 16, 2020 @05:08AM
(#25440859)
Quantum Bogosort[0] sorts in O(N) time, but the destroy_universe() step is only safe if the Many Worlds interpretation of Quantum Mechanics is correct.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by steerablesafe on Wednesday December 16, 2020 @10:03AM
(#25443349)
If you add bit errors to the picture then the check after shuffle spuriously passing has a significant, potentially much higher probability than a bit error introducing new, previously impossible random shuffling and producing a sorted sequence. So in a significant portion (maybe most) of the non-destroyed universes quantum bogosort returns an unsorted sequence due to bit errors.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by YokoZar on Wednesday December 16, 2020 @06:54AM
(#25441538)
If you're using a cloud host that doesn't charge you anything for instances with a very low runtime, you can implement quantum bogosort for free - just have every unsorted instance self-destruct promptly.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by bluGill on Wednesday December 16, 2020 @08:32AM
(#25442268)
You can trivially parallelize this algorithm to be O(1): for each permutation you create universes to check all finite lengths of the list in parallel and destroy the universes that check either less elements than are in the list or that run off the end of the list.
I'm not sure if this can extend to infinite size lists. Sorting infinite lists in finite time makes my head hurt.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by ironmagma on Wednesday December 16, 2020 @09:19AM
(#25442732)
Computationally, this (ab)uses the scheduler to do your sorting for you. So really the performance becomes whatever your scheduler’s performance is, probably heapsort time (O(n log n)).
Re:Bubblesort, rocksort, and cocktail-shaker sort
by avocad on Wednesday December 16, 2020 @04:39AM
(#25440641)
That was a great article! The last paragraph, however:
"By the way, Knuth is interested in these algorithms mainly for the interesting mathematical problems (...) not because they’re in any way efficient algorithms! "
Made me wonder, these kind of algorithms, where there is a lot of comparing and swapping of adjacent records might be more efficient on a tape-based architecture. Or an architecture with a lot of prefetch caching.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by vanderZwan on Wednesday December 16, 2020 @08:14AM
(#25442095)
Insertion sort is known to be the fastest option for small ranges, which is why it often is the sorting option hybrid sorts switch to for that case (like when the partitions in quicksort or merge sort are small enough).
AFAIK, this is mainly because even though it is expected O(n²), it has a really tiny overhead because insertion sort is incredibly simple, so for small enough n it wins. However, being very cache-friendly is also part of it (it's a linear search over the array).
IIRC some people found similar results for bubble sort.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by bestboy on Wednesday December 16, 2020 @05:18AM
(#25440925)
just want to quickly share an IMHO interesting sorting algorithm visualization video: https://youtu.be/kPRA0W1kECg
"Visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes.
Sorts random shuffles of integers, with both speed and the number of items adapted to each algorithm's complexity.
The algorithms are: selection sort, insertion sort, quick sort, merge sort, heap sort, radix sort (LSD), radix sort (MSD), std::sort (intro sort), std::stable_sort (adaptive merge sort), shell sort, bubble sort, cocktail shaker sort, gnome sort, bitonic sort and bogo sort (30 seconds of it)."
Re:Bubblesort, rocksort, and cocktail-shaker sort
by ogogmad on Wednesday December 16, 2020 @05:05AM
(#25440825)
Bubblesort appears to be inferior to insertion sort in every single way. It's more complicated, it's slower in every situation. I don't know why you'd ever use it. What's the point of it?
Re:Bubblesort, rocksort, and cocktail-shaker sort
by LordDragonfang on Wednesday December 16, 2020 @05:54AM
(#25441154)
The "point" is that it is one of the three intuitive sorting algorithms that someone unfamiliar with algorithmic complexity will write when asked to write a computer sorting algorithm (and happened to be the first sort I wrote when tasked with just that in college long ago). This makes it a useful thing to discuss because it's so clearly inferior to the other two despite being just as intuitive.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by ernesth on Wednesday December 16, 2020 @10:03AM
(#25443353)
My anecdotal experience as a teacher is that when tasked with implementing sort, students go for selection sort.
However when asked to do it in real life on a bundle of graded exam sheets, if I ask them to sort alphabetically, they will do insertion sort, if I demand to sort by grade, they will bubble sort. The number of sheets may also change their method.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by virgilp on Wednesday December 16, 2020 @07:49AM
(#25441900)
If you need an additional datapoint, bubble sort is also the first sorting algorithm I came up with. I find it super intuitive - the only slightly-less intuitive part maybe is that you need to do the outer loop at most N times (in my implementation, the outer loop was `while(changed)` where `changed` would be set to `true` if any swap was performed in the inner loop ).
Re:Bubblesort, rocksort, and cocktail-shaker sort
by bonoboTP on Wednesday December 16, 2020 @09:21AM
(#25442754)
Even though I know the algorithm, I still find that I need to think a nontrivial amount to see why it will not miss anything. I mean, sure, you are strictly improving the "sortedness" by a discrete amount in each pass and crucually, you don't destroy any progress you made before (not totally trivial), and there's only a finite amount of "sortedness" to attain, so it will converge to the sorted state. But how exactly and, as you say, after how many iterations, is not so clear. In more complex algorithms, you may get stuck in a local optimum with such a greedy approach though.
But contrast that with insertion sort. I have a sorted pile that grows after each insertion. I find it trivially clear that it works and when I will be done.
It's also something that people will intuitively do in the physical world to sort paper documents I think: just grow a pile of sorted documents by adding the next one in the right place.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by iainmerrick on Wednesday December 16, 2020 @07:36AM
(#25441815)
I think this is a bit dangerous because people take away the “I understand and can implement bubble sort” part, but forget the “it’s very inefficient, don’t use it” part. So people end up using bubble sort in production! It doesn’t help that it has such a cute and catchy name.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by kadoban on Wednesday December 16, 2020 @08:06AM
(#25442011)
Probably no real fix for that. In algorithms if you only taught the best algo for a particular problem, you'd lose everyone on the first day, and miss out on a lot of analysis/teaching opportunities. Remember that algorithms study isn't just about speed, it's actually about _correctness_ first.
Besides, it's pretty rare for someone to need to write their own sorting algorithm anyway, in production. And if they do but they're so addled they do it from memory and randomly pick bubblesort, hey at least it's fairly easy to be correct.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by smcl on Wednesday December 16, 2020 @08:08AM
(#25442033)
I wonder how many people actually write a sort algorithm in production code anymore. I haven't personally seen this, but I guess that doesn't really mean it doesn't exist.
What I have seen is pretty horrific abuse of Linq (i.e. repeated lookup of `things.Where(t => t.Id == query.Id).First()` as if it was a dictionary) which might stem from the same root cause - not thinking about what your code is actually doing and why it might be inefficient. It doesn't help that there's that there's those oft-quoted Bentley's Rules of Optimization which gives people an excuse to not care :-/
Re:Bubblesort, rocksort, and cocktail-shaker sort
by dragonwriter on Wednesday December 16, 2020 @10:31AM
(#25443740)
Huh, like when I learned this (back when I was in elementary school and the class was taught using unstructured BASIC, so the more natural lesson with most things more modern of “rely on your standard library for sorting, unless you have a really good cause to roll your own and then do some research” wasn't an option) the takeaway was “look up the implementation of a better algorithm if you are sorting nontrivial data”. (Plus, “its worth thinking about how much work your code is going to take to do what it needs to do”, as it was also my first introduction to algorithmic complexity.)
I'm trying to grasp the pedagogical failure that would result in people taking the lesson “implementing bubble sort is a reasonable thing to ever do for non-toy problems”.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by ogogmad on Tuesday December 22, 2020 @11:24AM
(#25507889)
Maybe it's the things you learn along the way, such as:
- Recursion and induction (mergesort, quicksort)
- Lower bounds on running time (O(n log n))
- Data structures (heaps in the context of heapsort, binary search trees in the context of treesort, tries in the context of radix sort, etc.)
- Difference between worst case and average case (quicksort)
- The role of the hidden coefficient in O notation (insertion sort is fast for small n even though its running time is O(n^2))
Re:Bubblesort, rocksort, and cocktail-shaker sort
by taneq on Wednesday December 16, 2020 @07:08AM
(#25441632)
It's good when there are a lot of elements off by a short distance in a mostly sorted list. The go-to use case that I've seen is depth sorting for 3D rendering on really low end hardware. Polygons usually don't move much in the Z-order each frame, so you run a few passes of bubblesort per frame for a good-enough linear-time sort.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by NortySpock on Wednesday December 16, 2020 @09:25AM
(#25442807)
Also, two passes of cocktail-shaker sort (back and forth bubble sort) would guarantee that the top and bottom z-order would be correct, which would probably be good enough to keep really obviously bad z-ordering at bay.
Like you say, when it's already partially sorted and you're just having to maintain a slowly-updated list, a single partial-sort pass per frame could be quite enough to maintain a good-enough ordering of a list.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by jan_Inkepa on Wednesday December 16, 2020 @06:49AM
(#25441510)
The differences between bubblesort and insertion sort are quite subtle and learning that it an of itself can be instructive IMO in terms of teaching rigour.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by fefe23 on Wednesday December 16, 2020 @04:47AM
(#25440706)
I feel that if you have to go to Stackoverflow after reading Knuth, maybe you didn't actually read the Knuth? Just skimmed it?<p>Not trying to piss on the OP here, but the idea with the Knuth books is that you spend time with them. Not just reading the table of contents and then going to Stackoverflow.<p>In fact, the reason for having books by authorities in the field like Knuth is so you become less dependent on places like Stackoverflow that replace factual validation by popularity validation. If you really did read Knuth you should be able to produce content on Stackoverflow instead of consuming it.
Re:Bubblesort, rocksort, and cocktail-shaker sort
by xg15 on Wednesday December 16, 2020 @06:11AM
(#25441265)
OP being in a book club - and then even writing a blog post about their takeaways - suggest to me that they did read it carefully.
No book is perfect and everything has a different level of knowledge that they have to integrate the new information from the book with. It seems reasonable to me to go to Stackoverflow to clear up questions, especially if you have such a well-known topic.
> If you really did read Knuth you should be able to produce content on Stackoverflow instead of consuming it.
Nope. Reading is just the first step. Then you have to find out whether or not you actually understood things correctly by discussing what you read and/or getting your hands dirty. After you've gained some experience, then you can start answering questions from others.
[0] https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort
I'm not sure if this can extend to infinite size lists. Sorting infinite lists in finite time makes my head hurt.
for x in "$@"; do (sleep $x; echo $x) &; done
"By the way, Knuth is interested in these algorithms mainly for the interesting mathematical problems (...) not because they’re in any way efficient algorithms! "
Made me wonder, these kind of algorithms, where there is a lot of comparing and swapping of adjacent records might be more efficient on a tape-based architecture. Or an architecture with a lot of prefetch caching.
AFAIK, this is mainly because even though it is expected O(n²), it has a really tiny overhead because insertion sort is incredibly simple, so for small enough n it wins. However, being very cache-friendly is also part of it (it's a linear search over the array).
IIRC some people found similar results for bubble sort.
"Visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes. Sorts random shuffles of integers, with both speed and the number of items adapted to each algorithm's complexity. The algorithms are: selection sort, insertion sort, quick sort, merge sort, heap sort, radix sort (LSD), radix sort (MSD), std::sort (intro sort), std::stable_sort (adaptive merge sort), shell sort, bubble sort, cocktail shaker sort, gnome sort, bitonic sort and bogo sort (30 seconds of it)."
I think the whole "swap neighbors and scan many times" thing isn't something a novice would come up with.
However when asked to do it in real life on a bundle of graded exam sheets, if I ask them to sort alphabetically, they will do insertion sort, if I demand to sort by grade, they will bubble sort. The number of sheets may also change their method.
But contrast that with insertion sort. I have a sorted pile that grows after each insertion. I find it trivially clear that it works and when I will be done.
It's also something that people will intuitively do in the physical world to sort paper documents I think: just grow a pile of sorted documents by adding the next one in the right place.
> [Bubble sort] happened to be the first sort I wrote when tasked with just that in college long ago
Besides, it's pretty rare for someone to need to write their own sorting algorithm anyway, in production. And if they do but they're so addled they do it from memory and randomly pick bubblesort, hey at least it's fairly easy to be correct.
What I have seen is pretty horrific abuse of Linq (i.e. repeated lookup of `things.Where(t => t.Id == query.Id).First()` as if it was a dictionary) which might stem from the same root cause - not thinking about what your code is actually doing and why it might be inefficient. It doesn't help that there's that there's those oft-quoted Bentley's Rules of Optimization which gives people an excuse to not care :-/
I'm trying to grasp the pedagogical failure that would result in people taking the lesson “implementing bubble sort is a reasonable thing to ever do for non-toy problems”.
(Semi-serious question, as you're quite right that hardly anyone ever needs to write a sort routine by hand these days.)
Like you say, when it's already partially sorted and you're just having to maintain a slowly-updated list, a single partial-sort pass per frame could be quite enough to maintain a good-enough ordering of a list.
I swear all the people recommending bubble sort for whatever reason are doing so out of ignorance.
No book is perfect and everything has a different level of knowledge that they have to integrate the new information from the book with. It seems reasonable to me to go to Stackoverflow to clear up questions, especially if you have such a well-known topic.
> If you really did read Knuth you should be able to produce content on Stackoverflow instead of consuming it.
Nope. Reading is just the first step. Then you have to find out whether or not you actually understood things correctly by discussing what you read and/or getting your hands dirty. After you've gained some experience, then you can start answering questions from others.