Last time, we got practice doing algorithm analysis on our user-defined dynamic array datatype. This time, we'll look at our first sorting algorithm, something called bubble sort. There's a reading about bubble sort and the next two sorting algorithms we'll look at in the next couple of lectures. The problem we're trying to solve, is that we want to sort the values in an array. One solution is to sort those values using an algorithm called bubble sort. This is not bulbasaur. I was talking about bubble sort to a class, and after a few minutes I had one of my students raise his hand and say, "Why do you keep saying bulbasaur?" So despite your background, this is not bulbasaur, this is bubble sort. I will also say that there are lots of online visualizations that show how bubble sort works. So you can watch bubble sort and action to get a better understanding of how it actually works. Let's go take a look at bubble sort. Here's the code we'll look at in this lecture. I've got the num values in my arrays that I'm sorting, sets to eight for this example. I have this flag called printed debug info that I've set to true. Throughout the code, I have the ability to print out intermediate results if I choose to do so, if this flag is set to true. If you don't want to see those intermediate results as you explore this code, just set the flag to false and you won't have to see those. Here's the function prototype for bubble sort, which we're talking about in this lecture, selection sort, which we'll talk about in the next lecture, and insertion sort, which we'll talk about in the lecture after that. I have some helper functions here. I can get a random array. I can print an array. I can print the array elements. I have a function called swap elements, that just swaps the elements that are in the first location provided, and the second location provided in this array. So that function just swaps the elements in those two locations. The main function just to demonstrate a variety of iterative sorting. So for today's lecture, we get a random array and print it out to show that it's unsorted. Then, we do a bubble sort on it, and then we print the array again. Let's go ahead and do that. As you can see, I'm outputting debug info. So at the very beginning, we can see the unsorted array. After we're done with bubble sort, you can see that the array elements are sorted in ascending order. It would be straightforward to change this to sort in descending order instead. I did just have to change one character in my code, but I'll sort them in ascending order. Let's go take a look at how bubble sort actually works. Here's that printing debug info. Here's the core of the algorithm. In this outer loop, we're going to work from right to left. The big idea is after the first iteration of this outer loop, the rightmost element in our array will be the biggest element we found. After the second iteration, the just one to the left of the rightmost element will be the second biggest element in the array. So each time we go through this outer loop, we're pushing the biggest unsorted element over to the right. How do we do that? We do that with the inner loop. So this inner loop actually starts on the left and goes up to not including k and checks to see if we should swap the elements. So let's say, we're at the very beginning. If array zero is bigger than array one, we want to swap those two so that the biggest element is now in array one. We keep doing this throughout this for loop. We stop just less than k because everything k and greater has already been sorted. Once we get there, we're done with the inner loop. So this inner loop bubbles the largest element in this range of numbers over to the right. Once this inner loop is done, then we come back here and we decrement k to move over a little bit because the rightmost part of our array that is now sorted is one larger. So we move to the left because we have a smaller amount that we need to sort. Notice by the way that this outer loop goes to k equal one not to k equals zero. Once we only have one element to sort, the 0th element of the array, we don't have to do anything because a single element is by definition, sorted. Okay, let's do the algorithm analysis of this algorithm. We know, if k starts at count minus one and goes down to one, then this outer loop executes n minus one times. Starting at n minus one and going down to one, that's n minus one times. What about the inner loop? Well, as k gets smaller, obviously, the number of times that this inner loop executes also gets smaller. So what's the worst case? The worst case is when k is equal to n minus one. So we're going to start at zero, and go up to n minus two, and that's also n minus one times. When we have nested loops, we have to multiply the complexity of the inner loop by the complexity of the outer loop to get our overall complexity. If this is n minus one, and this is n minus one, in the worst case, then when we multiply those together we have n squared minus 2n plus one. The n squared term in that equation is the dominant term. Remember, we don't have to worry about constants. There are constant time operations inside the body of the loop, and swap elements is constant time because it's just three lines of code swapping things around through a temporary variable. So if we have n squared minus 2n plus one, n squared is the dominant term. That makes bubble sort and order n-squared algorithm. Let's go take a look at a visualization of bubble sort. You can use any search engine you want, but I'll just use Google, and I'll search on bubble sort visualization. There's a YouTube video that demonstrates bubble sort. If I go to that video, the rightmost side gets cut off just a little bit. But as you can see, ticking these colors along as we go to the right is that inner loop, and each time a green bar is provided on the right, that is the end of an outer loop. So as you can see, for each inner loop, it bubbles the largest element in the unsorted part or the gray part is the unsorted part. It bubbles the largest element along. By the end of that inner loop, the largest element is smacked up against the left hand side of the sorted part of the array. So we grow the sorted part of the array from right to left. To recap, in this lecture, we learned how bubble sort works, and we learned through our algorithm analysis, that this is an order n squared algorithm. It's important to remember that algorithms have complexity, specific problems don't. So while bubble sort is an order n squared algorithm, the problem of sorting an array of values is not inherently in order n-squared problem. We evaluate algorithms and quantify their complexity. We don't quantify the complexity of problems we're solving with algorithms.
