Transcript from the "Quick Sort Overview" Lesson

[00:00:00]

>> Bianca Gandolfo: So we're gonna check out our next divide and conquer sorting algorithm. It's called quick sort, it's one of the more famous sorting algorithms out there. You guys ready, ready to jump in? So just a reminder, when we say divide and conquer we have aA few basic steps.

[00:00:20] The first one, we have to always find our base case. 2, we're gonna break our problem down during each loop. Conquer, do the work. And 3, combine. So with quick sort, or with merge sort, all of the work is happening on the combination piece. With quick sort we actually skip the combination part because we're doing an in place operation.

[00:00:51] And all of the action happens on the partition, which is the splitting.

>> Bianca Gandolfo: Cool, so in essence, what we're doing with a quick sort is we're choosing a pivot point and with everything, usually it's either the first one or the last one, the last element in array, we choose that.

[00:01:16] Here, let me have my picture for you. We choose our pivot point. So here we're choosing 4, which is the end of our array. And we're going to swap out all of the elements that are larger to the right. And all of them that are less are gonna be to the left.

[00:01:36] And so what happens when we loop through here and we swap them, 4 is gonna be in its final place where it's supposed to be, right? Does that make sense? So as we move all of the higher ones. So 7 would go there, then 5, 9, and 8, and then 5, right?

[00:02:00] The very last one. Then 4 is gonna be here, and that's its final position in the array. You see that? Even though everything else is out of order, the pivot point is now the partition, which is its final point. So that's sorted. Wherever it winds up is the sorted part of the array.

[00:02:21] In the bigger array, right? We're not sorted arrays of size one. We're talking about it has found its final place in the big array. And all this is taking place in place. Unlike merge sort where we are creating new arrays and then merging them together. Does that make sense?

[00:02:42] Cool, so once we find the final place for our 4, we are then gonna recursively partition the right side and the left side. So just like we did with the 4, we're going to choose maybe on the left side the last one, and then we're gonna swap it until it has its final place.

[00:03:07] Same thing on the right, we have quite a few more here, so a little few more steps. So 7, we get 7 into its final place, we split it, we split it again to the partition. And then it's all in its final place, cuz again, we're all doing this in place.

[00:03:26] So we don't have to merge it or combine it, that's why there's no combination step.

>> Bianca Gandolfo: Does that make sense?

>> Bianca Gandolfo: Brains exploding a little bit? Quick sort's kind of a crazy one.