Algorithms: Bubble Sort

Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview. Today I want to talk about bubble sort. Bubble sort
is a very naive sorting algorithm, not one we probably want to use in the real
world. But what it does is just walk through the array and every time we see
elements that are out of order it just swaps that. And so if we do this enough
times then we’ll eventually get our array to be sorted. So we walk through the
array swapping all the out-of-order elements and then we walk through it, and so
it’s a little more sorted than it was, and then we walked through it again, swapping all the elements that are out of order, and
eventually the elements kind of bubble around to where they should actually be.
Unfortunately bubble sort is pretty slow. We could have to do as many as O of n passes
through the array and each pass takes O of n time. So that’ll give us a runtime
of n squared but we don’t need any extra memory to run this algorithm. So now
let’s look at the implementation of it. To implement bubble sort what we want to
do is keep walking through the array as long as its unsorted and swap elements. So
let’s first just write out, we’re going to walk through as long as
the array is not sorted. So I’m gonna have a boolean is sorted, and I’m gonna
start this off as false presuming potentially that it’s not sort initially. Now I
need to walk through the array. So this is one sweep of the array and walk
through, this from up through length minus 1. Now I’m going to talk in a second about
why I have this written instead of just array.length. And then if the
elements are out of order if array of I is bigger than the next element, then
swap those values, swap array, and plus one, ok. So the reason why I have
this array minus 1 here is because array of i is actually going look at the next
element so if I had this be array just go up to array dot length, then I’m going
to get an out of bounds error on the very last element. So I need to make sure that this is array dot length minus 1. And so if I did have to swap the
elements then I know that my array is not sorted, so I’m gonna set that to be
false again. And then I’ll exit, or I’ll enter the for loop when is sorted is true.
So basically I assume it’s sorted here and then I walk through the array. If anything is out of order, swap those
elements and then I indicate hey it’s still not sorted quite yet. And then when I exit this while loop
my whole array will be sorted. So there’s one other little optimization we can
make. One thing we can notice is that at the end of the first pass the very
last element in the array will actually be the correct maximum value in the
array. So it will be the very last element, will be in place. And so in the
next sweep I don’t actually need to walk through the entire array, I can stop just
before the last element. So what I can do here is I can say, I can say you know
last unsorted, and I can set this initially equal to array dot length
minus 1. And then after I enter them in my for loop, I just shrink the last unsorted size.
Because once, as I said, once I get to the very end of the array at that first
sweep, the last element will be in place. On the second sweep, the second-to-last
element will be in place, on the third sweep, the third to last element. So I can
basically shrink that unsorted portion each time because these sweeps are
actually pushing the last max element along in the array. So that’s how we
implement bubble sort. Again, it’s a pretty inefficient algorithm and you’d
rarely ever implement this although maybe in particular circumstances it could be useful. For example, you have an array that’s
sorted and one element in the array gets incremented, you might then, 1 walkthrough a
bubble sort could then sort the array efficiently. But generally speaking you
probably wouldn’t use this algorithm a whole lot. But now that you’ve seen the
basics of bubble sort, why don’t you try out either implementing from scratch or
applying a new sorting algorithm into a different problem. Good luck.

Leave a Reply

Your email address will not be published. Required fields are marked *