1 00:00:00,550 --> 00:00:02,930 - [Instructor] Hi, in the previous video 2 00:00:02,930 --> 00:00:04,790 we introduced Quicksort 3 00:00:04,790 --> 00:00:08,890 and in this video, we're going to implement Quicksort in C++ 4 00:00:08,890 --> 00:00:10,420 actually we're going to implement 5 00:00:10,420 --> 00:00:14,000 a couple of different versions of Quicksort here. 6 00:00:14,000 --> 00:00:16,670 And the first one that we're going to implement 7 00:00:16,670 --> 00:00:19,370 we'll follow very closely the pseudocode 8 00:00:19,370 --> 00:00:22,120 that was presented in the previous video. 9 00:00:22,120 --> 00:00:23,713 So let's get started. 10 00:00:24,720 --> 00:00:27,380 I'm gonna create a file, 11 00:00:27,380 --> 00:00:29,167 I'm gonna call this Quicksort1 12 00:00:31,770 --> 00:00:34,233 because we're gonna do another one later. 13 00:00:35,450 --> 00:00:38,670 And I'm gonna borrow this snippet of code 14 00:00:38,670 --> 00:00:42,230 that we've been using for printing vectors. 15 00:00:42,230 --> 00:00:45,230 And that also includes a vector and iostream 16 00:00:45,230 --> 00:00:46,380 which we're gonna need. 17 00:00:47,310 --> 00:00:50,550 And if you'll recall from the pseudocode 18 00:00:50,550 --> 00:00:53,870 that was presented in the previous video, 19 00:00:53,870 --> 00:00:57,930 we have two functions that we're gonna look at. 20 00:00:57,930 --> 00:00:59,710 One is the partition function 21 00:00:59,710 --> 00:01:03,550 and the other is the recursive quicksort function. 22 00:01:03,550 --> 00:01:05,900 I'm also gonna introduce something new today 23 00:01:05,900 --> 00:01:07,883 which is called function overloading. 24 00:01:08,957 --> 00:01:13,160 And I'll call that out when we get to the appropriate point 25 00:01:13,160 --> 00:01:17,290 but it helps make our code in main a little cleaner. 26 00:01:17,290 --> 00:01:20,830 And when we start comparing in our projects 27 00:01:20,830 --> 00:01:23,790 a lot of different sorting algorithms, it may come in handy, 28 00:01:23,790 --> 00:01:26,310 so that's why I'm gonna introduce that here today. 29 00:01:26,310 --> 00:01:28,780 So let's copy this, 30 00:01:28,780 --> 00:01:32,350 to get started, let's copy this template and code 31 00:01:32,350 --> 00:01:37,240 and we're going to have a function that returns an int 32 00:01:37,240 --> 00:01:39,243 that's going to be called partition, 33 00:01:41,420 --> 00:01:46,420 and it's going to take a standard vector of comparables 34 00:01:49,860 --> 00:01:52,263 and we'll call that V. 35 00:01:53,630 --> 00:01:58,630 And then we also need the start and the end indices 36 00:01:58,870 --> 00:02:02,593 since we're working with subdivisions of our vector. 37 00:02:05,716 --> 00:02:06,716 So int start 38 00:02:11,775 --> 00:02:12,608 and an end 39 00:02:14,167 --> 00:02:16,567 and then the body of this function will go here. 40 00:02:19,130 --> 00:02:23,050 Then we're also gonna have a void function 41 00:02:24,590 --> 00:02:26,003 called quicksort, 42 00:02:28,280 --> 00:02:31,143 that is gonna have exactly the same signature. 43 00:02:33,120 --> 00:02:35,550 And I'm just gonna copy and paste that. 44 00:02:35,550 --> 00:02:38,373 And let's create, 45 00:02:39,900 --> 00:02:41,900 oh, I'm sorry didn't mean to paste that. 46 00:02:43,040 --> 00:02:46,963 Let's create another, 47 00:02:48,660 --> 00:02:53,240 and this is where the function overloading this coming in. 48 00:02:53,240 --> 00:02:54,503 Void quicksort, 49 00:02:57,400 --> 00:02:59,660 and this one is just gonna take 50 00:03:02,130 --> 00:03:04,943 this bit here, the vector. 51 00:03:07,570 --> 00:03:10,310 And this is okay in C++ 52 00:03:10,310 --> 00:03:14,120 to have two functions with the same name, 53 00:03:14,120 --> 00:03:15,900 and the compiler understands 54 00:03:15,900 --> 00:03:18,890 that they have two different signatures, 55 00:03:18,890 --> 00:03:23,190 and we'll recognize when we write a function call 56 00:03:23,190 --> 00:03:26,150 to quicksort and we only provide V 57 00:03:26,150 --> 00:03:29,130 it will know to call this version of Quicksort. 58 00:03:29,130 --> 00:03:33,900 And if we call quicksort with these three parameters 59 00:03:33,900 --> 00:03:36,970 it will know to call this version of Quicksort. 60 00:03:36,970 --> 00:03:40,610 And that's how simple a function overloading is. 61 00:03:40,610 --> 00:03:43,470 So we have two functions in Quicksort, 62 00:03:43,470 --> 00:03:45,060 but the compiler can tell the difference 63 00:03:45,060 --> 00:03:46,950 based on their signatures. 64 00:03:46,950 --> 00:03:48,830 And then finally we're gonna have main, 65 00:03:48,830 --> 00:03:53,830 int main and I'm gonna have return zero. 66 00:03:56,780 --> 00:03:58,560 Okay, so those are our placeholders, 67 00:03:58,560 --> 00:04:02,870 those are our signatures for the functions. 68 00:04:02,870 --> 00:04:05,270 So let's begin to flesh these out. 69 00:04:05,270 --> 00:04:09,140 First, let's do quicksort, this one here. 70 00:04:09,140 --> 00:04:11,853 Oops, again I didn't mean to paste that, sorry. 71 00:04:13,567 --> 00:04:16,400 Okay, so what do we do? 72 00:04:16,400 --> 00:04:18,040 It's a recursive function, 73 00:04:18,040 --> 00:04:20,700 we have to have a base case here's the base case 74 00:04:20,700 --> 00:04:25,700 if, and this is exactly what we had in our code 75 00:04:25,970 --> 00:04:29,373 for mergesort, if end less than or equal to start, 76 00:04:31,060 --> 00:04:36,060 that's if we have fewer than two elements, one or zero, 77 00:04:36,350 --> 00:04:39,480 that's our base case and what do we do? 78 00:04:39,480 --> 00:04:41,583 Same as mergesort, we just returned. 79 00:04:43,520 --> 00:04:45,370 Okay, so this is the base case 80 00:04:47,828 --> 00:04:49,143 of our recursion, 81 00:04:53,664 --> 00:04:54,497 all right? 82 00:04:54,497 --> 00:04:56,480 And then the recursive case. 83 00:04:56,480 --> 00:05:01,480 Else, this is where we have two or more elements, 84 00:05:02,870 --> 00:05:06,883 and I'll just put a note that this is the recursive case. 85 00:05:09,720 --> 00:05:14,720 And we have int P equals partition V, 86 00:05:18,880 --> 00:05:20,150 start and end. 87 00:05:22,160 --> 00:05:25,423 And remember that partition is gonna return an int. 88 00:05:26,780 --> 00:05:30,020 And then we make our two recursive calls 89 00:05:30,020 --> 00:05:32,760 on either side of that partition. 90 00:05:32,760 --> 00:05:37,240 So our vector is gonna be divided by P 91 00:05:37,240 --> 00:05:39,410 and then we make a recursive call 92 00:05:39,410 --> 00:05:43,630 on the portion of the vector that's to the right of P 93 00:05:43,630 --> 00:05:45,700 and then another call to the portion 94 00:05:45,700 --> 00:05:46,930 that's to the left of P. 95 00:05:46,930 --> 00:05:50,770 And you'll recall that the values of the elements 96 00:05:50,770 --> 00:05:54,180 to the left of P will be less than P 97 00:05:54,180 --> 00:05:57,700 and the values to the right of P 98 00:05:57,700 --> 00:06:00,423 will be greater than or equal to the value index by P. 99 00:06:01,568 --> 00:06:03,550 Okay, so we have these two calls, 100 00:06:03,550 --> 00:06:08,550 quicksort V, start 101 00:06:10,669 --> 00:06:13,203 and this one's gonna run two P minus one. 102 00:06:14,270 --> 00:06:17,920 Okay, that's the stuff to the left of P, 103 00:06:17,920 --> 00:06:19,320 and then again, quicksort P, 104 00:06:22,196 --> 00:06:25,150 and this is gonna run from P plus one to end, 105 00:06:28,066 --> 00:06:29,953 and those are our two recursive calls. 106 00:06:31,780 --> 00:06:34,800 And that's the complete function here. 107 00:06:34,800 --> 00:06:36,620 Most of the work is gonna be done 108 00:06:36,620 --> 00:06:38,820 in the partition function. 109 00:06:38,820 --> 00:06:40,233 So let's do that now. 110 00:06:41,220 --> 00:06:43,000 And if you recall, 111 00:06:43,000 --> 00:06:45,500 the first thing we're gonna do is we're gonna set, 112 00:06:46,880 --> 00:06:48,830 we're gonna get the value of the pivot, 113 00:06:51,530 --> 00:06:52,900 comparable pivot 114 00:06:55,240 --> 00:06:58,630 and we're gonna get the value at the end of our sub-sector. 115 00:06:58,630 --> 00:06:59,640 So V, end, 116 00:07:01,210 --> 00:07:03,210 and this is one way to get the pivot later on, 117 00:07:03,210 --> 00:07:04,660 we'll take a look at another. 118 00:07:05,735 --> 00:07:09,973 And that pivot in the book it's referred to as divider pivot 119 00:07:09,973 --> 00:07:12,210 it's a far more common term, 120 00:07:12,210 --> 00:07:15,390 if you look at other books or articles, 121 00:07:15,390 --> 00:07:17,720 you'll see pivot more than you'll see divider. 122 00:07:17,720 --> 00:07:20,330 And so this is the value 123 00:07:20,330 --> 00:07:22,750 that we're going to use to partition. 124 00:07:22,750 --> 00:07:24,700 So everything less than the pivot 125 00:07:24,700 --> 00:07:26,040 is gonna go to one side 126 00:07:26,040 --> 00:07:28,490 and everything that's greater than the pivot 127 00:07:28,490 --> 00:07:29,990 is gonna go to the other side. 128 00:07:30,880 --> 00:07:35,880 Okay, so we need to initialize this index to start. 129 00:07:38,690 --> 00:07:41,360 And here we're following that pseudocode 130 00:07:41,360 --> 00:07:43,730 that was presented in the previous video, 131 00:07:43,730 --> 00:07:45,610 almost line by line 132 00:07:45,610 --> 00:07:50,480 for int J equal start 133 00:07:52,300 --> 00:07:57,300 to J, sorry, J less than or equal to the end plus J. 134 00:08:03,270 --> 00:08:05,100 And then within the body of that loop, 135 00:08:05,100 --> 00:08:06,110 the first thing we're gonna do 136 00:08:06,110 --> 00:08:08,440 is we're gonna perform a comparison. 137 00:08:08,440 --> 00:08:13,440 If V sub J is less than that pivot, 138 00:08:18,390 --> 00:08:20,470 then we're gonna swap. 139 00:08:20,470 --> 00:08:21,520 And what did we swap? 140 00:08:21,520 --> 00:08:23,840 If you recall, again, from the previous video 141 00:08:23,840 --> 00:08:28,840 we're gonna swap the values at V sub of i 142 00:08:30,850 --> 00:08:35,850 and sub J, okay? 143 00:08:36,630 --> 00:08:39,020 And then the swapping code should look very familiar 144 00:08:39,020 --> 00:08:39,853 to you. 145 00:08:39,853 --> 00:08:44,710 Comparable temp is gonna take the value of V sub J. 146 00:08:47,330 --> 00:08:50,747 V sub J it's gonna take the value of V sub i 147 00:08:53,440 --> 00:08:57,873 and V sub i is gonna take the value of temp. 148 00:08:59,910 --> 00:09:03,570 There is our swap, and then we increment i. 149 00:09:03,570 --> 00:09:05,650 Again as you recall, from the previous video 150 00:09:05,650 --> 00:09:08,043 we increment i when we've made the swap. 151 00:09:09,020 --> 00:09:12,980 And then we only have one other thing to do here. 152 00:09:12,980 --> 00:09:17,870 And that is after this loop is finished, 153 00:09:17,870 --> 00:09:22,870 we swap the values at the position V sub i at the end. 154 00:09:23,720 --> 00:09:26,090 And that's our last step of the algorithm. 155 00:09:26,090 --> 00:09:29,690 So I'm just gonna put a note to that effect here, 156 00:09:29,690 --> 00:09:33,057 swap V sub i 157 00:09:35,411 --> 00:09:37,303 and V, end, 158 00:09:38,660 --> 00:09:41,470 and then this is gonna be pretty much the same, 159 00:09:41,470 --> 00:09:44,130 comparable temp 160 00:09:46,200 --> 00:09:48,833 equals V sub i this time. 161 00:09:50,610 --> 00:09:55,437 V sub i gets the value at the end 162 00:09:58,010 --> 00:10:03,010 and V end gets the value from the temp 163 00:10:03,080 --> 00:10:05,170 and that completes our swap 164 00:10:05,170 --> 00:10:09,060 and then the last thing we do is we return that index i, 165 00:10:09,060 --> 00:10:09,893 return i. 166 00:10:12,220 --> 00:10:14,400 And so that int that we return 167 00:10:15,820 --> 00:10:20,200 becomes assigned to this variable P 168 00:10:20,200 --> 00:10:22,600 and that's used as a divider 169 00:10:22,600 --> 00:10:25,040 when we make our recursive calls. 170 00:10:25,040 --> 00:10:29,183 So that is a complete implementation of quicksort. 171 00:10:30,380 --> 00:10:34,560 Let's just flush out this other method here. 172 00:10:34,560 --> 00:10:38,601 And all we're gonna do is since we're passing in 173 00:10:38,601 --> 00:10:41,110 you'll see we're passing in the vector. 174 00:10:41,110 --> 00:10:42,260 We wanna call quicksort 175 00:10:44,310 --> 00:10:48,540 again with the vector V 176 00:10:48,540 --> 00:10:50,880 and since we're only gonna use this 177 00:10:50,880 --> 00:10:54,040 for the first call to quicksort for main, 178 00:10:54,040 --> 00:10:57,150 we're going to run range over zero 179 00:10:57,150 --> 00:11:00,410 to the last element of the vector, 180 00:11:00,410 --> 00:11:04,867 which is indexed by V.size minus one. 181 00:11:09,280 --> 00:11:11,800 And mostly what that's doing is 182 00:11:11,800 --> 00:11:15,900 it's going to make our code in main a little prettier, 183 00:11:15,900 --> 00:11:20,900 but also when we get to comparing many sorting algorithms 184 00:11:21,290 --> 00:11:24,610 in our project, I think it's project four, 185 00:11:24,610 --> 00:11:28,520 it will be convenient if all of the algorithms 186 00:11:28,520 --> 00:11:30,690 have an entry point that looks the same, 187 00:11:30,690 --> 00:11:33,010 where you just pass in a vector. 188 00:11:33,010 --> 00:11:35,910 And so we have this little function 189 00:11:35,910 --> 00:11:38,823 that just adds the extra parameters as needed. 190 00:11:39,760 --> 00:11:44,030 So then we could call mergesort V, quicksort V, 191 00:11:44,030 --> 00:11:46,480 bubblesort V and so on. 192 00:11:46,480 --> 00:11:50,060 And you'll notice that some of the algorithms 193 00:11:50,060 --> 00:11:53,210 take additional parameters like these here and some don't. 194 00:11:53,210 --> 00:11:56,330 So this makes for a uniform presentation in main, 195 00:11:56,330 --> 00:11:58,160 that's all it's doing. 196 00:11:58,160 --> 00:11:59,853 Okay, so let's complete main. 197 00:12:00,920 --> 00:12:03,470 This again should look familiar 198 00:12:03,470 --> 00:12:06,470 based on some of the other sorting algorithms 199 00:12:06,470 --> 00:12:08,670 and the main functions we've used to test them. 200 00:12:08,670 --> 00:12:11,130 I'm just gonna run the algorithm through its paces, 201 00:12:11,130 --> 00:12:12,810 so we need a vector, 202 00:12:12,810 --> 00:12:16,513 standard vector of comparables, 203 00:12:18,910 --> 00:12:21,433 oh, no, we're gonna make it a ints, sorry. 204 00:12:22,570 --> 00:12:23,783 We'll call that V, 205 00:12:25,090 --> 00:12:30,090 and let's give it some numbers, eight, five, zero, 206 00:12:34,570 --> 00:12:39,200 four, three, nine, one, 207 00:12:39,200 --> 00:12:42,060 seven, two, six. 208 00:12:42,060 --> 00:12:47,060 Okay, that's all of the digits, zero to nine, 209 00:12:47,200 --> 00:12:49,050 all jumbled up. 210 00:12:49,050 --> 00:12:51,000 And then what are we gonna do? 211 00:12:51,000 --> 00:12:55,483 Well, we're going to print vector P. 212 00:12:56,650 --> 00:13:01,420 We're gonna call quicksort V, 213 00:13:01,420 --> 00:13:02,950 and that's gonna call this one 214 00:13:02,950 --> 00:13:05,200 and then this one is gonna call this 215 00:13:05,200 --> 00:13:07,500 with the correct parameters. 216 00:13:07,500 --> 00:13:12,500 And print vector P, again, that's it. 217 00:13:14,490 --> 00:13:16,793 So if I haven't made any typos, 218 00:13:18,970 --> 00:13:19,803 this looks good. 219 00:13:21,350 --> 00:13:22,750 This should compile and run. 220 00:13:29,010 --> 00:13:30,320 Okay, and let's run it 221 00:13:31,160 --> 00:13:34,300 and it should print out the unsorted vector 222 00:13:34,300 --> 00:13:35,133 and the sort of the vector 223 00:13:35,133 --> 00:13:36,790 and that's exactly what we've got here. 224 00:13:36,790 --> 00:13:40,000 Here's our unsorted doctor before the call to quicksort 225 00:13:41,100 --> 00:13:44,613 and here is our sorted vector after the call to quicksort, 226 00:13:45,660 --> 00:13:46,890 and that's exactly what we'd expect. 227 00:13:46,890 --> 00:13:51,890 So now we've completed the first implementation. 228 00:13:53,570 --> 00:13:57,720 Let's move on to a slightly different implementation 229 00:13:57,720 --> 00:14:01,410 where we implement the median of three method 230 00:14:01,410 --> 00:14:03,800 for choosing a pivot. 231 00:14:03,800 --> 00:14:05,140 So now that we have that working, 232 00:14:05,140 --> 00:14:09,080 let's continue and implement a version of Quicksort 233 00:14:09,080 --> 00:14:12,273 using the median of three approach to choose the pivot. 234 00:14:13,150 --> 00:14:15,560 You'll recall that we saw that in the previous video 235 00:14:15,560 --> 00:14:20,343 and what I'm gonna do, I'm just gonna copy all this, 236 00:14:23,260 --> 00:14:25,563 and make a few minor changes. 237 00:14:26,860 --> 00:14:30,090 I'm gonna call this partition median three 238 00:14:35,250 --> 00:14:39,330 and this will be quicksort median three 239 00:14:39,330 --> 00:14:42,670 and it's going to call partition median three 240 00:14:42,670 --> 00:14:44,603 and quicksort median three. 241 00:14:45,490 --> 00:14:47,240 And what we're doing is guaranteeing 242 00:14:47,240 --> 00:14:49,170 that we're going to call the correct version 243 00:14:49,170 --> 00:14:51,169 of partition here, which we're gonna modify in a second. 244 00:14:51,169 --> 00:14:54,893 And then quicksort media three. 245 00:14:56,550 --> 00:14:58,600 And then in our main, we'll get to that a little later, 246 00:14:58,600 --> 00:14:59,650 we'll call both of these 247 00:14:59,650 --> 00:15:01,540 and make sure that they're both working. 248 00:15:01,540 --> 00:15:02,670 So now what do we need to do? 249 00:15:02,670 --> 00:15:05,693 We need to modify the partition function. 250 00:15:07,420 --> 00:15:09,150 Wait, where did I go, I lost it? 251 00:15:09,150 --> 00:15:10,560 There it is, okay. 252 00:15:10,560 --> 00:15:13,540 We're gonna modify this partition function. 253 00:15:13,540 --> 00:15:17,660 And if you recall, the median of three method 254 00:15:17,660 --> 00:15:19,820 leaves the median value 255 00:15:19,820 --> 00:15:22,790 of the starting element in the vector, 256 00:15:22,790 --> 00:15:24,720 the middle element and the vector 257 00:15:24,720 --> 00:15:27,630 and the ending element vector in the end position. 258 00:15:27,630 --> 00:15:30,970 And we perform three comparisons on up to three swaps. 259 00:15:30,970 --> 00:15:32,470 So the first thing we need to do 260 00:15:32,470 --> 00:15:37,210 is calculate the middle of the vector or the sub vector 261 00:15:37,210 --> 00:15:38,490 as the case maybe. 262 00:15:38,490 --> 00:15:41,920 And we've seen this before in mergesort, 263 00:15:41,920 --> 00:15:44,570 we have int middle 264 00:15:46,100 --> 00:15:50,180 equals start plus end 265 00:15:51,410 --> 00:15:52,890 divided by two. 266 00:15:52,890 --> 00:15:55,180 And that's integer division as before 267 00:15:55,180 --> 00:15:57,780 so if we have an on a little truncate. 268 00:15:57,780 --> 00:15:59,390 And then we have three comparisons, 269 00:15:59,390 --> 00:16:04,390 the first one, if the sub middle, 270 00:16:06,640 --> 00:16:10,693 sorry, less than the sub start. 271 00:16:12,680 --> 00:16:13,610 And then what do we do? 272 00:16:13,610 --> 00:16:18,363 We swap middle and start. 273 00:16:20,110 --> 00:16:24,240 And this should look let's just borrow this here 274 00:16:25,930 --> 00:16:27,550 and make a few changes, 275 00:16:27,550 --> 00:16:30,453 so we have comparable temp is gonna take V start. 276 00:16:32,740 --> 00:16:36,007 V start is gonna take Vmiddle 277 00:16:38,090 --> 00:16:39,690 and V middle is gonna take temp. 278 00:16:42,250 --> 00:16:43,963 And that's our first case. 279 00:16:44,940 --> 00:16:46,340 And we're gonna have two other cases 280 00:16:46,340 --> 00:16:47,900 that look very much like this. 281 00:16:47,900 --> 00:16:50,883 So let's just copy this now. 282 00:16:52,430 --> 00:16:56,283 And our second is we're gonna compare end and start. 283 00:16:59,160 --> 00:17:02,070 And if end is less than start 284 00:17:02,070 --> 00:17:05,393 then we're gonna swap end and start. 285 00:17:06,420 --> 00:17:09,070 And this swap is gonna be similar, 286 00:17:09,070 --> 00:17:12,273 start, start, this one's gonna become end. 287 00:17:16,590 --> 00:17:17,823 And this one and here, 288 00:17:19,810 --> 00:17:22,340 and then, yeah, one more comparison, 289 00:17:22,340 --> 00:17:24,040 and possibly one more swap 290 00:17:25,120 --> 00:17:26,543 where we do middle and end? 291 00:17:29,470 --> 00:17:32,053 Swap middle and end. 292 00:17:33,390 --> 00:17:37,167 And then this becomes V middle, V end, 293 00:17:42,781 --> 00:17:44,837 oh sorry, V middle gets V end 294 00:17:49,830 --> 00:17:51,123 and V end gets temp. 295 00:17:53,920 --> 00:17:57,700 And that's our median of three method here. 296 00:17:57,700 --> 00:18:00,750 This parallels V pseudocode 297 00:18:00,750 --> 00:18:03,320 that was presented in the previous video, 298 00:18:03,320 --> 00:18:07,810 and it takes the beginning, middle and end elements 299 00:18:07,810 --> 00:18:09,960 and chooses the median of three 300 00:18:09,960 --> 00:18:13,880 and leaves that value in the end position. 301 00:18:13,880 --> 00:18:18,880 And so now when we take this comparable pivot here 302 00:18:20,010 --> 00:18:24,490 equal to V end, this V end is now the median 303 00:18:24,490 --> 00:18:27,190 of the three and the other two 304 00:18:27,190 --> 00:18:31,230 have been swapped into the appropriate positions as needed. 305 00:18:31,230 --> 00:18:34,610 So that's the entirety of quicksort 306 00:18:34,610 --> 00:18:36,910 using the median three approach. 307 00:18:36,910 --> 00:18:38,700 And so now what we're gonna do 308 00:18:38,700 --> 00:18:40,340 is we're gonna modify main a little bit. 309 00:18:40,340 --> 00:18:43,530 I'm gonna call this a base vector 310 00:18:43,530 --> 00:18:44,840 'cause we're gonna make copies of it 311 00:18:44,840 --> 00:18:48,860 to make sure that the input to the two vectors we have 312 00:18:48,860 --> 00:18:50,433 is the same. 313 00:18:51,720 --> 00:18:56,230 And so we're gonna have quicksort median three 314 00:18:57,660 --> 00:19:02,660 and here we're gonna have standard vector of ints, 315 00:19:05,750 --> 00:19:09,323 sorry, the equal base vector. 316 00:19:13,170 --> 00:19:16,633 We're just gonna make a copy of that, sorry, base vector. 317 00:19:18,180 --> 00:19:20,330 And now we're gonna do the same thing here. 318 00:19:22,300 --> 00:19:26,230 So we ensure that both the first Quicksort version 319 00:19:26,230 --> 00:19:29,410 we implemented and the newer version using media three, 320 00:19:29,410 --> 00:19:31,383 both get the exactly the same input. 321 00:19:33,720 --> 00:19:37,913 So, if I haven't made any typos that should build, 322 00:19:39,980 --> 00:19:42,060 okay, and it should run. 323 00:19:42,060 --> 00:19:43,903 Let me do something here real quick. 324 00:19:46,436 --> 00:19:47,983 Just putting in a blank line 325 00:19:50,290 --> 00:19:53,973 to separate the outputs of these two tests here, 326 00:19:55,910 --> 00:19:57,840 build and run. 327 00:19:57,840 --> 00:20:00,540 And what we should see is two identical outputs. 328 00:20:00,540 --> 00:20:03,500 Here's the unsorted input vector, 329 00:20:03,500 --> 00:20:06,080 here's the sorted output vector, 330 00:20:06,080 --> 00:20:09,080 here's the unsorted input vector 331 00:20:09,080 --> 00:20:11,430 and the sorted output vector. 332 00:20:11,430 --> 00:20:14,900 And now what we're gonna do is we're gonna set timers 333 00:20:14,900 --> 00:20:19,900 on these algorithms and we're gonna supply the algorithms 334 00:20:19,970 --> 00:20:24,970 with sorted and shuffled vectors to see how they perform. 335 00:20:26,440 --> 00:20:28,120 Okay, so now what we're gonna do 336 00:20:28,120 --> 00:20:30,360 is we're gonna set some timers on this 337 00:20:30,360 --> 00:20:31,740 and we're gonna see 338 00:20:31,740 --> 00:20:35,200 how Quicksort performs with and without 339 00:20:35,200 --> 00:20:40,023 this median of three method for choosing the pivot. 340 00:20:42,160 --> 00:20:45,440 So let me think, 341 00:20:45,440 --> 00:20:46,490 what I'm gonna do, 342 00:20:46,490 --> 00:20:48,770 actually, I'm gonna make a copy of this 343 00:20:52,710 --> 00:20:56,063 and call it quicksort two and this'll be our timed version. 344 00:20:58,000 --> 00:21:00,760 And we're gonna need to make some modifications 345 00:21:00,760 --> 00:21:03,460 to the includes, so we're gonna need to include chrono 346 00:21:10,380 --> 00:21:12,150 and that's for timing 347 00:21:12,150 --> 00:21:17,150 and include random that's for shuffling, okay? 348 00:21:20,880 --> 00:21:23,210 That print vector function stays the same. 349 00:21:23,210 --> 00:21:25,140 All of these stay the same, 350 00:21:25,140 --> 00:21:26,740 I guess we just 351 00:21:28,670 --> 00:21:31,213 need to modify main, okay. 352 00:21:33,040 --> 00:21:35,500 So in main, we're going to 353 00:21:35,500 --> 00:21:38,140 want to be able to shuffle our vectors. 354 00:21:38,140 --> 00:21:42,293 So we're going to need the standard random device, 355 00:21:48,450 --> 00:21:52,270 call that rd, short for random device. 356 00:21:52,270 --> 00:21:54,290 And then instead of this vector 357 00:21:54,290 --> 00:21:56,720 we're gonna create a much bigger vector. 358 00:21:56,720 --> 00:21:59,630 So standard vector int 359 00:21:59,630 --> 00:22:03,043 we'll continue to call this a base vector, 360 00:22:04,100 --> 00:22:05,743 but then we'll get rid of this. 361 00:22:06,830 --> 00:22:11,830 And then we'll initialize it for int i equal zero, 362 00:22:15,430 --> 00:22:20,430 i less than 10,000, say plus plus i. 363 00:22:24,810 --> 00:22:26,160 And then what we're gonna do 364 00:22:26,160 --> 00:22:30,720 is we're just gonna push that i on to the a vector. 365 00:22:30,720 --> 00:22:32,100 So base vector 366 00:22:35,930 --> 00:22:39,053 pushback i. 367 00:22:40,270 --> 00:22:43,460 So that's gonna give us a vector of 10,000 elements 368 00:22:43,460 --> 00:22:47,123 ranging from zero to 9,999. 369 00:22:49,590 --> 00:22:53,490 And then we're gonna want to shuffle the vector. 370 00:22:53,490 --> 00:22:56,230 So standard 371 00:22:59,770 --> 00:23:03,623 shuffle base vector, 372 00:23:05,330 --> 00:23:06,880 and we give begin 373 00:23:10,830 --> 00:23:11,900 and the end 374 00:23:17,040 --> 00:23:20,160 and the random device, rd. 375 00:23:20,160 --> 00:23:24,723 And that's our syntax for a shuffling of vector. 376 00:23:25,860 --> 00:23:28,640 And so now we should have a shuffled vector. 377 00:23:28,640 --> 00:23:31,060 Let's do some tests and some timing. 378 00:23:31,060 --> 00:23:34,313 First we're going to work with the shuffled vector. 379 00:23:37,030 --> 00:23:39,930 So let's put a line in our output 380 00:23:39,930 --> 00:23:43,583 to indicate that shuffled collector and 381 00:23:55,386 --> 00:24:00,386 all right, and then vector into V equals base vector 382 00:24:00,410 --> 00:24:03,970 and so we're not gonna want these print statements 383 00:24:03,970 --> 00:24:07,530 'cause we don't wanna print out 10,000 elements, 384 00:24:07,530 --> 00:24:08,530 that would be silly. 385 00:24:10,040 --> 00:24:11,250 So what we're gonna do instead 386 00:24:11,250 --> 00:24:16,250 is we're gonna set timers and let's see auto start time. 387 00:24:20,800 --> 00:24:22,560 And I'll explain all this in a minute, 388 00:24:22,560 --> 00:24:24,380 I think we've seen this before 389 00:24:24,380 --> 00:24:27,550 but I will explain it in just a second, 390 00:24:27,550 --> 00:24:31,483 equals let me think here, standard, 391 00:24:33,530 --> 00:24:35,927 chrono, high resolution clock 392 00:24:49,255 --> 00:24:50,088 and now. 393 00:24:54,180 --> 00:24:56,940 And so what this is, oh, I got to booboo here, 394 00:24:56,940 --> 00:24:58,400 how do I start time? 395 00:24:58,400 --> 00:25:01,360 And so what this is doing is it's saying 396 00:25:01,360 --> 00:25:04,063 auto is just a keyword that's saying a 397 00:25:04,063 --> 00:25:07,440 C++ compiler I think you're smart enough to figure out 398 00:25:07,440 --> 00:25:08,680 what type this is 399 00:25:08,680 --> 00:25:12,060 and so it's gonna type start time for us. 400 00:25:12,060 --> 00:25:14,800 And so here we have standard chrono 401 00:25:14,800 --> 00:25:17,150 we're making reference to the chrono library 402 00:25:17,150 --> 00:25:20,280 and this thing called the high resolution clock 403 00:25:20,280 --> 00:25:23,100 and we're calling this a method called now, 404 00:25:23,100 --> 00:25:28,100 and that's going to give a timestamp in microseconds, okay? 405 00:25:28,530 --> 00:25:31,000 And then we're gonna run quicksort 406 00:25:31,000 --> 00:25:34,373 and then we're gonna do exactly the same thing here, 407 00:25:34,373 --> 00:25:36,000 we're just gonna copy this line, 408 00:25:36,000 --> 00:25:38,477 make a call to exactly the same function, 409 00:25:38,477 --> 00:25:40,277 except we're gonna call it end time, 410 00:25:41,240 --> 00:25:43,580 and so we get the timestamp here 411 00:25:43,580 --> 00:25:45,670 and the timestamp as soon as we're done, 412 00:25:45,670 --> 00:25:47,524 that's in microseconds again. 413 00:25:47,524 --> 00:25:51,320 And then we're gonna perform a little conversion 414 00:25:51,320 --> 00:25:55,720 auto duration, 415 00:25:55,720 --> 00:25:57,730 which is ultimately gonna be the start time 416 00:25:57,730 --> 00:26:01,370 minus the end time but we have to do a little juggling here 417 00:26:01,370 --> 00:26:05,210 equals a standard chrono 418 00:26:09,560 --> 00:26:11,230 duration cast, 419 00:26:11,230 --> 00:26:14,150 see how that filled it in automatically for us 420 00:26:14,150 --> 00:26:18,947 standard chrono microseconds. 421 00:26:25,620 --> 00:26:28,910 Okay, so we're saying we want this output all 422 00:26:28,910 --> 00:26:31,760 in microseconds 423 00:26:31,760 --> 00:26:35,330 and then we want end time, sorry, 424 00:26:35,330 --> 00:26:40,017 end time minus start time and count. 425 00:26:42,270 --> 00:26:45,280 And what count does, is it counts the microseconds 426 00:26:45,280 --> 00:26:48,010 in that calculated interval. 427 00:26:48,010 --> 00:26:52,020 And, well that's a long line, 428 00:26:52,020 --> 00:26:56,030 but no, let's break it. I don't like long lines. 429 00:26:56,030 --> 00:26:58,570 Okay, so that'll work. 430 00:26:58,570 --> 00:27:00,870 And so what we're doing here is we're getting a timestamp 431 00:27:00,870 --> 00:27:03,170 for the start, we're running quicksort, 432 00:27:03,170 --> 00:27:05,010 we're getting the timestamp for the end time, 433 00:27:05,010 --> 00:27:08,320 we're calculating the duration in microseconds 434 00:27:08,320 --> 00:27:12,320 and then we will print the result. 435 00:27:12,320 --> 00:27:15,123 And so that's standard cout, 436 00:27:16,740 --> 00:27:18,143 excuse me quicksort 437 00:27:22,229 --> 00:27:24,933 and we're gonna give the duration. 438 00:27:26,370 --> 00:27:28,210 Now that's gonna be in microseconds 439 00:27:28,210 --> 00:27:29,830 so it's gonna be a big number 440 00:27:31,712 --> 00:27:33,610 and an endline. 441 00:27:33,610 --> 00:27:35,300 And I'm not gonna fuss with formatting 442 00:27:35,300 --> 00:27:38,300 it it'll be readable enough for us. 443 00:27:38,300 --> 00:27:39,380 And then what we're gonna do 444 00:27:39,380 --> 00:27:42,520 is we're gonna do exactly the same thing 445 00:27:45,500 --> 00:27:47,923 for our quicksort median three. 446 00:27:55,180 --> 00:27:57,730 And that's gonna be quicksort median three 447 00:27:57,730 --> 00:28:00,790 and since we've already declared start time and end time 448 00:28:00,790 --> 00:28:02,410 we don't need the autos here anymore 449 00:28:02,410 --> 00:28:04,313 and duration we don't need anymore. 450 00:28:06,620 --> 00:28:09,580 And so the code that we have here now, 451 00:28:09,580 --> 00:28:10,810 let's just recap. 452 00:28:10,810 --> 00:28:13,180 Let me just get rid of that. 453 00:28:15,380 --> 00:28:18,430 Let's just recap real quick what we have here 454 00:28:18,430 --> 00:28:21,700 is we're getting the random device 455 00:28:21,700 --> 00:28:23,713 that we're gonna need for a shuffling, 456 00:28:24,820 --> 00:28:29,820 we're creating a base vector of 10,000 elements. 457 00:28:30,090 --> 00:28:32,670 We are shuffling that so that's gonna randomize 458 00:28:32,670 --> 00:28:35,410 the order of all the elements in the vector 459 00:28:35,410 --> 00:28:37,440 and then we're printing a little heading here 460 00:28:37,440 --> 00:28:39,860 that we're working with a shuffled vector. 461 00:28:39,860 --> 00:28:44,373 And then we are making a copy of that base vector, 462 00:28:45,260 --> 00:28:49,280 we don't need this here, calling that V 463 00:28:49,280 --> 00:28:51,620 and passing V to quicksort, 464 00:28:51,620 --> 00:28:53,730 we're setting timers at the beginning of the end, 465 00:28:53,730 --> 00:28:54,840 we're getting the duration 466 00:28:54,840 --> 00:28:57,400 and we're gonna print out the duration, 467 00:28:57,400 --> 00:28:58,890 put a blank line, 468 00:28:58,890 --> 00:29:03,770 and we're going to then reassign based vector to V 469 00:29:03,770 --> 00:29:05,020 we're gonna do the same thing 470 00:29:05,020 --> 00:29:10,020 for the median of three algorithm and then print the result. 471 00:29:10,160 --> 00:29:12,520 Now let's do that right now. 472 00:29:12,520 --> 00:29:15,330 And again, if I don't have any typos 473 00:29:15,330 --> 00:29:16,290 reload this 474 00:29:23,333 --> 00:29:26,166 I need to add this, sorry, my bad. 475 00:29:32,900 --> 00:29:35,120 Okay, so now we have to execute bubbles, 476 00:29:35,120 --> 00:29:36,747 we can build quicksort2 477 00:29:38,030 --> 00:29:40,973 and we'll run it and, 478 00:29:43,770 --> 00:29:44,603 oops! 479 00:29:47,490 --> 00:29:52,455 Okay, so here's shuffled vector and quicksort 480 00:29:52,455 --> 00:29:53,290 and quicksort median of three 481 00:29:53,290 --> 00:29:57,500 and almost exactly the same number of microseconds 482 00:29:57,500 --> 00:30:01,130 with a shuffled vector as the input, okay? 483 00:30:01,130 --> 00:30:03,563 Let's move this out here. 484 00:30:05,330 --> 00:30:10,330 And now we're going to feed it as sorted vector 485 00:30:10,530 --> 00:30:11,900 and see what the result is. 486 00:30:11,900 --> 00:30:13,733 So let's go back. 487 00:30:16,980 --> 00:30:20,600 And we are going to, 488 00:30:20,600 --> 00:30:22,650 let's see what's the best way to do this, 489 00:30:24,210 --> 00:30:25,573 that's base vector, 490 00:30:30,110 --> 00:30:32,875 base vector clear, 491 00:30:32,875 --> 00:30:35,960 clear is a method that just empties out a vector. 492 00:30:35,960 --> 00:30:39,490 So whatever we had in that vector, that's gone now. 493 00:30:39,490 --> 00:30:41,030 And now we're gonna initialize it 494 00:30:41,030 --> 00:30:42,790 the same way we did before, 495 00:30:42,790 --> 00:30:47,640 just taking the numbers from zero to 9,999 496 00:30:47,640 --> 00:30:51,230 except this time we are not going to shuffle it. 497 00:30:51,230 --> 00:30:53,180 And so we'll put a little heading here. 498 00:30:59,970 --> 00:31:02,253 This is the sorted vector. 499 00:31:12,660 --> 00:31:17,283 Okay, and then we're gonna take all this exact same stuff. 500 00:31:22,240 --> 00:31:23,943 Okay, and just copy paste, 501 00:31:25,780 --> 00:31:28,440 and we just need to make a few minor changes here, 502 00:31:28,440 --> 00:31:33,440 we don't need these type specifiers 503 00:31:33,610 --> 00:31:38,610 in the assignments 504 00:31:38,980 --> 00:31:41,493 'cause we already know what those are. 505 00:31:42,510 --> 00:31:46,170 And so now just to recap, 506 00:31:46,170 --> 00:31:48,450 we've taken that base vector that shuffled vector, 507 00:31:48,450 --> 00:31:51,490 and we've wiped out all of the values, 508 00:31:51,490 --> 00:31:52,800 we've emptied into values. 509 00:31:52,800 --> 00:31:56,900 And then we've created a new vector that's sorted. 510 00:31:56,900 --> 00:31:59,160 If we just do this it's gonna give us a vector 511 00:31:59,160 --> 00:32:01,610 that's in ascending order. 512 00:32:01,610 --> 00:32:03,640 And so now we've printed out a little heading 513 00:32:03,640 --> 00:32:05,530 that says sorted vector, 514 00:32:05,530 --> 00:32:10,530 we assigned the base vector to V, 515 00:32:10,970 --> 00:32:13,460 we set the timer, we were run quicksort, 516 00:32:13,460 --> 00:32:16,133 we get the end time, we calculate the duration, 517 00:32:17,014 --> 00:32:19,790 we put print the duration, and then the same thing 518 00:32:19,790 --> 00:32:23,230 for the quicksort median three algorithm. 519 00:32:23,230 --> 00:32:25,283 And again, if I've had no typos, 520 00:32:26,830 --> 00:32:27,853 this should build. 521 00:32:32,630 --> 00:32:35,083 Okay, that looks good, and now let's run it. 522 00:32:40,600 --> 00:32:43,170 Now, look at the results here. 523 00:32:43,170 --> 00:32:44,650 This is for our shuffled back there 524 00:32:44,650 --> 00:32:46,070 and you can see the quicksort 525 00:32:46,070 --> 00:32:50,450 and quicksort median of three have comparable performance, 526 00:32:50,450 --> 00:32:53,490 so median three is slightly faster 527 00:32:53,490 --> 00:32:55,490 and that's where the shuffled vector. 528 00:32:55,490 --> 00:32:58,853 But now look at what happens with the sorted vector. 529 00:32:58,853 --> 00:33:03,010 Quicksort performance deteriorates horribly. 530 00:33:03,010 --> 00:33:05,207 This is 1, 293,000 microseconds 531 00:33:10,181 --> 00:33:14,143 as compared to a little under 3000. 532 00:33:15,870 --> 00:33:19,610 And here we have virtually the same performance 533 00:33:19,610 --> 00:33:23,560 for the median of three version that we have above. 534 00:33:23,560 --> 00:33:27,270 So you can see at least in this simple test, 535 00:33:27,270 --> 00:33:30,560 that median of three vastly outperforms, 536 00:33:30,560 --> 00:33:33,190 the version of quicksort where we just naively picked 537 00:33:33,190 --> 00:33:36,060 from the end of the vector to choose our pivot. 538 00:33:36,060 --> 00:33:41,060 So this clearly is a better method for choosing our pivot. 539 00:33:41,450 --> 00:33:45,380 And I hope you found that coding session 540 00:33:45,380 --> 00:33:48,163 and experiment instructive, okay?