Quick Sort
Resources
Video Script
The last sorting algorithm we’re going to look at is quicksort. Quicksort is the newest of these algorithms being first published in 1961. Quicksort is a little bit different than the other sorting algorithms, because it requires us to choose a pivot element from the list and then sort based off of that pivot elements, it’s really kind of hard to understand conceptually without seeing it in action. So let’s take a look at how we perform quicksort using our deck of cards. The last sorting algorithm we’ll look at in this class is quicksort. Quicksort is a very unique algorithm. It’s like a divide and conquer algorithm, but it has some really interesting quirks and how it works that make it work really fast with random data. So let’s take a look at how quicksort works and see if we can get it to sort our deck of cards. The first step in quicksort is to choose a pivot element. And this is actually one of the key things about quicksort is choosing a pivot element most quicksort algorithm Don’t even put any thought into it, they just pick the last element or the first element in the list and call that the pivot.
So we’re going to take our six, and we’re going to call that our pivot element. Then we simply go through all the rest of the cards and sort them into two piles. All of the cards that are less than six go on one side, and all of the cards that are greater than six, go on the other side. And you notice that I’m not changing the order at all, I’m not doing any other sorting in those groups. I’m just putting them into those groups in the order that they come. So now we have our six that was our pivot elements, we have all of the items that are less than six on one side, and we have all of the items that are greater than six on the other side. This is where the divide and conquer part comes into this algorithm. We will do the same thing for each of these two groups. We’ll choose the pivot element, which is the last card and we will sort in this case the pivot element is five and all of the rest of Have the cards are less than five. So we don’t really gain a whole lot there, we just move this down to the next group. Here, we would choose the pivot element has eight. And so we would end up sorting the seven and the nine after the eights are, my my apologies, we would end up sorting the nine to 10 after the eight, whereas the seven would go before us.
So now we can do this again, we’ll pick this item as our pivot. And we will notice that very quickly, the ace goes before the three and the four. And notice I’m not changing anything else, I’m just arranging them in the order that they come. So now we’ve had six as a pivot, we’ve had five as a pivot to as a pivot, and eight as a pivot. So now we need to look at the other groups. We have a single group here, so that would become the pivot and gets locked in place. We have a group of two here where that becomes the pivot and gets locked into place. We have a group of one here where that becomes a pivot, and we have a group of two here where that becomes the pivot And now we can lock the others in place. And tada, it’s already sorted. That seemed to go very, very quickly.
So let’s shuffle this up and try again and see if quicksort really is just that fast. So let’s walk through quicksort. Again very quickly and see if it works just like we think. We’ll start by selecting our pivot element as three. And then we will put all of the elements that are greater than three on one side. And again, I’m not changing the order of them, I’m just grabbing them as they come. And then we’ll put all of the elements that are less than three on the other side. So now we’ve divided and we’ve set it up like that, in this item, we have two, so the two will become the pivot, the ace doesn’t move and an ace becomes the pivot. We’re already done with that side. Here are the four will become the pivot, and we know that everything is greater than the four after we look at It so the four will get locked in over here. The six will become the next pivot, and we will shuffle things around such that the six is in the correct spot. The five is a single so it’s going to get locked in place, we’ll choose the seven is the pivot, everything is greater than seven, it will get locked in place, which is the eight is the pivot, it will get locked in place, then we will choose the 10 is the pivot and finally the nine will get locked.
So again quicksort works very quickly. But let’s take a look at an example where quicksort may not work as well. And then in the later video, we’ll analyze why that doesn’t work. Alright, so now we have one more list of cards that we’re going to start with quicksort. And obviously, looking at this, you realize immediately that this is sorted, but the computer would know that without checking, so we’re going to do our quicksort algorithm and see what happens. So we’ll pick the 10 as the first pivot, and we’ll put everything less than 10 on one side and everything greater than 10 on the other side, and we noticed that everything left is less than 10. So nothing moves. So now we’ll do the nine. And now we’ll have to do the same thing by looking at every single card and making sure that it’s less than nine, and it is, and then we’ll do eight, and we’ll make sure that everything is less than eight. And it is we’ll do seven, we’ll make sure everything is less than seven.
And as we go through this process, you’ll notice that this feels an awful lot like so, like Insertion Sort. We’re comparing each card to each other card and trying to figure out where it fits. And so as it turns out, quicksort has this really weird Worst case where if the data is already sorted quicksort is actually very inefficient. And it runs pretty much the same as Insertion Sort with a few extra steps. So in the next video, we’ll do some analysis of mergesort and look at its complexity. And then we’ll also look at the complexity of quicksort and see why it has this really bad worst case.