MARK GROZEN-SMITH: Hi, I'm Mark Grozen-Smith, and this is Quicksort. Just like insertion sort and bubble sort, Quicksort is an algorithm for sorting a list or an array of things. For simplicity, let's assume that those things are just integers, but know that Quicksort works for more than just numbers. Quickstart is a bit more complicated than insertion or bubble, but it's also much more efficient in most cases. Wait a second. Did he just say "most cases," not "all"? Interestingly, no. Not all cases are the same. Don't worry about this detail if you haven't seen big O notation yet, but Quicksort is an O (n squared) algorithm at worst, just like insertion or bubble sort. However, it typically acts much more like an old analog m algorithm. Why? We'll get back to that later. But for now, let's just learn how Quicksort works. 

So let's walk through Quicksorting this array of integers from smallest to largest. Here we have the integers 6, 5, 1, 3, 8, 4, 7, 9, and 2. First, we pick the final element of this array-- in this case, two-- and call that the "pivot." Next, we start to look at two things-- one, the lowest index, which I'll refer to as staying to the right of the wall, and, two, the leftmost element, which I'll call the "current element." What we're going to do is look all the other elements, other than the pivot, and put all the elements smaller than the pivot to the left of the wall and all those larger than the pivot to the right of the wall. Then, finally, we'll drop the pivot right on that wall to put it between all the numbers smaller than it and all the numbers larger. 

So let's do that. Pick up the 2, put the wall at the beginning, and call the 6 the "current element." So we want to look at our current element, the 6. And since it's larger than the 2, we leave it there to the right of the wall. Then, we move on to look at the 5 as our current element and see that this is, again, larger than the pivot, so we leave it where it is on the right side of the wall. We move on. Our current element is now 1, and-- oh. This is different now. The current element is now smaller than the pivot, so we want to put it to the left of the wall. To do this, let's just switch the current element with the lowest index sitting just to the right of the wall. Now, we move the wall up one index so the 1 is on the left side of the wall now. 

Wait. I just mixed up the elements on the right side of the wall, didn't I? Don't worry. That's fine. The only thing we care about for now is that all these elements to the right of the wall are bigger than the pivot. No actual order is assumed yet. 

Now, back to sorting. So we continue on looking at the rest of the elements. And in this case, we see that there are no other elements less than the pivot, so we leave them all on the right side of the wall. Finally, we get to the current element and see that it is the pivot. Now, that means that we have two sections of the array, the first being small on the pivot and on the left side of the wall, and the second being larger than the pivot to the right side of the wall. We want to put the pivot element between the two, and then we'll know that the pivot is in its right final sorted place. So we switch the first element on the right side of the wall with the pivot, and we know the pivot's in its right position. 

We then repeat this process for the subarrays left and right of the pivot. Since the last subarray is only one element long, we know that's already sorted because how can you be out of order if you're only one element? For the right side of the subarray, we see that the pivot is 5, and the wall is just left of the 6. And the current element also starts out as the 6. So 6 is greater than 5. We leave it where it is on the right side of the wall. Now, moving on, 3 is less than 5. So we switch it with the first element just right of the wall. Now, I moved the wall up one. Now, moving on to the 8. 8 is greater than 5, and so we leave it. The 4 is less than 5, so we switch it. And on. And on. 

Each time we repeat the process on the left and right sides of the array. we choose a pivot and do the comparisons and create another level of left and right subarrays. This recursive call will continue until we reach the end when we've divided up the overall array into just subarrays of length 1. From there, we know the array is sorted because every element has, at some point, been a pivot. In other words, for every element, all the numbers to the left are lesser values and all the numbers to the right have greater values. 

This method works very well if the value of the pivot chosen is approximately in the middle range of the list values. This would mean that, after we move elements around, there about as many elements to the left of the pivot as there are to the right. And the divide-and-conquer nature of the Quicksort algorithm is then taken full advantage of. This creates a runtime of O (n log n,) the n because we have to do n minus 1 comparisons on each generation and log n because we have to divide the list log n times. However, in the worst cases, this algorithm can actually be O (n squared.) Suppose on each generation, the pivot just so happens to be the smallest or the largest of the numbers we're sorting. This would mean breaking down the list n times and making n minus 1 comparisons every single time. Thus, o of n squared. 

How can we improve the method? One good way to improve the method is to cut down on the probability that the runtime is ever actually o of n squared. Remember this worst, worst case scenario can only happen when the pivot chosen is always the highest or lowest value in the array. To ensure this is less likely to happen, we can find the pivot by choosing multiple elements and taking the median value. 

My name is Mark Grozen-Smith, and this is CS50. 

For simplicity, let's assume that those things are just integers, but know that Quicksert-- Quicksert? Sorry. 

Here we have the integers 6, 5, 1, 3, 8, 4, 9. 

SPEAKER 1: Really? 

SPEAKER 2: Don't stop there. 

SPEAKER 1: Really?