1 00:00:00,360 --> 00:00:03,720 ‫So now we're going to write our code for QuickSort. 2 00:00:04,050 --> 00:00:06,480 ‫So I'm going to bring up an array like this. 3 00:00:06,480 --> 00:00:12,480 ‫And the first thing we do when we run quicksort is we run pivot on the array. 4 00:00:12,660 --> 00:00:18,060 ‫So remember with Pivot, we have a pivot point which will be that first item. 5 00:00:18,210 --> 00:00:22,940 ‫And when we get done running pivot, that item will be sorted. 6 00:00:22,950 --> 00:00:28,980 ‫All the items that are less than will be on the left and everything greater than will be on the right. 7 00:00:29,220 --> 00:00:33,870 ‫And then Pivot will also return the index of this item. 8 00:00:34,170 --> 00:00:40,200 ‫But with QuickSort, we're also going to run pivot on this range on the left. 9 00:00:40,440 --> 00:00:43,650 ‫And then we'll run it on this range on the right. 10 00:00:43,920 --> 00:00:49,170 ‫And we'll keep doing it on a smaller and smaller range until the array is sorted. 11 00:00:49,500 --> 00:00:53,820 ‫So I'm going to put the array back the way it was, and I'll shrink this down. 12 00:00:53,820 --> 00:00:56,640 ‫So we have room for our code. 13 00:00:57,060 --> 00:01:01,890 ‫So we'll pass this an array and the left index and the right index. 14 00:01:02,100 --> 00:01:08,280 ‫So when we first call quicksort, the left index will be the first item and the right index will be 15 00:01:08,280 --> 00:01:10,410 ‫the last item in the array. 16 00:01:10,860 --> 00:01:17,910 ‫So on the right, I'm going to bring up a call stack and add this instance of quicksort to the call 17 00:01:17,910 --> 00:01:18,600 ‫stack. 18 00:01:18,840 --> 00:01:24,690 ‫And in this case, left index is zero and the right index is six. 19 00:01:25,260 --> 00:01:32,850 ‫So the next thing we're going to do is we're going to run pivot and we're going to pass pivot these 20 00:01:32,850 --> 00:01:33,560 ‫values. 21 00:01:33,570 --> 00:01:36,660 ‫It's the very thing that we passed to quicksort. 22 00:01:36,930 --> 00:01:40,650 ‫So now we have an instance of pivot on the call stack. 23 00:01:41,010 --> 00:01:44,880 ‫And since we're calling a different function here, I made it a different color. 24 00:01:44,880 --> 00:01:50,580 ‫But notice that left and right is the same as quicksort below it. 25 00:01:50,940 --> 00:01:57,300 ‫Whenever we call pivot, it will be on the same range that we used in the instance of quicksort. 26 00:01:57,630 --> 00:02:02,640 ‫And when we run Pivot, it's going to make our array look like this. 27 00:02:03,000 --> 00:02:09,510 ‫But the other thing Pivot does is it returns this index and we're going to store it in this variable 28 00:02:09,510 --> 00:02:12,000 ‫that we called pivot index. 29 00:02:12,390 --> 00:02:16,710 ‫And this variable exists in this instance of quicksort. 30 00:02:16,710 --> 00:02:19,090 ‫So I'm going to put that three there. 31 00:02:19,110 --> 00:02:25,170 ‫And once that is done, pivot is done running and it gets popped from the call stack. 32 00:02:25,440 --> 00:02:29,340 ‫So now this instance of QuickSort is at the top of the call stack. 33 00:02:29,340 --> 00:02:32,010 ‫So it is the instance that is running. 34 00:02:32,520 --> 00:02:35,220 ‫So now what it's going to do is call quicksort. 35 00:02:35,220 --> 00:02:43,830 ‫This is the first recursive function call, but the range for left index and right index is different. 36 00:02:44,100 --> 00:02:52,740 ‫So this left index is this down here in this instance of quicksort, which is zero and pivot index minus 37 00:02:52,740 --> 00:02:56,100 ‫one is three minus one, which is two. 38 00:02:56,490 --> 00:03:01,020 ‫So left index is zero and right index is two. 39 00:03:01,380 --> 00:03:05,100 ‫So I'm going to bracket this range on the array. 40 00:03:05,400 --> 00:03:07,530 ‫It is that first three items. 41 00:03:08,010 --> 00:03:12,360 ‫So now this is the active instance of quicksort. 42 00:03:12,750 --> 00:03:21,660 ‫So now we're going to call pivot with these variables and that adds pivot to the call stack once again. 43 00:03:21,660 --> 00:03:27,900 ‫Notice that left and right for pivot is the same as the instance of quicksort that called it. 44 00:03:28,200 --> 00:03:36,120 ‫So when we run pivot, that too is the pivot point and then we end up with it looking like this. 45 00:03:36,450 --> 00:03:43,710 ‫And the next thing pivot does is it returns the index of this item, which is the index of one. 46 00:03:44,040 --> 00:03:48,570 ‫Now that instance of pivot is done running and it gets popped from the call stack. 47 00:03:48,780 --> 00:03:54,240 ‫So this instance of QuickSort is now the active instance on the call stack. 48 00:03:54,570 --> 00:04:00,030 ‫It ran this line of code and then it moves to this line of code. 49 00:04:00,240 --> 00:04:06,630 ‫The left index is zero and then pivot index minus one is also zero. 50 00:04:06,630 --> 00:04:14,760 ‫So we add this to the call stack and this is our base case because left and right index are both this 51 00:04:14,760 --> 00:04:16,440 ‫item down here. 52 00:04:16,710 --> 00:04:21,750 ‫So now I'm going to bring in this if statement above these other two lines of code. 53 00:04:21,960 --> 00:04:27,330 ‫So we'll say if left index is greater than or equal to right index. 54 00:04:27,330 --> 00:04:31,320 ‫And in this case, left and right index are both equal. 55 00:04:31,320 --> 00:04:33,810 ‫So this conditional will be true. 56 00:04:33,990 --> 00:04:39,090 ‫We're just going to run return, which removes this from the call stack. 57 00:04:39,390 --> 00:04:44,250 ‫And once that pops from the call stack, we know the item at the index of zero is sorted. 58 00:04:44,250 --> 00:04:46,800 ‫So I will color that in green. 59 00:04:47,130 --> 00:04:52,140 ‫And now once again, this becomes the active instance on the call stack. 60 00:04:52,410 --> 00:04:59,010 ‫So that instance has already run this line of code and this line of code which runs quicksort on the 61 00:04:59,010 --> 00:04:59,460 ‫left. 62 00:05:00,000 --> 00:05:05,640 ‫Now we need to run quicksort on the right and we'll do it with this line of code. 63 00:05:05,880 --> 00:05:09,180 ‫And this is the final line of code and the function. 64 00:05:09,420 --> 00:05:12,600 ‫So we'll run this on pivot index plus one. 65 00:05:12,600 --> 00:05:14,430 ‫So pivot index is one. 66 00:05:14,430 --> 00:05:17,160 ‫So pivot index plus one is going to be two. 67 00:05:17,220 --> 00:05:22,650 ‫And then right index, you can see here that right index is also two. 68 00:05:22,980 --> 00:05:25,290 ‫So we'll add this to the call stack. 69 00:05:25,320 --> 00:05:28,620 ‫This becomes the active instance on the call stack in. 70 00:05:28,620 --> 00:05:31,680 ‫The first thing it does is run this if statement. 71 00:05:31,890 --> 00:05:37,410 ‫And because left index is equal to right index, we're going to return, which immediately pops this 72 00:05:37,410 --> 00:05:43,680 ‫from the call stack and now we know the item at the index of two is sorted, so I'll color that in green. 73 00:05:44,070 --> 00:05:49,230 ‫So now once again, this is the active instance of quicksort on the call stack. 74 00:05:49,350 --> 00:05:54,180 ‫It has run all three of these lines of code, which means it is done running. 75 00:05:54,450 --> 00:05:57,090 ‫So this gets popped from the call stack. 76 00:05:57,090 --> 00:06:01,710 ‫So now this is the active instance of quicksort on the call stack. 77 00:06:01,980 --> 00:06:05,820 ‫This instance of QuickSort has run these two lines. 78 00:06:05,820 --> 00:06:08,580 ‫Now it needs to move to this line. 79 00:06:08,700 --> 00:06:11,070 ‫So pivot index plus one. 80 00:06:11,070 --> 00:06:15,450 ‫Pivot index is three, pivot index plus one is four. 81 00:06:15,450 --> 00:06:20,190 ‫And then right index, you can see here that the right index is six. 82 00:06:20,460 --> 00:06:25,680 ‫So we're calling an instance of quicksort where left is four and right is six. 83 00:06:25,950 --> 00:06:31,740 ‫First, we'll check to see if left index is greater than or equal to right index, which is not the 84 00:06:31,740 --> 00:06:32,640 ‫case here. 85 00:06:32,940 --> 00:06:36,630 ‫Then we move down to this line where we run pivot. 86 00:06:36,840 --> 00:06:40,350 ‫So that adds an instance of pivot to the call stack. 87 00:06:40,470 --> 00:06:46,110 ‫Once again, left and right is the same as the instance of quicksort below it. 88 00:06:46,290 --> 00:06:49,170 ‫So I'm going to bracket the range on the array. 89 00:06:49,380 --> 00:06:53,250 ‫The item at our pivot index is going to be that number six there. 90 00:06:53,250 --> 00:07:03,330 ‫When we run Pivot, it ends up looking like this and then we return this index to this instance of quicksort. 91 00:07:03,660 --> 00:07:07,650 ‫And once pivot does that, it gets popped from the call stack. 92 00:07:07,980 --> 00:07:11,790 ‫So now this instance of QuickSort is the top of the call stack. 93 00:07:12,450 --> 00:07:14,490 ‫It has run this line of code. 94 00:07:14,490 --> 00:07:20,250 ‫Now it moves to this line of code, which creates an instance of quicksort where both the left and right 95 00:07:20,250 --> 00:07:22,380 ‫indexes are equal to four. 96 00:07:22,410 --> 00:07:29,070 ‫In this instance of quicksort, the first thing we'll do is this if statement and since the left index 97 00:07:29,070 --> 00:07:33,810 ‫and right index are equal, this will be immediately popped from the call stack. 98 00:07:34,020 --> 00:07:38,850 ‫And when that gets popped, we know that that item at the index of four is sorted. 99 00:07:38,850 --> 00:07:40,740 ‫I'll color that in green. 100 00:07:41,010 --> 00:07:45,120 ‫And now once again, this instance of quicksort is what is running. 101 00:07:45,120 --> 00:07:47,760 ‫It has run these two lines of code. 102 00:07:47,760 --> 00:07:54,090 ‫Now it moves to this line of code, which creates an instance of quicksort where left and right index 103 00:07:54,090 --> 00:07:55,290 ‫are equal to six. 104 00:07:55,290 --> 00:08:02,130 ‫And because those are equal, we're just going to run return and that gets popped from the call stack. 105 00:08:02,400 --> 00:08:05,790 ‫And when that happens, we know that item at the index of six is sorted. 106 00:08:05,790 --> 00:08:10,920 ‫So I'll color that in green and this becomes the active instance of quicksort. 107 00:08:10,920 --> 00:08:17,220 ‫Again, it has already run all three of these lines of code, which means this instance of quicksort 108 00:08:17,220 --> 00:08:19,320 ‫will be popped from the call stack. 109 00:08:19,560 --> 00:08:22,170 ‫Now this becomes the active instance. 110 00:08:22,440 --> 00:08:29,340 ‫This has run all three of these lines of code and now it will be popped from the call stack and now 111 00:08:29,340 --> 00:08:33,840 ‫QuickSort is done running and we have a sorted array. 112 00:08:34,200 --> 00:08:39,990 ‫So we'll look at this code in a moment in VS code and when we do we'll start out with an array that 113 00:08:39,990 --> 00:08:44,580 ‫looks like this and we'll run quicksort on it and sort it. 114 00:08:45,000 --> 00:08:48,120 ‫So now let's flip over and take a look at this. 115 00:08:48,720 --> 00:08:54,330 ‫So there is our pivot function that we created in the last video and this is quicksort that we just 116 00:08:54,330 --> 00:08:56,370 ‫created and this video. 117 00:08:56,700 --> 00:08:58,290 ‫So now I'll scroll up. 118 00:09:00,410 --> 00:09:04,550 ‫And in our main function, this creates the array that will be sorting. 119 00:09:04,910 --> 00:09:08,060 ‫With this line, we calculate the size of the array. 120 00:09:08,270 --> 00:09:11,660 ‫And with this line, we'll run quicksort on the array. 121 00:09:11,870 --> 00:09:14,780 ‫And with this for loop, we'll print that out. 122 00:09:15,170 --> 00:09:22,250 ‫So now I'll run this and you can see that we have a sorted array one through seven. 123 00:09:22,870 --> 00:09:26,710 ‫And that is our function for quicksort.