Okay. Now we come to one of our most important topics. This starts getting you way more sophisticated in your use of the programming language C. What we're going to show is a sorting algorithm, a very simple sorting algorithm, it's called bubble sort. While it's perfectly fine for small arrays, it's considered quite inefficient if you're going to use it on very large arrays. Now, sorting is one of the most important functions one does under computer. Why? It is used for a lot of data. So let's take data and phone-book for a big city like New York or London or Moscow, where there might be many million of people. If those phone numbers and the people were an unsorted, then it would be excessively difficult to go through and try and find somebody's phone number. Think about it. If you had several million phone numbers unordered, it would take you something like several million looks at that pile of information to come up with the right phone number. Or heaven forbid if a person wasn't in that city, you would be hopelessly searching through every piece of information only to find that the person wasn't there. On the other hand, if you have the information sorted, then you can find that information in what we call login time. Namely if there's several million, then it might take you only 10 or 15 looks in that big phone book, in that big thick phone book to actually look somebody up because you can look towards the middle of the phone book and see whether you've past where the person's name might be or you haven't come on it yet. Then you'd look in the next quarter of the phone book and then you would get down to the right page and on the right page you'd be able to also do an efficient search of finding that phone number. So by having information sorted, you have it also readily available for searching and looking up. Sorting and searching are so important that most important computer scientist of our era wrote a book Don Knuth, this book is called sorting and searching. So it's a volume just devoted to these techniques with very detailed analysis of them. Indeed even talks a fair amount about the Bubble Sort. Let me just read you. He says, "Perhaps the most obvious way to sort by exchanges is to compare two keys, interchanging R1 and R2, if the keys are out of order and then keep doing this. Repeating it until in effect you have the information sorted." So, these methods have been exhaustively analyzed because it's so important. Let's see how to do that now that we know how to have parameters passed. So critical thing we're going to look at is swap, where the swap occurs between in effect what will be to out of order keys a and b. Notice again that we're using our pointer parameters to simulate call-by-reference so that the two actual values can be interchanged. We're going to in this program have reason to print out the array because we want to see that it's been properly sorted. We see how we have a parameter for how many elements the data that we're sorting. Then in this case when we're printing the array, we're going to print it with a title, namely the pointer to character which we're going to call s-t-r for string. Looking at the routine, we first print using a format percent s for string, the string, the title and then we go in again idiomatically that's what you got to learn, these idioms once you master them, you can do most of your coding. You can do it very, very correctly and quickly. So for I is assigned to zero. I if it's less than how many elements, auto increment i and then print each element with the tab in between it. Now let's go to the actual bubble sort. We have the unsorted data at first, potentially unsorted data, by accident it could be sorted. We want again to sort certain number of elements and we're going to need a double loop. So in the double loop, we're going to have two indexes i and j. I'm going to use a little trick because I want to show you how this works. So I'm going to use an integer which is going to be a way to have the program stop at the critical point in the loop and only go on if we enter this particular integer. So look at this double loop. For the outer loop is for i equal how many, auto increment i and then we're going to print how the array looks each time through. So for each i we're going to print array and notice our title, it's inside the bubble sort. Then I'm going to ask you to continue. After we've printed the array in order to continue, you're going to have to enter something of value for gone. You don't really care what that is, this is just a standard technique to halt the program. Now you could halt the program other ways. Frequently the system you have might have a very good debugger and you can set breakpoints in which the debugger will automatically look at the program at particular times, but this gives us control and we can see exactly what we need to see. We want to see for each step through the array how does the sorting work. Then this is what's called the inner loop for j equals how many minus one, we don't have to go the whole way. We advanced j, but we subtract j, J starts at five. Then, what this bubble sort is going to do is it's going to place the largest element in the array off to what might be called the extreme right. So each time through the ever loop, we get one more element properly sorted. Here's a sort. We see if two elements are out of order, if they are, we swap them. Okay. Let's look at how main works. We're going to do it with a simple case. You can do it with something larger. One thing I'd recommend is take this and generate a bunch of data for very large array using random numbers to have appropriate data and then see how this might work for a much larger dataset. We're going to first print the array of grades and we've done that before and then we're going to bubble it. Don't forget internally to bubble, we've put that in effect debugging statements showing how the bubble sort works and then when we're finally done, we're also going to print out the fully sorted list. Okay. So that's what we're doing. Let's see it work, execute. So, just as in that program, the Data started with it being out-of-order,78 is too large. Excuse me, a message showed up that I'm not interested in. Okay. So, I've started the program, my grades are 78,67,92,83,88. Some of those are out-of-order, then we've entered bubble sort and then inside bubble, don't forget that was printing a title. We're using PrintArray in each case and now we stop and it's saying, okay, this is what we see before we do any swapping. Now I'm going to input an integer to continue. Then, the first time through the swapping has swapped 67 and 78 and then 83 and 92. Oh, we went backwards, excuse me. Let's start that over. So, 88 got compared to 83, they got swapped, 88 got compared to paired 92, they got swapped, 83 got compared to 67, it wasn't swap, 67 got compared to 78 and they were swapped. Let's do it again. Ninety-two got compared to 88, they were swapped, 88 is compared to 83, no swapping, 83 is compared to 78 no swapping, etc. One of the inefficiencies of bubble sort is that even though we're ready in order, it doesn't know we're in order, it has to complete the n-minus-one inner loops to make sure that things were out-of-order because if the smallest element is 67 had been over there, it would have bubbled down to the first element you would have seen it occur throughout. So one of it's inefficiencies is and you could try to improve on this by seeing if you could check whether it's already sorted, you could have a flag and it could test whether any swapping occurred. If no swapping occurred during a particular routine, you could stop right after that. That would indicate that everything was in order. Then my sorted grades are indeed 67, 78, 83, 88, 92. Why don't you play around with that program and we're going to also show you some more advanced sorting techniques that are efficient. A, because it's such an important topic that you really need to understand it and B, if you want to go on and computer science or even if you just want to be informed, there's lots of fancy things and fancy programming that you learn by doing these more efficient and more sophisticated sorting routines.
