Skip

Gnitros Tuo Gnitros
July 28, 2012 6:17 AM   Subscribe

Sorting Out Sorting

An exploration of sorting techniques by Professor Ronald Baecker.
posted by Ad hominem (22 comments total) 32 users marked this as a favorite

 
Bonus for quicksort fans: Hungarian Folk Dance Quicksort.
posted by Ad hominem at 6:28 AM on July 28, 2012 [5 favorites]


Awesome. I just watched about half, up to quicksort, and re-learned stuff I'd forgotten years ago. I'm going to finish it up later when I have time.

Also, I love the music, which sounds like it may all be computer generated, from back when that was pretty hard. And the "sort is finished" motif is funny.
posted by dubitable at 6:57 AM on July 28, 2012


The shaky recording gave me a headache about 5 minutes in and I had to turn it off. It's too bad, because sorting algorithms are a pretty fun subject.
posted by KGMoney at 6:59 AM on July 28, 2012


I think all films should end with a narrator asking, "Instead, why not see the whole film again?" Followed by a high-speed recapitulation of the entire film.
posted by etc. at 7:00 AM on July 28, 2012 [4 favorites]


I love the music too, it sort of reminds me of Mr Rogers. Come to think of it, the whole thing reminds me of Mr Rogers. Watching the lines move and hearing the bleeps, bloops and the narrator's super-humanly even tone is so soothing.
posted by Ad hominem at 7:06 AM on July 28, 2012 [1 favorite]


I'm disappointed the credits were cut off, or not included. I was curious to see if any of the creators are still around as faculty at the UofT so I could reference this subtlety and see if they noticed.
posted by Algebra at 7:15 AM on July 28, 2012


Oh, whoops. Dr. Baecker. Of course!
posted by Algebra at 7:18 AM on July 28, 2012


Recursion, my old enemy, we meet again.
posted by tommasz at 7:22 AM on July 28, 2012 [1 favorite]


Bonus for quicksort fans: Hungarian Folk Dance Quicksort yt
Nearly seven minutes. Jeez, it's a good thing those guys weren't using bubblesort.
posted by Flunkie at 7:33 AM on July 28, 2012




A long buildup to a great punchline: "If you're getting bored, let that be a lesson about n2 sorts."
posted by Lokheed at 8:13 AM on July 28, 2012 [5 favorites]


The credits are in the middle of the end of the movie, around the 27 minute mark. For example, James Montgomery composed the music. Searching on his name led me to this, which predates the movie by a year, and goes into some detail about how the music is generated. He is also a founding member of the Canadian Electronic Ensemble, which has been playing since 1971. Video.
posted by zabuni at 8:24 AM on July 28, 2012 [4 favorites]


Hmm. I'm a programmer and I think sorting is just kind of a pain in the butt.
posted by Foosnark at 8:27 AM on July 28, 2012


which has been playing since 1971. Video . that is great, that guy really is in a band and really does play laptop.
posted by Ad hominem at 8:31 AM on July 28, 2012


Sorta put me to sleep.
posted by weapons-grade pandemonium at 9:48 AM on July 28, 2012


Sorta put me to sleep.
Sleep Sort
posted by Flunkie at 9:52 AM on July 28, 2012


Hungarian Folk Dance Quicksort

Of course, eventually we saw the commercialization of traditional folk sorting in the 50s, 60s and 70s; as technology and distribution models improved, "pop sorting" became big, big business, with sorting studio executives devoting large budgets and massive capital pressure to the pursuit of slickly polished and sanitized algorithms and "best case" performances.

And new ground was broken, certainly, in optimality and sorting tech, but with it came a kind of flattening of the scene, a loss of the sort of vital randomness and enthusiasm of the traditional "swap dance" experience that the industry leveraged to such considerable profitability.

Which, then: the late seventies, the height of "Big O" decadence, and the rise in defiance to all that of a new kind of anti-refinement, as the sorting scene refound itself in the rough, improvised, bullheaded and algorithm-poor rumble that was the Punk Sort revolution. Loud and fast and routinely out of order, young sorters mocked the stagnant commercial scene as acts like Bubble Trouble, X to the N, and The Bogos stumbled around on tiny stages in no-name venues, staging with no clear apparent end goal a fractured, transformed return, equal parts obnoxious and glorious, to the stripped-bare roots of folk sorting.
posted by cortex at 10:33 AM on July 28, 2012 [9 favorites]


Even my 7 year old figure this one out: Visualizing Quicksort
posted by DU at 12:06 PM on July 28, 2012 [1 favorite]


Well one thing I learned was the O in "Big O" means Order. I'm not sure if I never learned that or just forgot it once the final was over.
posted by Ad hominem at 6:19 PM on July 28, 2012


sortvis
posted by bleary at 10:22 PM on July 28, 2012


I came here to complain about how those Hungarians didn't dance themselves to order in parallel.
posted by Anything at 4:33 AM on July 29, 2012


The film didn't touch on my favorite Quicksort variant, where instead of switching to a bubble sort once the sublists being partitioned get small enough to make that optimal, you simply exit; having finished the entire Quicksort process, you then run a linear insertion sort over the entire list at the end. This saves a whole lot of loop control and function call overhead, and because the Quicksort pass has left the list mostly sorted, the linear insertion sort will never actually perform more operations than the multitude of little bubble sorts would have done.
posted by flabdablet at 8:45 PM on July 29, 2012 [1 favorite]


« Older "Move along. Move along."   |   Da-da-da-DUN-DAH-wub-wub-woo Newer »


This thread has been archived and is closed to new comments



Post