Hacker News Reader

Comment by saghm | Hacker News Reader

If we're willing optimize for aesthetic over ability to help understand, I'll nominate demonstration via Hungarian Folk Dance[1] as a candidate for the best medium to depict sorting algorithms, which I first saw during a lecture years ago when the professor pulled up on of the videos to show us in class

[1]: quicksort is shown here, but the channel has plenty of others https://youtu.be/3San3uKKHgg

View on HN

Such a internet classic. I have never once searched for it, yet seen it dozens of times.

So what is the best algorithm when you have a bunch of people and want them sorted in order of, say, birthday.

Tell the people with any CS experience they're not allowed to talk, and then let everyone just go for it.

The first part is crucial, because if the group has two or more people exposed to CS courses, they'll invariably start negotiating the optimal algorithm to use while trying to recall the actual implementation, thus preventing any actual sorting from taking place.

Presumably some kind of Radix Sort: you ask the crowd to split up and group together by month, let the people in each group self-sort and organize however they'd like, and then just concatenate the sorted queues together

Or to make “concatenate” more physical, divide an area into 12, one for each month in order, then in each area, people sort themselves.

This is similar to the best design we have for the fastest way to board a plane: take people in a dozen or so “chunks”, then have each chunk stand in a sorting area atop a diagram of the airplane, one chunk at a time. A group enters the area and sorts themselves by standing near the place on the diagram where their seat is, then boards the plane in line. As each chunk boards, they’re already in the right order so that nobody is blocking anyone while trying to stuff their overhead luggage.

I’m not sure if any company has implemented the system but there was some test a company did of a bunch of boarding techniques and it was the most efficient.

It should be obvious that's most efficient if you can get everyone to be there 30 mins early. Which they can't, mostly due to connecting flights and really not having what to do at the gate for 30 mins.

Real objects are basically always either psuedo-radix because you have a good idea of the distribution and aren't limited to pairwise comparison, or psuedo-selection because the objects are big and heavy so you don't want to move them more than necessary. For people self-sorting psuedo-radix is definitely the way because they can self-parallelize easily.

I say psuedo because real objects have lots of properties both on the rearranging and comparison sides that are not quite the same as digital ones. For eg it's faster to compare numbers that have a large difference in magnitude, and it's easier to swap objects that are physically close to each other. So following a CS algorithm to the letter is usually slower than adapting a little.

Tell them to make sure the person in front of them has a birthday before theirs. If not, keep jumping back the line until they do.

Practical CS theory isn’t really relevant here because it is N-parallel for N people.

You could use a sorting network too

That is, in practice, what I just described.

I was disappointed that men in the video were sorted by their numbers, but not their height! ;)

Reply on news.ycombinator.com