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.