Barack Obama - Computer Science Question

Barack Obama gets asked a computer science question by Google CEO Eric Schmidt.

Full interview: http://www.youtube.com/watch?v=m4yVlP...

• Category

  News & Politics

[engiiiiii]

people always hating on BubbleSort even though an optimized all purpose sorting algorithm uses QuickSort(large arrays) and BubbleSort(small arrays)

And since QuickSort recursively creates smaller arrays.. guess who does the actual sorting

[Maxim Ivanov]

Sorry, but the statement that BubbleSort is practically used for smaller arrays is not correct, or at least not up-to-date.

However, it is true that contemporary general-purpose sorting routines will switch the sorting technique once the array chunk being sorted becomes small enough to fit in the processor cache. Often this will be a variation of insertion sort -- but not bubble sort, ever.

Also Python's TimSort is kicking the ass of small array sorting, and is the default in Java 7, etc.

[danrayson]

I recommend using dancing african hound hogs dressed in turquoise suits to do it. But blowing bubbles is fun too :)

[VillageIdiot453]

BubbleSort is not the best sort for any possible case except already sorted list, in which there are other sorts which are equally as good. .

[Benny Mirahy]

I thought he said BUBLESAUR lol

[Daniel Pendergast]

Hahaha. The interviewer got all embarrassed.

[sailorbob74133]

Actually, 1.386 n lg n is the expected average case run time. But yeah, theoretically the worst case is n^2, but as you note you pretty much have to be intentionally trying to break quicksort to get that.

[Trent Houliston]

That's assuming a best case scenario, in a worst case scenario quick sort is O(n^2), but in general I agree with you (O(n^2) you pretty much have to be trying to break quick-sort)

Come to think of it, Timsort is pretty damn good too, that would be worth trying also

[sailorbob74133]

The range of your 32 bit integers is 0 -> 2^32-1 and the largest practical base you could use might be 2^16 giving you a run time of 10^6*log_{2^16} 2^32 + 2^16 * log_{2^16} 2^32 = 10^6*2 + 2^17 = 2131072 operations. By contrast randomized quicksort of 10^6 32 bit integers would have an expected running time of 1.386 * 10^6 which is almost twice as fast.

[DavidVonR]

SocialistSort, which sorts the tax base of the US and redistributes wealth to moochers. O(log n) algorithm.

[Jeorney]

unsort() is the fastest