Bubble sort is an algorithm with a very bad reputation. Robert Sedgwick, in Algorithms in C, notes that bubble sort is “an elementary sorting method” and “it does much more work” than it needs to. Donald Knuth is much more harsh when he states “the bubble sort seems to have nothing to recommend it, except a catchy name…” in the Art of Computer Programming.
Like a an actor valued only for his good looks bubble sort is an algorithm an enterprising coder should probably not admire.
Why is bubble sort so bad? Why does decent computer society advise young and impressionable software engineers avoid it? Why am I devoting a whole blog post to the ugliest sorting algorithms?
TIL: You can learn more from the flawed than you can from the flawless.
I’m not going to tell you why bubble sort is so bad. But before you google it why not try to figure out on your own?
The truth is that modern programmers don’t usually implement any standard sorting routines on the job-even the good ones! Generally there exists a collection class or library that is well written and well tested. If you have a mentor she will tell you not to bother with your own interpretations of the standard body of algorithms. That problem as been solved.
However, I think you’re missing out. Knowing now to implement well known algorithms can help you understand when to use them, what their strengths and weaknesses are, and how to talk about them. Like in a job interview.
Bubble sort is a great place to start. In order to understand why it’s so bad you have to understand big O notation, how algorithms are classified, and how the ordering of input data impacts the performance of an algorithm.
It’s my opinion that bubble sort is only the most terribad sorting method in the platonic world of absolute randomly unordered data. Bubble sort is actually very appropriate for error detection or for data that is already mostly sorted. You know, the kind of data that you are likely to run into in real life.
// Bubble sort
func bubble(inputList:[Int]) -> [Int] {
var l = inputList
var t = 0
var swapped = false
repeat {
swapped = false
for var i = 1; i < l.count; i++ {
if l[i-1] > l[i] {
t = l[i-1]
l[i-1] = l[i]
l[i] = t
swapped = true
}
}
} while swapped
return l
}
var results: [Int]
var randomList = [5,2,7,8,1,9,0,3,4,6]
results = bubble(randomList)
var orderedList = [0,1,2,3,4,5,6,7,8,9]
results = bubble(orderedList)
var semiorderList = [0,1,2,3,4,9,6,8,5,7]
results = bubble(semiorderList)