The second example that I want to go through is shown here. We're going to create a VBA sub that's going to sort vector values in ascending order using something known as the bubble sort algorithm. So, I've got 5, 7, 3, 9, 1, and we want to sort that in ascending order. Now, the bubble sort is probably the worst sorting algorithm. It's the slowest. But nevertheless, it's a good algorithm to teach this type of stuff to you guys. All right. The way the bubble sort works, is we start with our initial column of values and the way the bubble sort works, is we do pairwise comparisons. We first compare item one with item two. If that's not in ascending order, then we make a swap. But since those are already in ascending order there's nothing that we have to do. Next, we move on to items two and three. Since those are not in ascending order, we have to make a swap. So we're going to switch the order of those two, and we end up with three and seven for items two and three. Next, we compare three with four. So, since seven and nine are already in ascending order there's nothing that we have to do. And finally, we compare items four and five. And since those are not in ascending order we will have to swap those. And what we end up with are one and nine for items four and five. Now, if you noticed, if you have n items, here we had n equals five, we had to do that swap n minus one times. So we had to make that comparison four times total. We've done one pass of the bubble sort. We've done those pairwise comparisons and minus one of those. However, you notice that obviously this is not in ascending order. So we have to do this iteration again. So we would compare in the second round of this process, we would now compare five to three. We make that swap. We then compare five with seven. And there's nothing we need to do there. Next, we compare seven and one and we would have to swap those because those are not in ascending order. And finally, we compare seven with nine and those already in ascending order. So, what you notice is, after each pass, now, I've done this pass twice. We are sort of bubbling up the lighter elements. You noticed that one started at the very bottom, and after one round of this process it was in the fourth position. After two rounds it's in the third position and so on. We have to do this twice more. And it turns out that if you have n items, in each pass, you have to do n-1 comparisons and I've already talked about that. But you also need to do n-1 passes. And in the end then we would get 1, 3, 5, 7, 9. So let me draw a flowchart for this entire process. We're going to start, we're going to count the number of rows that will tell us the number of elements. The first four loop is going to be sort of the outer loop which is the total number of passes that we have to do. And we recall from the previous analysis that we have to do n-1 rounds of this. So, I'm going to go from two to n. And that will be my n-1 passes. Now, inside that outer for loop, we're going to have an inner for loop, which means that during each pass we have to make n-1 pairwise comparisons. And since we do that n-1 times, I'm also starting with another index, j. J is going to go from two to n. And for each of the pairwise comparisons then we have to check to see if A(j-1) is greater than A(j). So, that means if the jth element in the vector is less than the (j-1) element, then we're going to have to swap. So we're going to do a swapping algorithm. And if this condition is false, that already means that those two are in ascending order and we don't need to do anything. Then we reconvene and we bump j up by 1. Once we've done all the pairwise comparisons then, we bump up to the outer for loop and we do the second pass, or the next pass where each pass does n-1 pairwise comparisons. And we keep going, going until we're done and we end. Now, this swap algorithm we're going to make as it's own subroutine, and the flow chart looks like this. Where we are defining a new variable Temp, that's going to equal to one of the values. And then the other value A(j) will be equal to A(j-1) and A(j-1) is Temp. So, it's sort of like a mailbox where if you want to swap one and two here, you can't just say this cell is equal to that and that cell is equal this. What you first have to do is say, we're going to put the one in some temporary variable. Then I'm going to say that this is equal to the second one. So that be a two. Then we're going to say, this is equal to what's in our Temp. So that's how we can do this swap algorithm. So, our entire flowchart is shown here. And let's go ahead and code this in VBA. Going to call this bubble sort. We have to Dim n, which is the number of items in our column vector i, and j, all as integers. We count the number of rows and assign that to the variable n. Now, we're going to set up our outer loop which is the index i. We're going from for i equals one to n. Now, inside the outer loop with the index i, we're going to have this inner loop which generates over the index j. Now, inside the inner for loop, we have a one-way if then, if Selection.Cells j-1. You notice that in my flowchart A(j-1) is just referring to Selection.Cells j-1 just to make things easier in the flowchart. So that's greater than A(j) then, we're going to do something. If this condition is true, we're going to run a swap algorithm. I could put this in its own subroutine, but I'm just going to put it into the code right here. We also need to Dim Temp as a double. And then we plug in the code for the swap algorithm into the one way if then. And then we're done. There's nothing we need to do. There's no other output to this subroutine. It's just acting on that selection and making manipulations to the data. Let's go ahead and run this. I'm going to step through this using F8. We count the number of rows of my selection. We get five. Then we're entering into the first pass. And in each pass, we're going to do n-1 pairwise comparisons. Looks like we have an error here, so let's debug this. I know exactly what I did wrong. For each of these we need to go two to n. Some you may have caught that. So, let's go ahead and reset this. Run through this again. All right. So, now we're doing a pairwise comparison between five and seven. That's already in the right order. So we just move along. Now, we're comparing seven with three. Because seven is greater than three, we have to swap. So, we store the three in a temporary value and we kind of do the swap that way. And you see that we've swapped three and seven. So now we do a comparison between seven and nine. That's already in the right order. And finally, we do a comparison between the nine and one, we put that in the correct order. And we keep going. You notice that that one as I just hold this F8 down, that one is just sort of bubbling its way to the top. So, all the lighter elements sort of bubble their way to the top. And that's why it's called the bubble sort. So, hopefully, this gives you another example of how we can implement these types of things in advanced algorithms. In this case, we've got a for loop embedded within another for loop.
