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 this YouTube video 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 bubble sort would be the wrong way to go". My family knows that I enjoy pointing out pop references to CS, 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 Big-Oh notation and O(n²) versus (nlogn), and why the latter is better. We talked about how we can characterize an algorithm by its running time as proportional to n² or nlogn for some factor k, and the role that k plays in complicating our comparisons. I mentioned that O(n²) and a big k 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 Bubble Sort: An Archaeological Algorithmic Analysis (PDF), available from his web site.) 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, mergesort. 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. -----