"The bubble sort would be the wrong way to go"

February 21, 2019 9:17 PM

16 sorting algorithms, demonstrated with the help of a color circle [SLYT]
posted by slater (51 comments total)

I think I prefer this one.
Color is not a great way to convey sortable data, IMHO.
posted by Aleyn at 9:35 PM on February 21, 2019 [5 favorites]

I think the color wheel approach is at least interesting as an alternate style of presentation; it does convey the early vs. late vs. incremental grouping nature of the different algos in an interesting way at times, all else aside.

But, man, the aspect ratio! That is giving me agita.
posted by cortex at 9:49 PM on February 21, 2019 [7 favorites]

something something black magic fuckery something.

That was great.
posted by RolandOfEld at 10:00 PM on February 21, 2019

OMG the Gravity Sort was my favorite until I saw the Radix LSD In-Place Sort (Base 10)...

...was not a sentence I expected to be typing tonight, but here we are.
posted by vverse23 at 10:01 PM on February 21, 2019 [9 favorites]

I liked the ones where it looked like nothing was happening until everything happened at the same time. Like a big finale.
posted by bleep at 10:22 PM on February 21, 2019 [4 favorites]

It strikes me as obvious from watching these that some of these algos could be parallelizable -- the ones that divide the field into partitions, then work on each partition sequentially -- they could work on the partitions in parallel. Quck googling confirms that there are parallel versions of such algos.
posted by smcameron at 10:32 PM on February 21, 2019 [1 favorite]

What, no bogosort? Guess they saved that for the unlimited-length video.
posted by axiom at 10:44 PM on February 21, 2019 [1 favorite]

I just want to know how they mapped sort activity to the sound effects.
posted by GuyZero at 11:01 PM on February 21, 2019 [2 favorites]

until I saw the Radix LSD In-Place Sort (Base 10)...

.... oh, hell yeah!
posted by Silvery Fish at 11:05 PM on February 21, 2019

I am reminded of the old NBC sort.
posted by pracowity at 12:08 AM on February 22, 2019 [4 favorites]

I wish they had a brief line on each sort giving advantages/disadvantages (ie, fast if entire sort can fit into RAM, slow as hell if not, or good for database-driven sorts, or ...). But cool, none-the-less.
posted by maxwelton at 12:32 AM on February 22, 2019 [1 favorite]

You want wikipedia's "Comparison of Sorting Algorithms" table:

https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
posted by Wolfdog at 3:32 AM on February 22, 2019 [3 favorites]

I can see this as a projection in a trance club.
posted by pompomtom at 3:44 AM on February 22, 2019 [1 favorite]

I think I prefer this one.
Color is not a great way to convey sortable data, IMHO.
posted by Aleyn at 9:35 PM on February 21 [+] [!]

i)strobe warning
ii) serial animations are for noobs
look at 24 sorts in parallel.

posted by lalochezia at 4:01 AM on February 22, 2019 [2 favorites]

Holy crap, this was awesome. I'm teaching an algorithms class this semester and will be showing this to my students.
posted by SuperSquirrel at 4:02 AM on February 22, 2019

This 80s video is also important viewing.

I'm not saying I put a bubble sort into production code as a fuck-you to a certain other engineer, I'm saying they assured me there'd only ever be a handful of items on the list that they refused to otherwise explain, and I took them at their word.
posted by fleacircus at 4:33 AM on February 22, 2019 [3 favorites]

What, no bogosort?

Also missing nimzosort
posted by thelonius at 4:53 AM on February 22, 2019 [2 favorites]

Aleyn's link ended with a Bogosort, which I had never heard of. Seems like that would be even less the way to go than a Bubble sort.

This led me to wondering what kind of a sort was used in card sorters (e.g. IBM 083) and check sorters I used to see and/or work on in my younger days. Say you wanted to sort 1000 punch cards by ZIP code, and the ZIP code was in columns 45-49.
The operator would put the cards in the hopper and set the brush to column 49 and hit Start. The cards would go into stackers 0-9 (and Reject!). The operator would then pick up the cards from stacker 0, pick up the cards from stacker 1 and put them on top of the pile, and so on for all piles. Put the pile back in the hopper, set the brush to column 48 and do it again. And so on through column 45. When you stack the cards after the 5th pass, they're in order.
I couldn't figure out which kind of sort this was on my phone, but now I see it's an LSD Radix. Easy to train an operator on, and fairly fast.

I liked the color demo, and also Aleyn's link, but I'm a noob.
posted by MtDewd at 5:49 AM on February 22, 2019 [3 favorites]

what the heck was Bogo sort?
posted by rebent at 5:51 AM on February 22, 2019

The audio frequency mapping is what I enjoyed the most.
posted by phenylphenol at 5:52 AM on February 22, 2019 [1 favorite]

what the heck was Bogo sort?

Random resorting in hopes you chance upon the ordered sequence.
posted by NoxAeternum at 6:03 AM on February 22, 2019

what the heck was Bogo sort?

The function successively generates permutations of its input until it finds one that is sorted.
posted by thelonius at 6:04 AM on February 22, 2019

It's extremely efficient if you're very very lucky
posted by ook at 6:06 AM on February 22, 2019 [13 favorites]

Now I'm wondering about nimzosort. Sorting chess openings?
posted by MtDewd at 6:13 AM on February 22, 2019

well there is a Bogoindian defense, and the more common Nimzoindian
posted by thelonius at 7:03 AM on February 22, 2019

Is that last one supposed to be Timsort? I can't find reference to anything called a "Time Sort". Whatever it is, it's witchcraft!
posted by howling fantods at 7:07 AM on February 22, 2019 [1 favorite]

Also, here is the source code. For anyone who wants to fix the awful aspect ratio stretching.
posted by howling fantods at 7:08 AM on February 22, 2019

Holy crap, this was awesome. I'm teaching an algorithms class this semester and will be showing this to my students.

Not for nothing, but I think you really want this post.
posted by The Bellman at 7:17 AM on February 22, 2019 [1 favorite]

I can't find reference to anything called a "Time Sort". Whatever it is, it's witchcraft!

Inspecting the code it looks like it's just a multi-threaded insertion sort. Why not just call it that?
posted by howling fantods at 7:21 AM on February 22, 2019

I used this page in teaching sorting on a first year "computing for engineers" module this term: https://www.toptal.com/developers/sorting-algorithms - shows algorithms in parallel on different types of dataset (random, reversed, nearly sorted, few unique values). The site also gives the algorithms and some discussion of the advantages and disadvantages of each algorithm (do you want to minimise the amount of movement of data, for example?).
posted by nja at 7:25 AM on February 22, 2019 [1 favorite]

I'll stick to Hungarian dancing, thanks.
posted by DreamerFi at 7:27 AM on February 22, 2019 [3 favorites]

This led me to wondering what kind of a sort was used in card sorters (e.g. IBM 083) and check sorters I used to see and/or work on in my younger days. Say you wanted to sort 1000 punch cards by ZIP code, and the ZIP code was in columns 45-49.

Radix sorts also lend themselves well to human use, as do semantic analogies like sorting a large stack of e.g. misc. documents to be filed first into categories and then sub-categories and then by date order.

Which reminds me that I'd probably genuinely enjoy a writeup of sorting algorithms being used in the wild for physical sorting in non-CS contexts. Bureaucracy itself isn't exactly a sexy subject but the need for humans to sort and store and retrieve physical documents and other items means a billion different people have tackled subsets of these problems independently and the way that knowledge accretes and moves around from one person to the next is a quietly fascinating notion.
posted by cortex at 7:51 AM on February 22, 2019 [1 favorite]

The Angry Rainbow palette strikes again. Never, ever use a fully saturated rainbow in naive RGB colorspace like this. Use a perceptually uniform color map instead. There are many options, including ones that still look like a rainbow.
posted by Nelson at 8:32 AM on February 22, 2019 [4 favorites]

The perceptually uniform color maps look dull. I'll take an angry rainbow any day of the week.

Also: timsort FTW!
posted by grumpybear69 at 8:46 AM on February 22, 2019

There are loads on the channel here is another one. Gravity sort just looks like magic every time and the Radix LSD in place sort (base 10) is glorious.
posted by epo at 10:59 AM on February 22, 2019 [1 favorite]

> It's extremely efficient if you're very very lucky

... is this the part of the thread where we talk about quantum bogosort?
posted by Reclusive Novelist Thomas Pynchon at 1:31 PM on February 22, 2019

I'm not saying I put a bubble sort into production code as a fuck-you to a certain other engineer, I'm saying they assured me there'd only ever be a handful of items on the list that they refused to otherwise explain, and I took them at their word.

I'm saying that the only reason to code a bubble sort ever is as a fuck-you to somebody. There is no use case for which bubble sort works faster or uses less memory than linear insertion, and linear insertion requires less code.

My personal favourite is a variant of Quicksort where instead of reverting to linear insertion when the number of elements in a sublist gets small, you simply fail to sort any small sublist altogether; then you run a single pass of linear insertion over the entire list at the end. The quicksort step has partitioned the list into mutually sorted sublists, so the insertion sort pass ends up doing the same work that individually insertion-sorting the sublists would have done but with less function call and loop setup overhead and better cache utilization.
posted by flabdablet at 5:34 PM on February 22, 2019 [2 favorites]

There is no use case for which bubble sort works faster or uses less memory than linear insertion, and linear insertion requires less code.

I've probably implemented bubble sort in a couple different Zachtronics games where saving the cost of an extra register or parallel computing core was worth it just to reduce the component cost of a design to the absolute minimum regardless of the ramifications for code length and run time. But that's sufficiently pathological that it's more or less the opposite of a counter-argument.

(I guess the straight-faced defense of bubble sort is that, though: it has the conceptual strength of requiring less context and situational awareness than anything else in the game other than bogosort. You can bubble sort even if you have zero attention span and can't remember what you were doing two seconds ago or where. Dire is the situation where those constraints are in play in practice, but insofar as everything has its place that's bubble sort's.)
posted by cortex at 4:57 PM on February 24, 2019

insofar as everything has its place that's bubble sort's

...and if you reef the bubble sort out of that place and drop in a linear insertion sort instead, you end up with slightly shorter code that works better; sometimes significantly better.

The only reason - seriously, the only reason - that anybody uses bubble sort for anything is that they were taught it before being taught linear insertion. It's reasonably easy to understand how it does what it does and newbie programmers just fixate on it like little ducklings. Bubble sort is the canonical "simple" O(n²) sorting algorithm.

But it absolutely shouldn't be. Linear insertion sort is easier to understand, simpler to implement, never works worse and often works better. Teaching bubble sort ought to be a fireable offence.
posted by flabdablet at 6:32 PM on February 24, 2019

I'm saying that the only reason to code a bubble sort ever is as a fuck-you to somebody.

Oh no, they're on to me.
posted by fleacircus at 7:22 PM on February 24, 2019 [1 favorite]

I don't think they even taught bubble sort in the CS classes I took.....I remember it being mentioned, but I don't recall being assigned to implement it. That was a long time ago now, however!
posted by thelonius at 7:50 PM on February 24, 2019

I remember it being taught in my high school Pascal class but that was explicitly an introduction as a very basic exercise; and I feel like it's been taught as a kind of nightmare baseline in every course I took in college that touched on complexity theory. But never as an uninflected "here's a good way to do it!" sort of thing.

You know what these visualizations never show? A nice Tower of Hanoi sort. Let's get some exponential big O going.
posted by cortex at 8:08 PM on February 24, 2019 [1 favorite]

I have a clear memory of being taught it as an alternative to straight selection, superior in that it could be coded to recognize that no interchanges had happened during the inner pass and made to stop early on that condition.

But that optimization requires extra code. Without it, bubble sort runs in O(n²) time regardless of input data.

Linear insertion, by contrast, does not require extra code to run in nearly O(n) time for nearly sorted data, and a completely naive linear insertion sort is usually one or two lines of code shorter than a naive bubble sort.

Linear insertion is the Betamax of low-conceptual-complexity sorting algorithms. It's cheaper than VHS, smaller than VHS, has better video bandwidth than VHS, loads faster than VHS, doesn't jam and tangle like VHS, but fucking VHS is fucking everywhere and it's still all anybody talks about when they're trying to introduce people to videotape. It's maddening.
posted by flabdablet at 8:15 PM on February 24, 2019

that was explicitly an introduction as a very basic exercise

Ducklings, man. Ducklings.
posted by flabdablet at 8:17 PM on February 24, 2019

I mean in practice almost everybody is going to use a library implementation of something stronger and faster than either; I feel you on the hair-splitting for righteous hair-splitting's sake but it's also far enough outside the realm of actual practice that it's hard for me to see it as anything other than something to tell bar stories about.
posted by cortex at 8:45 PM on February 24, 2019

To put it another way, supporting new programmers is a good goal but if the roadblock to someone doing good development is that they can't recover from toxic early exposure to the slightly worse of two sorting algorithms neither of which they will basically ever use in serious practice they probably do not have a particular predisposition toward code design to begin with.
posted by cortex at 8:48 PM on February 24, 2019

(looks around at a software landscape dominated by a vast snarl of IoT kudzu not quite managing to smother the smoking ruins)

they probably do not have a particular predisposition toward code design to begin with

Well that explains that then.
posted by flabdablet at 8:52 PM on February 24, 2019 [2 favorites]

Bubble sort has the nice property that you only ever swap two elements. Insertion sort requires moving whole ranges at a time. In a low level language like C, insertion sort can seem harder to implement.

In the real world, no programmer should ever* be writing their own sort function. The system library is always going to have one they should use. Similarly programmers should never be implementing linked lists, or string types, or binary searches, or any of the other toy algorithms that are taught in intro programming classes.

(*) exception made if you are one of about 20 programmers in the world who have the right to create new languages or fundamental system libraries. Or if you're just goofing around.
posted by Nelson at 7:28 AM on February 25, 2019 [1 favorite]

Bubble sort has the nice property that you only ever swap two elements. Insertion sort requires moving whole ranges at a time.

That's not a nice property at all. In fact it's one of the reasons that linear insertion sort outperforms bubble sort while being both conceptually and operationally simpler.

Linear insertion sort does not require "moving whole ranges at a time"; it copies elements one at a time in the process of comparing them with the next item to be inserted into the sorted region. That simple copy is never slower and usually faster than the swap operation inside a bubble sort's inner loop, since a memory-to-memory swap typically needs to be synthesized from multiple copy operations anyway.

Insertion sort with binary search does require whole ranges to be moved at a time but that's not the algorithm I'm suggesting we should expunge bubble sort in favour of.
posted by flabdablet at 10:08 AM on February 25, 2019

In a low level language like C, insertion sort can seem harder to implement.

void linear_insertion_sort(long double data[], int items) {
	int i, j;
	long double item;
	for (i = 1; i < items; i++) {
		item = data[j=i];
		while (data[j-1] > item) {
			data[j] = data[j-1];
			if (--j == 0) break;
		}
		data[j] = item;
	}
}

void bubble_sort(long double data[], int items) {
	int i, j;
	long double item;
	for (i = 0; i < items; i++) {
		for (j = 0; j < items-1-i; j++) {
			item = data[j+1];
			if (data[j] > item) {
				data[j+1] = data[j];
				data[j] = item;
			}
		}
	}
}

Coded off the top of my head. Not tested. In no way guaranteed bug-free. This linear insertion sort compiles to less machine code than this bubble sort, its inner loop contains less work, and on partially sorted data that inner loop will run fewer times than bubble sort's.
posted by flabdablet at 10:32 AM on February 25, 2019

I am now even more convinced I was correct to put that bubble sort in.
posted by fleacircus at 6:43 AM on February 27, 2019 [1 favorite]