TITLE: An Odd Dinner Conversation
AUTHOR: Eugene Wallingford
DATE: March 06, 2008  8:07 PM
DESC: 
-----
BODY:
Last night, at dinner with my family, I casually mentioned
<A HREF="http://www.youtube.com/watch?v=k4RRi_ntQc8">
   this YouTube video</A>
in which Barack Obama answers a question from a Google
interviewer about how to sort a million 32-bit integers.
Obama gets a good laugh when he says that "the
<A HREF="http://en.wikipedia.org/wiki/Bubble_sort">
   bubble sort</A>
would be the wrong way to go".  My family knows that I
enjoy pointing out
<A HREF="http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2008-02.html#e2008-02-20T14_55_18.htm">
   pop references to CS</A>, so I figured they'd take
this one in stride and move.

But they didn't.  Instead, they asked questions.  What is
"bubble sort"?  Why do they call it that?  As I described
the idea, they followed with more questions and ideas of
their own.  I told them that bubble sort was the first
sorting algorithm I ever learned, programming in BASIC as
a junior in high school.  My wife mentioned something like
the selection sort, so I told them a bit about selection
sort and insertion sort, and how they are considered "better"
than bubble sort.

Why? they asked.  That led us to
<A HREF="http://en.wikipedia.org/wiki/Big_oh">
   Big-Oh notation</A>
and O(<I>n</I>&sup2;) versus (<I>n</I>log<I>n</I>), and
why the latter is better.  We talked about how we can
characterize an algorithm by its running time as proportional
to <I>n</I>&sup2; or <I>n</I>log<I>n</I> for some factor
<I>k</I>, and the role that <I>k</I> plays in complicating
our comparisons.  I mentioned that O(<I>n</I>&sup2;) and
a big <I>k</I> are part of the reason that bubble sort is
considered bad, and that's what made the answer in the
video correct -- and also why I am pretty sure that Obama
did not understand any of the reasoning behind his answer,
which is what made his deadpan confidence worth a chuckle.

(If you would like to learn more about bubble sort and have
a chuckle of your own, read Owen Astrachan's
<A HREF="http://www.cs.duke.edu/~ola/papers/bubble.pdf">
   Bubble Sort: An Archaeological Algorithmic Analysis</A>
(PDF), available from
<A HREF="http://www.cs.duke.edu/~ola/papers.html">
   his web site</A>.)

As the conversation wound down, we talked about how we
ourselves sort things, and I got to mention my favorite
sorting algorithm for day-to-day tasks,
<A HREF="http://en.wikipedia.org/wiki/Merge_sort">
   mergesort</A>.

I suspect that my younger daughter enjoyed this conversation
mostly for hearing daddy the computer scientist answer
questions, but my wife and freshman daughter seemed to have
grokked some of what we talked about.  Honest -- this wasn't
just me prattling on unprovoked.  It was fun, yet strange.
Maybe conversations like this one can help my daughters have
a sense of the many kinds of things that computer scientists
think about.  Even if it was just bubble sort.
-----