Search This Blog

23 January 2007

Rise, Dame RheLynn, Guesser of QuickSort!

Sir Charles Antony Richard (Tony) Hoare & wife Jill at Buckingham Palace to receive his Knighthood "for services to education and Computing Science."

Hi RheLynn! Hi Mark!

Glad ya like Vleeptron!

You now have 75 days in which to solve the Easter Bunny Faberge Egg Distribution Problem!

http://vleeptronz.blogspot.com/2006/12/pizzaq-help-easter-bunny-find-shortest.html

That should be enough time -- but I advise you and all other ppl who want to take a whack at it not to tarry or dawdle.

RheLynn -- you really ARE a Geeky Girl Extraordinaire!

By virtue of Our powers as Sovereign of the Planets Vleeptron, Yobbo, Hoon, Mollyringwald, and the Dwingeloo-2 Galaxy, Rise, Dame RheLynn of Earth!

On the nose! It's Sir Tony Hoare's Amazing QuickSort!

I'd describe it as The Fastest Known Way To Sort Things ... but it's NOT! QuickSort has this screwy little caveat loophole:

If the initial Set of Elements to be sorted is ALMOST in proper order to begin with, then QuickSort is the SLOWEST sorting method of all! Slower than even Cocktail or the even more primitive Bubble!

But when the initial Set is very jumbled up and disordered, yes indeedy, Sir Tony's QuickSort is the Fastest Known Way (at least on Earth) to Sort a buncha disordered Things!

Wish I'd been at Buckingham Palace to watch Her Majesty say, "Rise, Sir Tony, Inventor of the Amazing QuickSort Algorithm!"

Who says Math(s) will never get you anywhere?

btw we saw Helen Mirren's movie "The Queen" Sunday night. You guys can catch it at the Regal Brooklyn Center 20 in Minneapolis. It's Really Good! (Only one car chase.)

Tony Blair is wheezing to the end of his Prime Ministry with a nasty ugly tabloid scandal in which his Labour Party is accused of selling Knighthoods for political cash contributions. But I very seriously doubt that Sir Tony Hoare's name will be dragged through the mud.

Had you read Knuth's volume "Sorting and Searching"? Had you bumped into QuickSort before? Where? Dja ever have to write a QuickSort proggie? Or did you get the answer from a Cold Start just from gazing mesmerized at the Wiggle.gif ?

So anyway, now everybody (including Mark and the cats) on Vleeptron must address you as Madame or as Dame RheLynn! Also you get some pizza if you're ever hereabouts. Ya like anchovies?

Meanwhile, for your Alter Ego KnitOwl, here's a little treat:

http://vleeptronz.blogspot.com/2006/10/phobos-et-deimos-les-satellites-de.html


2 comments:

RheLynn said...

To be honest, I had no idea about the different sorting methods available - although I have some small amount of programming experience. However - by 'staring mesmerized' at the wiggly gif it was apparent that 1. this was a procedure that operated according to a specific set of rules - algorithm? 2. it was sorting some sort of data

My first thought was 'what kind of data would this be - that we would need to sort it thus?' - and I went off searching for census statistics and algorithms that work with that. That lead to all sorts of interesting things - matroid theory and Big O Notation and lots of little nooks and crannies to go look at later -- but when I finally hit the 'sorting algorithm' page at Wikipedia, it was a quick hop to bubble sort, and that didn't look quite right things were lining up from one end to the other instead of jumping about...- so on to cocktail sort and finally Quicksort where YES - that is the right sequence (not to mention the same image... *nudge*) and Hoare was indeed a Knighted SIR so double-bang, that was it ;o)

Haven't read much Knuth - although I have the opportunity to as there is a set wandering around here. I've really just begun to let my mind 'back out of the box' it has been hiding in for a few years -- and having a lot of fun seeing where it wants to go now ;o)

So, is double pepperoni extra-cheese deep-dish Vleeptron pizza available? I'm just really happy to have something click!

Vleeptron Dude said...

well if you have Knuth at hand, his explanation of QuickSort -- algorithm and the Deep Math behind all this Sorting Stuph -- is your best possible intro to Sir Tony's astonishing QuickSort.

Don't forget to check out my subsequent post which illustrates VleepSort, the pathetic, primitive, low-rent, trailer park sorting algorithm we use on Planet Vleeptron.

It's faster than QuickSort if all the elements except one are initially in proper low-to-high left-to-right order -- so there! Eat my shorts, Sir Tony!

Were you surprised that Natural Logarithms describe the efficiency of Sorting Algorithms? I was.

Sir T was knighted for "contributions to education and computing science," but as far as I'm concerned, he got it entirely for inventing QuickSort, and could have spent the rest of his life resting on that Laurel.

Just imagine how $$$$$$$ has been saved over the past 40 years in CPU time alone sorting and ordering vast government and corporate databases. Think of the Sears & Roebuck Accounts Receivable database or the US Social Security database -- we're talking about savings of days or weeks of CPU time.

Yes, 'twas Wikipedia's (free copyright) Wiggle Gif what got filched by the Vleeptron Ministry of Pizza, thanks for reminding me to give that lovely Wiggle Gif its credit where (no) credit is due! Here's a profile of RolandH, who created the Wiggle Gif:

http://en.wikipedia.org/wiki/User:RolandH

btw the new souped-up free version of MS_Paint can do Wiggle Gifs, it's called Paint.Net i think, it was a class project for programming students at Washington State University, mentored by Microsoft, and has now had a gazillion free downloads. Wikipedia has a wiki about it. (I can't use it because it doesn't support the vile, useless and now un-supported WindowsME.)