6 ms·
Bubblesort, rocksort, and cocktail-shaker sort
- avocad 6y agoThat 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.
- vanderZwan 6y agoInsertion 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.
- steerablesafe 6y agoIt's both cache-friendly and its branches are easy to predict.
- fefe23 6y agoI 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.
- xg15 6y agoOP 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.
- ogogmad 6y agoBubblesort 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?
- LordDragonfang 6y agoThe "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.
- bonoboTP 6y agoInsertion sort seems more intuitive. Just take the next item and file it at its correct position. I think the whole "swap neighbors and scan many times" thing isn't something a novice would come up with.
- quietbritishjim 6y agoThe refutation of that is in the comment you're replying to: > [Bubble sort] happened to be the first sort I wrote when tasked with just that in college long ago
- virgilp 6y agoIf 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 ).
- bonoboTP 6y agoEven 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.
- KMag 6y agoQuantum 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. [0] https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort https://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort
- steerablesafe 6y agoAlso you you need "real" (in the quantum sense) random generator for the shuffling. If you use a PRNG then you risk destroying all the universes.
- taneq 6y agoYou could always just use a pseudorandom number generator and rely on bit errors to generate the different potential sort orders. ;)
- steerablesafe 6y agoIf 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.
- taneq 6y agoRepeat the check an arbitrary number of times then? We have infinite universes, remember. :)
- YokoZar 6y agoIf 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.
- bestboy 6y agojust want to quickly share an IMHO interesting sorting algorithm visualization video: https://youtu.be/kPRA0W1kECg 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)."
- jedisct1 6y agoThe sleep sort only requires n operations. for x in "$@"; do (sleep $x; echo $x) &; done
- bluGill 6y agoAlthough if your computer is slow compared to the size of the list this will not work due to race conditions. Still cleaver.
- ironmagma 6y agoComputationally, 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)).
- xiaodai 6y agoRadix sort ftw