He claimed that choosing a subset of k integers at random from {1..n} should have a log in its complexity, because one needs to sort to detect duplicates. I realized that if one divided [1..n] into k bins, one could detect duplicates within each bin, for a linear algorithm. I chose bubble sort because the average occupancy was 1, so bubble sort gave the best constant.
I described this algorithm to him around 5pm, end of his office hours as he was facing horrendous traffic home. I looked like George Harrison post-Beatles, and probably smelled of pot smoke. Understandably, he didn't recognize a future mathematician.
Around 10pm the dorm hall phone rang, one of my professors relaying an apology for brushing me off. He got it, and credited me with many ideas in the next edition of his book.
Of course, I eventually found all of this and more in Knuth's books. I was disillusioned, imagining that adults read everything. Later I came to understand that this was unrealistic.
Of course my intuition would be that you can do a random shuffle and then take the first k, which is O(N). So I might be misunderstanding.
Their 1978 second edition works in exactly the memory needed to store the answer, by simulating my algorithm in a first pass but only saving the occupancy counts.
Oh, and thanks (I guess). I really didn't expect to ever be reading FORTRAN code again. One learned to program at Swarthmore that year by punching cards, crashing our IBM 1130, and bringing the printout to my supervisor shift. I'd find the square brackets and explain how you'd overwritten your array. I even helped an economics professor Frederic Pryor (the grad student in the "Bridge of Spies" cold war spy swap) this way, when I made an ill-advised visit to the computer center on a Saturday night. Apparently I could still find square brackets.
It's basically asymptotically approacting the correct (sorted) list instead of shuffling the list in weird ways until it's all magically correct in the end.
A few other algorithms would have fit the bill just as well, but bubblesort is perfectly adequate, so that's what will likely ship. More complex algorithms end up losing out due to greater initial overhead or larger ROM size.
My goal is to stop working as soon as possible; this is a 1.7 MHz CPU and it has many other tasks to perform on a given frame. It's hard to appreciate unless you sit down to actually do it, but on a processor this slow, the scanning of the list and the comparison of depth is not cheap. It's computed on the fly as we go, there isn't spare RAM to cache it, and it changes every frame anyway. All of that makes the scanning and comparisons way more expensive than the eventual swap.
Insertion would be ideal here for a freshly spawned object, since we already know it is out of position and merely need to find its destination. (The work to shift the rest of the list down isn't super expensive, thankfully.) In practice this is already a big enough visual change that the player doesn't have much time to notice a depth error before it corrects itself.
But this is a case where theory doesn't count as much as having an acceptable result. It is typical in video games, if it plays well and looks fine, who cares if it is incorrect. Here I guess that sometimes a sprite appears on top of another sprite when it should have been behind it, because of the early exit, but while playing, it turned out not to be noticeable enough to change the algorithm.
Both Insertion sort and Bubble sort are O(N^2). Both are stable sorts. Insertion sort consumes only about 10-20 bytes more flash memory than Bubble sort. It's hard to think of situations where Bubble sort would be preferred over Insertion sort.
Shell sort is vastly superior if you can afford an extra 40-100 bytes of flash memory. (It's not too much more complicated than Insertion sort, but sometimes, we don't have 100 extra bytes.) It is O(N^k), where k ≈ 1.3 to 1.5. As soon as N ⪆ 30, Shell sort will start clobbering Insertion sort. For N ≈ 1000, Shell sort is 10X faster than Insertion sort, which in turn is 6X faster than Bubble sort. Unfortunately Shell sort is not stable.
Comb sort has a similar O(N^k) runtime complexity as Shell sort. But it seems slower than Shell sort by a constant factor. Comb sort is also not stable. I cannot think of any reason to use Comb sort over Shell sort.
Quick sort is not much faster than Shell until about N ≈ 300. Above that, the O(N*log(N) of Quick sort wins over the O(N^k) of Shell sort. But Quick sort is not stable.
Merge sort is stable and runs in O(N*log(N)), but it consumes an extra O(N) of RAM, which may be impossible on a microcontroller. You may be forced back to Insertion sort for a stable sort.
You didn't mention heap sort. A simple implementation, which doesn't do any method calls just like shell sort (also next to the merge sort above) is about twice as complex than shell sort.
I think I ignored Heap sort because it uses O(N) extra RAM, which is precious on a resource-constrained microcontroller.
Bubble sort doesn't click for me easily. I think it's because the terminating condition seems uglier than Selection sort or Insertion sort. I always have a little voice in the back of my mind, "Is this outer loop guaranteed to terminate?"
I don't believe that insertion/selection sort is easier to grasp. Can you type it from memory, without looking it up? Here's bubble sort:
var swapped = true
while swapped:
swapped = false
for i in 0 .. list.len-2:
if list[i] > list[i+1]:
swap(list[i], list[i+1])
swapped = trueFor the curious, the ZX Spectrum microdrive listed files on the cartridges by order found on tape. I wanted to display it in alphabetical order like the "big" computers did.
It is your choice which career to pursue, but in my experience, absolute majority of programmers don't know algorithms and data structures outside of very shallow understanding required to pass some popular interview questions. May be you've put too high artificial barriers, which weren't necessary.
To be a professional software developer, you need to write code to solve real life tasks. These tasks mostly super-primitive in terms of algorithms. You just glue together libraries and write so-called "business-logic" in terms of incomprehensible tree of if-s which nobody truly understands. People love it and pay money for it.
I used to think alike (I'm +30 year programing) until I decide to do https://tablam.org, and making a "database" is the kind of project where all this stuff suddenly is practical and worthwhile.
The idea was that the vast majority of arrays in a large set are not searched often enough to justify the cost of sorting them and sorting is an expensive operation if you are computing on a deadline. You also don't always know which ones will be heavily searched ahead of time. Using bubblesort, only the heavily accessed arrays end up sorted but as a side-effect of search rather than having separate heuristics to decide when/what to sort.
Also, general wisdom to be mindful of data sizes and cache coherency. O(NLogN) vs. O(N^2) doesn't mean much when you're only sorting a few dozen items. Meanwhile, O(N) space can have drastic performance hitches when reallocating memory.
if you apply quicksort to 2^20 random integers, at some point you're sorting 2^17 8-integer subpartitions
and every new hire got taken to the whiteboard to learn about sort algorithm performance: bubblesort is O(n) in the best case.
and in our codebase, the data being sorted fit that best case (the data was already sorted or almost sorted).
I said sure, quicksort, mergesort or radixsort?
He just said "okay, let's skip to the next question". :)
Though in reality almost never: you almost always have a convenient built-in sort that is as quick & easy to use (likely quicker & easier), and in circumstances where the set is small enough for bubblesort to be just fine, the speed, memory use, or other properties of what-ever other sort your standard library uses aren't going to be a problem either.
As others have pointed out, sometimes it is useful for partial sorts due to the “always no less sorted than before at any point in the process (assuming no changes due to external influence)” property.
wrt:
> If you make each frame of the animation one pass of bubblesort, the particles will all move smoothly into the right positions. I couldn't find any examples in the wild,
There are hundreds of sort demos out there, both live running and on publicly hosted videos, that show the final positions by hue, getting this effect. Seems odd that they couldn't find a single one.
EDIT: actually, I can't find any of the rainbow based sort demos I was thinking of, a lot of promising links seem dead. I take back my little moan!
Worse, big-O always hides a constant factor. What's bubblesort's constant? What's quicksort's? It wouldn't surprise me if, for small enough n (2 or 3, and maybe a bit higher), bubblesort is actually faster.
Note well: I have not actually benchmarked this.
Also note well: Determine what your n is; don't assume that it's either large or small.
It was one of the many viral moments during Obama's original campaign where he seemed cool and in touch.
[1] https://github.com/thomasmueller/bau-lang/blob/main/src/test...
https://en.wikipedia.org/wiki/Shellsort
Shellsort can be regarded as an improvement over either Bubble Sort or Insertion Sort.
You can also do something like a calendar queue with bubble sort for each bin.
And while I've never hit a case I would think it would have merit with data known to be pretty close to properly sorted.
When I was playing The Farmer Was Replaced and needed to implement sorting, I just wrote a bubble sort. Worked first time.