1 00:00:00,349 --> 00:00:01,349 - Quicksort. 2 00:00:02,300 --> 00:00:05,260 I showed this image of a 1959 six pence 3 00:00:05,260 --> 00:00:07,570 because once there was a six pence bet 4 00:00:07,570 --> 00:00:09,500 between the inventor of quicksort, 5 00:00:09,500 --> 00:00:13,130 Sir Tony Hoare and his employer at the time. 6 00:00:13,130 --> 00:00:16,150 Tony was asked to implement a version of shell sort. 7 00:00:16,150 --> 00:00:19,910 Shell short is an improved version of insertion sort. 8 00:00:19,910 --> 00:00:22,790 And Tony said he knew a faster algorithm. 9 00:00:22,790 --> 00:00:23,623 They made a bet. 10 00:00:23,623 --> 00:00:25,510 And while you can guess what happened. 11 00:00:25,510 --> 00:00:27,060 Now we have quicksort which is one 12 00:00:27,060 --> 00:00:29,260 of the fastest sorting algorithms we have 13 00:00:29,260 --> 00:00:31,403 for a wide variety of use cases. 14 00:00:34,110 --> 00:00:34,943 Like merge sort, 15 00:00:34,943 --> 00:00:37,670 quicksort is a divide-and-conquer algorithm. 16 00:00:37,670 --> 00:00:38,820 And as you recall, 17 00:00:38,820 --> 00:00:41,040 divide-and-conquer algorithms break down 18 00:00:41,040 --> 00:00:43,590 a problem recursively and then combine the results 19 00:00:43,590 --> 00:00:46,163 of subproblems to produce the final result. 20 00:00:48,210 --> 00:00:50,910 To refresh our memory on recursion, 21 00:00:50,910 --> 00:00:53,110 recursive functions call themselves. 22 00:00:53,110 --> 00:00:54,830 And they require a base case. 23 00:00:54,830 --> 00:00:58,200 And here the base case is vector of one element 24 00:00:58,200 --> 00:01:00,180 which is already sorted. 25 00:01:00,180 --> 00:01:02,550 And we've seen now many examples 26 00:01:02,550 --> 00:01:04,420 of recursive functions in this class. 27 00:01:04,420 --> 00:01:06,910 Merge sort in some previous videos, 28 00:01:06,910 --> 00:01:07,743 Fibonacci, 29 00:01:07,743 --> 00:01:10,083 factorial and Shamos' subsequence sum. 30 00:01:13,014 --> 00:01:14,700 So what is quicksort? 31 00:01:14,700 --> 00:01:16,810 Well let's look at some pseudocode. 32 00:01:16,810 --> 00:01:19,370 What do you notice about this algorithm? 33 00:01:19,370 --> 00:01:21,970 When we compare it with merge sort what's different? 34 00:01:23,100 --> 00:01:23,933 Well, 35 00:01:23,933 --> 00:01:24,963 let's walk through it. 36 00:01:24,963 --> 00:01:28,250 Quicksort picks an element to divide the array. 37 00:01:28,250 --> 00:01:29,690 We call that the pivot. 38 00:01:29,690 --> 00:01:31,950 I think your book calls it the divider 39 00:01:33,220 --> 00:01:36,073 but pivot is a more common term. 40 00:01:37,380 --> 00:01:40,110 Move items less than the pivot to the left 41 00:01:40,110 --> 00:01:42,930 of the pivot and move items greater than 42 00:01:42,930 --> 00:01:45,593 or equal to the pivot to the right of the pivot. 43 00:01:46,780 --> 00:01:48,560 And then we let p be the index 44 00:01:48,560 --> 00:01:50,410 of the pivot and we start over again. 45 00:01:51,940 --> 00:01:54,860 So the big difference here is that quicksort does the work 46 00:01:54,860 --> 00:01:57,210 before making the recursive calls. 47 00:01:57,210 --> 00:02:00,140 Whereas most of merge sorts work is emerging 48 00:02:00,140 --> 00:02:02,003 after the elements have been split. 49 00:02:03,550 --> 00:02:04,820 You can think of quicksort 50 00:02:04,820 --> 00:02:07,370 as a series of successive refinements. 51 00:02:07,370 --> 00:02:10,410 First we segregate elements into two partitions, 52 00:02:10,410 --> 00:02:12,220 on one side values that are less than 53 00:02:12,220 --> 00:02:13,940 the pivot and on the other values that 54 00:02:13,940 --> 00:02:16,580 are greater than or equal to that of the pivot. 55 00:02:16,580 --> 00:02:18,130 And then we make the recursive calls 56 00:02:18,130 --> 00:02:19,320 on these two partitions, 57 00:02:19,320 --> 00:02:22,200 on these two portions of our vector, 58 00:02:22,200 --> 00:02:24,073 refining them further each time. 59 00:02:26,040 --> 00:02:29,200 Now I know we visited visualgo.net 60 00:02:29,200 --> 00:02:31,136 and I encourage you to do so please. 61 00:02:31,136 --> 00:02:33,120 But I also like this animation. 62 00:02:33,120 --> 00:02:35,150 This is from Wikipedia 63 00:02:37,180 --> 00:02:41,070 and it shows now we're spanning the entire vector 64 00:02:41,070 --> 00:02:46,070 and where the red bar indicates the pivot. 65 00:02:46,930 --> 00:02:49,760 And we're putting all of the elements 66 00:02:49,760 --> 00:02:53,440 that are smaller than the pivot to the left-hand side 67 00:02:53,440 --> 00:02:56,610 and all of the elements that are larger than 68 00:02:56,610 --> 00:02:59,763 or equal to that of the pivot on the right-hand side. 69 00:03:00,950 --> 00:03:02,090 And you'll see as it goes 70 00:03:02,090 --> 00:03:07,090 through the process that it successively refines the sort. 71 00:03:10,130 --> 00:03:11,893 Let that go one more time. 72 00:03:14,240 --> 00:03:15,940 Now we're working on the left half 73 00:03:17,088 --> 00:03:18,680 or the left side I should say 74 00:03:19,720 --> 00:03:23,640 left side of the left side and right side of the left side. 75 00:03:24,610 --> 00:03:25,770 See how these, 76 00:03:25,770 --> 00:03:29,373 the gray bar indicates the span that we're working with. 77 00:03:34,990 --> 00:03:36,237 And that's quicksort. 78 00:03:38,450 --> 00:03:39,870 So this is the basic idea, 79 00:03:39,870 --> 00:03:43,330 but there are lots of implementation details to consider. 80 00:03:43,330 --> 00:03:45,490 But let's look at more detailed pseudocode 81 00:03:45,490 --> 00:03:48,093 and then work through some small problem instances. 82 00:03:49,470 --> 00:03:51,730 Here's some more detailed pseudocode. 83 00:03:51,730 --> 00:03:54,240 You'll see we have the quicksort function itself 84 00:03:54,240 --> 00:03:56,260 and a separate function called by quicksort 85 00:03:56,260 --> 00:03:57,423 to do the partitioning. 86 00:03:58,870 --> 00:04:00,200 Quicksort calls partition 87 00:04:00,200 --> 00:04:02,100 and partition returns and integer, 88 00:04:02,100 --> 00:04:03,730 which is an index that indicates 89 00:04:03,730 --> 00:04:05,690 how the vector has been partitioned. 90 00:04:05,690 --> 00:04:07,543 That's p the pseudocode here. 91 00:04:08,958 --> 00:04:11,370 Quicksort makes two recursive calls, 92 00:04:11,370 --> 00:04:13,520 one passing in the portion of the vector 93 00:04:13,520 --> 00:04:15,680 to the left of what's index by p 94 00:04:15,680 --> 00:04:18,000 and another passing in the portion of the vector 95 00:04:18,000 --> 00:04:20,150 that's to the right of p. 96 00:04:20,150 --> 00:04:23,050 Most of the work is done in that partitioning function. 97 00:04:23,050 --> 00:04:23,883 Here. 98 00:04:26,890 --> 00:04:29,920 Let's see what happens now in that partition function. 99 00:04:29,920 --> 00:04:32,530 If the partition function receives one element 100 00:04:32,530 --> 00:04:34,700 then nothing has changed. 101 00:04:34,700 --> 00:04:36,340 So let's look at a case where 102 00:04:36,340 --> 00:04:39,083 the partition function receives two elements. 103 00:04:40,910 --> 00:04:43,290 Here the elements are in order. 104 00:04:43,290 --> 00:04:45,400 And here we choose the pivot to be the element 105 00:04:45,400 --> 00:04:46,713 at the end of the vector. 106 00:04:47,800 --> 00:04:50,433 We set i to the start and begin the loop. 107 00:04:51,520 --> 00:04:53,350 Here so i equals start 108 00:04:53,350 --> 00:04:56,373 and here's our loop for j from start to end. 109 00:04:58,830 --> 00:04:59,870 So here, 110 00:04:59,870 --> 00:05:03,220 the value at position j now five 111 00:05:03,220 --> 00:05:04,810 is less than that of the pivot 112 00:05:04,810 --> 00:05:08,290 so we swap the elements of positions i and j. 113 00:05:08,290 --> 00:05:09,560 But i and j are the same. 114 00:05:09,560 --> 00:05:13,230 So we're swapping five with itself and there's no change. 115 00:05:13,230 --> 00:05:14,653 Now we increment i, 116 00:05:16,660 --> 00:05:18,700 and we continue to loop. 117 00:05:18,700 --> 00:05:21,670 Nine is not less than nine so we do nothing 118 00:05:21,670 --> 00:05:23,103 and the loop terminates. 119 00:05:24,040 --> 00:05:25,440 As a last step, 120 00:05:25,440 --> 00:05:29,030 you'll see here we swap the elements of position 121 00:05:29,030 --> 00:05:31,070 i and the end. 122 00:05:31,070 --> 00:05:32,970 Again these are the same in this case 123 00:05:32,970 --> 00:05:35,170 so we swap nine with nine. 124 00:05:35,170 --> 00:05:38,030 And you see if we pass in a two element vector 125 00:05:38,030 --> 00:05:39,390 with the elements in order 126 00:05:39,390 --> 00:05:42,510 their order is preserved by the partition function. 127 00:05:42,510 --> 00:05:45,740 Now let's look at a case where they're out of order. 128 00:05:45,740 --> 00:05:47,940 We've initialized as before, 129 00:05:47,940 --> 00:05:50,310 but now five is the pivot. 130 00:05:50,310 --> 00:05:53,523 And we begin this loop for j from start to end. 131 00:05:54,710 --> 00:05:57,010 Now nine is not less than five 132 00:05:57,010 --> 00:06:00,130 so we don't swap and we don't increment i, 133 00:06:00,130 --> 00:06:03,010 we just continue with that loop incrementing j. 134 00:06:03,010 --> 00:06:07,470 So we move to the next j now five is not less than five. 135 00:06:07,470 --> 00:06:09,620 So again we do nothing. 136 00:06:09,620 --> 00:06:13,240 And now the last step calls for us to swap the elements 137 00:06:13,240 --> 00:06:16,383 of position i and the ending position. 138 00:06:18,870 --> 00:06:20,290 So if we swap, 139 00:06:20,290 --> 00:06:23,130 now our elements are in the correct order. 140 00:06:23,130 --> 00:06:26,360 So we've seen in the case of two element factors 141 00:06:26,360 --> 00:06:28,910 that everything works as we'd want it to. 142 00:06:28,910 --> 00:06:30,500 If the elements are out of order, 143 00:06:30,500 --> 00:06:32,020 they're put into order. 144 00:06:32,020 --> 00:06:34,000 And if the elements are already in order, 145 00:06:34,000 --> 00:06:35,600 we leave them as is. 146 00:06:35,600 --> 00:06:37,890 That might not be an earth shattering result 147 00:06:37,890 --> 00:06:39,500 but let's see what happens when we look at 148 00:06:39,500 --> 00:06:40,723 a little bigger example. 149 00:06:42,730 --> 00:06:45,330 Here we have a vector of four elements. 150 00:06:45,330 --> 00:06:47,763 Six, three, eight, and four. 151 00:06:48,650 --> 00:06:50,990 Initializing as before we take the value 152 00:06:50,990 --> 00:06:53,260 of the element at the end to be the pivot. 153 00:06:53,260 --> 00:06:54,113 That's four, 154 00:06:55,120 --> 00:06:58,490 we initialize i and j and we begin our four loop. 155 00:06:58,490 --> 00:07:00,330 That's the four loop here. 156 00:07:00,330 --> 00:07:04,320 And so for the first step of six is not less than four. 157 00:07:04,320 --> 00:07:07,170 So we don't swap and we don't increment i, 158 00:07:07,170 --> 00:07:08,893 we just move on to the next j. 159 00:07:10,700 --> 00:07:11,610 Now here, 160 00:07:11,610 --> 00:07:15,970 the value at the position j is less than that of the pivot. 161 00:07:15,970 --> 00:07:20,970 And so we swap elements i and j and we increment i. 162 00:07:24,990 --> 00:07:27,450 Now we move on to the next j. 163 00:07:27,450 --> 00:07:29,870 Here eight is not less than four 164 00:07:29,870 --> 00:07:31,093 and so we do nothing. 165 00:07:33,510 --> 00:07:35,150 And we increment j and then 166 00:07:35,150 --> 00:07:37,630 at the next step four is not less than four. 167 00:07:37,630 --> 00:07:39,810 So again we do nothing. 168 00:07:39,810 --> 00:07:43,400 So now we've finished this loop. 169 00:07:43,400 --> 00:07:48,400 So we're going to exit that loop and then execute this swap. 170 00:07:48,730 --> 00:07:52,890 So we swap the values of four and six 171 00:07:53,810 --> 00:07:56,980 and now you'll notice that all the values 172 00:07:56,980 --> 00:07:59,333 to the left of four are smaller than four. 173 00:08:00,460 --> 00:08:02,080 And all the values to the right 174 00:08:02,080 --> 00:08:04,210 of four are greater than or equal to four 175 00:08:04,210 --> 00:08:05,823 and our partition is complete. 176 00:08:07,360 --> 00:08:08,260 Now wait a minute, 177 00:08:08,260 --> 00:08:10,130 you say these aren't completely sorted. 178 00:08:10,130 --> 00:08:13,429 And you're right but let's see what happens next. 179 00:08:13,429 --> 00:08:17,660 This value of i is returned to quicksort. 180 00:08:17,660 --> 00:08:20,693 It'll be one in this case cause we're zero indexed. 181 00:08:22,710 --> 00:08:26,350 And so now p equals one and we call quicksort again, 182 00:08:26,350 --> 00:08:28,080 first on the portion of the vector 183 00:08:28,080 --> 00:08:31,100 to the left of p that's this three here, 184 00:08:31,100 --> 00:08:32,820 and then on the portion of the vector 185 00:08:32,820 --> 00:08:35,990 to the right of p that's the six. 186 00:08:35,990 --> 00:08:38,220 And the first recursive call we'll get 187 00:08:38,220 --> 00:08:40,390 a single element three and that's already sorted 188 00:08:40,390 --> 00:08:43,000 that's our base case so nothing changes. 189 00:08:43,000 --> 00:08:46,340 And for the portion on the right, we've already seen that 190 00:08:46,340 --> 00:08:49,780 if we pass a two element vector to the partition function 191 00:08:49,780 --> 00:08:52,560 that the elements will be placed in the correct order. 192 00:08:52,560 --> 00:08:54,850 So after those two calls have been made 193 00:08:54,850 --> 00:08:57,053 our vector will be completely sorted. 194 00:08:59,360 --> 00:09:02,400 So no matter how large the original input vector is 195 00:09:02,400 --> 00:09:06,060 we'll always work our way down to small cases like this. 196 00:09:06,060 --> 00:09:08,170 At each smaller partition, 197 00:09:08,170 --> 00:09:10,260 we refine the order of the elements 198 00:09:10,260 --> 00:09:13,400 and ultimately this produces a sorted vector. 199 00:09:13,400 --> 00:09:14,233 Now, 200 00:09:14,233 --> 00:09:16,070 quicksort has many different implementations 201 00:09:16,070 --> 00:09:18,450 and performance varies significantly 202 00:09:18,450 --> 00:09:21,050 with the implementation. 203 00:09:21,050 --> 00:09:23,260 So what are these implementation issues 204 00:09:23,260 --> 00:09:26,280 and why does performance vary? 205 00:09:26,280 --> 00:09:28,870 Well how do we choose a pivot or the divider? 206 00:09:28,870 --> 00:09:30,010 There are many schemes, 207 00:09:30,010 --> 00:09:32,163 and we'll look at one of those later on. 208 00:09:33,001 --> 00:09:35,720 Quicksort also doesn't do well on sorted lists 209 00:09:35,720 --> 00:09:37,800 or when there are many repeated values 210 00:09:37,800 --> 00:09:38,810 and quicksort can have 211 00:09:38,810 --> 00:09:41,067 a worst-case complexity of O(n squared). 212 00:09:43,110 --> 00:09:44,330 In the best cases, 213 00:09:44,330 --> 00:09:45,536 with a good implementation, 214 00:09:45,536 --> 00:09:48,213 quicksort is faster than merge sort. 215 00:09:48,213 --> 00:09:50,110 And there's another algorithm 216 00:09:50,110 --> 00:09:52,580 we'll see a little later called heap sort. 217 00:09:52,580 --> 00:09:55,053 Quicksort also generally outperforms heap sort. 218 00:09:55,900 --> 00:09:59,070 And sometimes it's implemented in a hybrid form 219 00:09:59,070 --> 00:10:02,130 with insertion sort used when the sub-problems become small. 220 00:10:02,130 --> 00:10:05,393 We'll also touch on that a little later in the video. 221 00:10:06,810 --> 00:10:08,200 But let's see why quicksort 222 00:10:08,200 --> 00:10:10,570 doesn't do well with sorted lists. 223 00:10:10,570 --> 00:10:13,313 First let's take a step back and look at merge sort. 224 00:10:14,240 --> 00:10:17,456 This is sort of a schematic of what goes on on merge sort 225 00:10:17,456 --> 00:10:21,890 at least in the portion where we're dividing our vector 226 00:10:21,890 --> 00:10:25,290 into single element sub vectors. 227 00:10:25,290 --> 00:10:27,240 Here we have 16 elements, 228 00:10:27,240 --> 00:10:29,690 and we divide these into individual elements 229 00:10:29,690 --> 00:10:30,960 in only four steps. 230 00:10:30,960 --> 00:10:32,550 So if we divide by half, 231 00:10:32,550 --> 00:10:33,830 this is our input factor. 232 00:10:33,830 --> 00:10:38,830 We divide by half, once, twice, three times, four times. 233 00:10:38,990 --> 00:10:42,390 And notice we have 16 elements 234 00:10:42,390 --> 00:10:47,390 and four divisions to get to one element sub vectors 235 00:10:48,350 --> 00:10:49,650 it should come as no surprise 236 00:10:49,650 --> 00:10:52,350 that log base two of 16 is four 237 00:10:52,350 --> 00:10:55,100 and hence the maximum number of recursion depth is log (n). 238 00:10:55,100 --> 00:10:56,440 That makes sense. 239 00:10:56,440 --> 00:10:58,413 That's what we've seen in merge sort. 240 00:10:59,730 --> 00:11:02,160 And in the case of quicksort 241 00:11:02,160 --> 00:11:05,580 we divide elements with respect to some pivot element. 242 00:11:05,580 --> 00:11:09,890 Now, if we were to choose the median value each time, 243 00:11:09,890 --> 00:11:11,990 we'd have something similar to merge sort. 244 00:11:11,990 --> 00:11:15,260 A recursion depth of roughly log (n) 245 00:11:15,260 --> 00:11:18,290 Now, in many cases the depth may be a little more, 246 00:11:18,290 --> 00:11:19,403 but not much more. 247 00:11:20,400 --> 00:11:24,457 But what happens if we pass a sorted list to quicksort? 248 00:11:25,300 --> 00:11:27,080 Well, things go wrong. 249 00:11:27,080 --> 00:11:29,198 If we pass a sorted list to quicksort 250 00:11:29,198 --> 00:11:31,610 and our algorithm always chooses, 251 00:11:31,610 --> 00:11:34,950 say the left most element and the vector to serve as a pivot 252 00:11:34,950 --> 00:11:37,330 then we'd have a recursion depths of n. 253 00:11:37,330 --> 00:11:39,022 You see what's happening here. 254 00:11:39,022 --> 00:11:41,420 We're going to partition everything 255 00:11:41,420 --> 00:11:44,160 that's less than a to the left-hand side 256 00:11:44,160 --> 00:11:46,780 and everything that's greater than or equal to a 257 00:11:46,780 --> 00:11:48,203 to the right-hand side. 258 00:11:49,686 --> 00:11:53,693 And so we partition only one element at each step. 259 00:11:54,770 --> 00:11:59,490 And so to break our problem down here in 260 00:12:01,040 --> 00:12:05,080 we have 16 elements here to break the problem 261 00:12:05,080 --> 00:12:10,080 down into 16 individual single element factors, 262 00:12:10,560 --> 00:12:14,920 we'd have a recursion depth of n not log (n) but n. 263 00:12:14,920 --> 00:12:16,253 That's a big difference. 264 00:12:17,660 --> 00:12:19,110 So in the worst case, 265 00:12:19,110 --> 00:12:22,100 this would take O(n squared) time 266 00:12:22,100 --> 00:12:24,370 because we have n elements to process 267 00:12:24,370 --> 00:12:25,840 and a recursion depth of n. 268 00:12:25,840 --> 00:12:27,483 N times n is n squared. 269 00:12:28,500 --> 00:12:30,310 And if the problem instance were big enough 270 00:12:30,310 --> 00:12:32,370 we could even overflow the call stack. 271 00:12:32,370 --> 00:12:35,653 We could cause a crash. 272 00:12:36,490 --> 00:12:40,110 So while picking one end or the other of our vector to serve 273 00:12:40,110 --> 00:12:43,060 as a pivot might do well with unsorted data, 274 00:12:43,060 --> 00:12:47,070 it can perform horribly with sorted or partly sorted data 275 00:12:47,070 --> 00:12:50,020 or data that have a large number of repeated values. 276 00:12:50,020 --> 00:12:51,700 Now notice that the same thing would happen 277 00:12:51,700 --> 00:12:54,790 if we were to choose the right most element as the pivot 278 00:12:54,790 --> 00:12:56,853 it's just that we would have, 279 00:12:56,853 --> 00:12:58,620 we'd be splitting off elements 280 00:12:58,620 --> 00:13:01,170 from this side rather than this side 281 00:13:02,238 --> 00:13:03,250 but the result is the same, 282 00:13:03,250 --> 00:13:05,083 o events squared and that's yucky. 283 00:13:07,490 --> 00:13:10,266 So how do we choose a pivot? 284 00:13:10,266 --> 00:13:12,930 Well, we've seen that we can choose the element 285 00:13:12,930 --> 00:13:14,910 from one end or the other of the vector 286 00:13:14,910 --> 00:13:16,830 and that works pretty well in most cases 287 00:13:16,830 --> 00:13:19,030 and it's super easy in the implementation 288 00:13:19,030 --> 00:13:22,648 but the downside is it can really perform horribly 289 00:13:22,648 --> 00:13:26,110 if we pass a sorted already sorted list 290 00:13:26,110 --> 00:13:29,120 or a partially sorted list to the algorithm, 291 00:13:29,120 --> 00:13:29,953 it get bad. 292 00:13:30,830 --> 00:13:32,580 And we could pick at random, 293 00:13:32,580 --> 00:13:34,640 and that would work pretty well on most cases, 294 00:13:34,640 --> 00:13:37,050 it's unlikely that we would choose the minimum 295 00:13:37,050 --> 00:13:40,240 or the maximum value and run into these problems 296 00:13:40,240 --> 00:13:43,660 with this long linear chain of recursion calls. 297 00:13:43,660 --> 00:13:46,040 But then there's the overhead of choosing it random. 298 00:13:46,040 --> 00:13:49,520 After you have to pick a random number each time 299 00:13:50,610 --> 00:13:51,960 and that that gets costly. 300 00:13:51,960 --> 00:13:54,720 So that's really not worth the trouble. 301 00:13:54,720 --> 00:13:55,830 Then there's this technique 302 00:13:55,830 --> 00:13:57,560 that's called median-of-three. 303 00:13:57,560 --> 00:14:00,940 Median-of-three is simply if we have three values 304 00:14:00,940 --> 00:14:02,440 we pick the one in the middle, 305 00:14:03,600 --> 00:14:05,640 and that works pretty well in most cases 306 00:14:05,640 --> 00:14:07,170 and it's not too costly. 307 00:14:07,170 --> 00:14:09,290 And it really reduces the likelihood 308 00:14:09,290 --> 00:14:12,130 of this worst case performance that we've seen. 309 00:14:12,130 --> 00:14:14,140 The downside is we have a little overhead 310 00:14:14,140 --> 00:14:16,020 we have to do three extra comparisons 311 00:14:16,020 --> 00:14:18,210 and up to three extra swaps, 312 00:14:18,210 --> 00:14:20,420 but that's a small price to pay 313 00:14:20,420 --> 00:14:23,610 to avoid this O(n squared) performance. 314 00:14:23,610 --> 00:14:26,543 So let's look at what median-of-three does. 315 00:14:27,720 --> 00:14:31,140 Given some vector V and start and end indices, 316 00:14:31,140 --> 00:14:32,450 we can calculate the middle. 317 00:14:32,450 --> 00:14:34,748 We've done this before with a merge sort 318 00:14:34,748 --> 00:14:38,090 where we take start plus end and divide by two. 319 00:14:38,090 --> 00:14:39,610 And that's integer division. 320 00:14:39,610 --> 00:14:42,173 So it'll truncate if we have an odd number. 321 00:14:43,090 --> 00:14:46,050 And then if the element indexed by middle is less 322 00:14:46,050 --> 00:14:49,630 than the element index by start we swap those two. 323 00:14:49,630 --> 00:14:52,260 Then if the element index by end is less 324 00:14:52,260 --> 00:14:55,473 than the element index by start we swap those two. 325 00:14:56,610 --> 00:14:59,720 And if the element index by the middle is less 326 00:14:59,720 --> 00:15:03,030 than the element index by the end we swap those two. 327 00:15:03,030 --> 00:15:05,460 And then we let the pivot be the element that's now 328 00:15:05,460 --> 00:15:06,573 at the end position. 329 00:15:07,940 --> 00:15:10,030 Let's see how that works in practice. 330 00:15:10,030 --> 00:15:13,570 We'll go back to our playing cards here 331 00:15:13,570 --> 00:15:14,820 for this demonstration. 332 00:15:14,820 --> 00:15:17,370 Here's median of three at work. 333 00:15:17,370 --> 00:15:19,020 Let's say we have these cards, 334 00:15:19,020 --> 00:15:22,770 and we're gonna run the median of three algorithm. 335 00:15:22,770 --> 00:15:25,010 Well, the first thing we're going to do is we're 336 00:15:25,010 --> 00:15:27,420 gonna compare the middle and start elements. 337 00:15:27,420 --> 00:15:29,200 If the middle element is less 338 00:15:29,200 --> 00:15:31,300 than the start element, then we swap. 339 00:15:31,300 --> 00:15:33,903 So here we're going to swap six and 10. 340 00:15:36,210 --> 00:15:38,533 That's one comparison and one swap. 341 00:15:40,550 --> 00:15:41,870 Now we compare the element 342 00:15:41,870 --> 00:15:44,250 at the start position with the one at the end. 343 00:15:44,250 --> 00:15:45,790 If the one at the end is less 344 00:15:45,790 --> 00:15:47,773 than the one at the start we swap. 345 00:15:49,260 --> 00:15:52,513 So now we've made two comparisons and two swaps. 346 00:15:54,160 --> 00:15:56,450 Finally, we compare the middle element 347 00:15:56,450 --> 00:15:58,070 and the one at the end. 348 00:15:58,070 --> 00:16:00,750 If the middle element is less than the one at the end 349 00:16:00,750 --> 00:16:02,560 and we swap middle and end. 350 00:16:02,560 --> 00:16:04,460 Here 10 is greater than six. 351 00:16:04,460 --> 00:16:05,593 So we don't swap. 352 00:16:08,090 --> 00:16:11,310 And so that's three comparisons and two swaps. 353 00:16:11,310 --> 00:16:15,810 And the one left at the end position becomes our pivot. 354 00:16:15,810 --> 00:16:16,810 So that's our pivot. 355 00:16:16,810 --> 00:16:17,643 And you'll notice 356 00:16:17,643 --> 00:16:21,303 that that's the median of four, 10, and six. 357 00:16:22,950 --> 00:16:25,930 Now this doesn't guarantee that you'll find the median 358 00:16:25,930 --> 00:16:28,110 of all the values of the cards, 359 00:16:28,110 --> 00:16:30,450 just the median of the three that we chose. 360 00:16:30,450 --> 00:16:32,470 But it is a quick way to make sure that you're 361 00:16:32,470 --> 00:16:35,513 not picking the largest or smallest valued element. 362 00:16:36,410 --> 00:16:39,130 So this simple technique reduces the likelihood 363 00:16:39,130 --> 00:16:42,540 of choosing a really bad pivot and driving your performance 364 00:16:42,540 --> 00:16:45,470 toward that OFN square worst case. 365 00:16:45,470 --> 00:16:47,510 We'll include this in the next video 366 00:16:47,510 --> 00:16:50,508 when we implement quicksort in C++ we'll see, 367 00:16:50,508 --> 00:16:54,010 we'll compare our version that uses median 368 00:16:54,010 --> 00:16:55,773 of three in a version that doesn't. 369 00:16:57,620 --> 00:16:59,823 So what is quicksorts complexity? 370 00:17:01,010 --> 00:17:05,320 Well, the partition function must process O(n) elements 371 00:17:05,320 --> 00:17:08,280 and the recursion depth is typically O(log n), 372 00:17:08,280 --> 00:17:11,005 hence we have O(n log n) 373 00:17:11,005 --> 00:17:14,190 And that's the best case and the average case. 374 00:17:14,190 --> 00:17:16,810 So what is quicksorts complexity? 375 00:17:16,810 --> 00:17:20,750 The partition function must process O(n) elements. 376 00:17:20,750 --> 00:17:24,059 And the recursion depth is typically O(log n), 377 00:17:24,059 --> 00:17:24,903 hence we have O(n log n). 378 00:17:25,900 --> 00:17:28,223 This is the best case and the average case. 379 00:17:29,070 --> 00:17:31,160 The worst case is as we have seen 380 00:17:31,160 --> 00:17:33,210 when we have a linear chain of partitions 381 00:17:33,210 --> 00:17:34,763 and a recursion depth of O (n). 382 00:17:35,971 --> 00:17:40,240 Again the partition function has to process O(n) elements 383 00:17:40,240 --> 00:17:42,393 and so we have n times n that's n square. 384 00:17:44,250 --> 00:17:46,520 However we can avoid worst case performance 385 00:17:46,520 --> 00:17:49,270 in many situations by choosing our pivot well. 386 00:17:49,270 --> 00:17:51,020 This is why many implementations 387 00:17:51,020 --> 00:17:53,310 of quicksort use the median-of-three approach, 388 00:17:53,310 --> 00:17:54,443 or something similar. 389 00:17:57,070 --> 00:17:58,630 Now what about stability. 390 00:17:58,630 --> 00:18:00,000 Is quicksort stable? 391 00:18:00,000 --> 00:18:01,523 The answer here is maybe. 392 00:18:02,390 --> 00:18:04,380 In its original form and in the form 393 00:18:04,380 --> 00:18:06,860 I've shown you quicksort does not 394 00:18:06,860 --> 00:18:08,390 preserve the relative border 395 00:18:08,390 --> 00:18:10,070 of equal values in the input factor. 396 00:18:10,070 --> 00:18:12,850 So what I've shown you is not stable. 397 00:18:12,850 --> 00:18:16,000 It can however be implemented in a stable form 398 00:18:16,000 --> 00:18:17,670 although this takes more space. 399 00:18:17,670 --> 00:18:20,791 So if we're willing to use a little more working space 400 00:18:20,791 --> 00:18:25,140 we can implement a stable version of quicksort. 401 00:18:25,140 --> 00:18:26,480 But again, what I've shown you here 402 00:18:26,480 --> 00:18:28,390 in this video is not stable. 403 00:18:28,390 --> 00:18:30,210 We will demonstrate an implementation 404 00:18:30,210 --> 00:18:32,293 of stable version in a later video. 405 00:18:34,970 --> 00:18:38,840 Now let's get back to this hybridization 406 00:18:38,840 --> 00:18:41,670 that I mentioned in an earlier slide. 407 00:18:41,670 --> 00:18:44,110 It's not uncommon that quicksort is hybridized 408 00:18:44,110 --> 00:18:45,520 with another algorithm, 409 00:18:45,520 --> 00:18:46,973 typically insertion sort. 410 00:18:47,820 --> 00:18:49,230 And you may have noticed that when we have 411 00:18:49,230 --> 00:18:53,460 small vectors that we've seen swapping an element 412 00:18:53,460 --> 00:18:55,540 with itself is not uncommon 413 00:18:55,540 --> 00:18:56,940 and that's kind of wasteful. 414 00:18:57,950 --> 00:19:00,810 And insertion sort performs well 415 00:19:00,810 --> 00:19:02,940 with partially sorted lists. 416 00:19:02,940 --> 00:19:05,940 So we're likely in small vectors 417 00:19:05,940 --> 00:19:09,870 with quicksort to have partially sorted lists. 418 00:19:09,870 --> 00:19:13,730 So we use insertion sort for vectors below a certain size, 419 00:19:13,730 --> 00:19:15,820 say around 10 elements. 420 00:19:15,820 --> 00:19:19,830 We use quicksort in the main for larger problem instances. 421 00:19:19,830 --> 00:19:22,143 But when we get below a certain size 422 00:19:22,143 --> 00:19:25,040 we switched to insertion sort. 423 00:19:25,040 --> 00:19:29,150 And that gives quick sort of modest speed up in many cases. 424 00:19:29,150 --> 00:19:31,370 Now let's go back to that comparison chart 425 00:19:31,370 --> 00:19:32,990 that we've been looking at. 426 00:19:32,990 --> 00:19:36,427 You can see here that quicksort has a time complexity 427 00:19:36,427 --> 00:19:40,830 of O(n log n) that's what we've seen so far. 428 00:19:40,830 --> 00:19:43,880 It has a space complexity of O(1). 429 00:19:43,880 --> 00:19:45,520 So it's space complexity is less 430 00:19:45,520 --> 00:19:49,493 than that of merge sort and it's not stable. 431 00:19:50,450 --> 00:19:53,070 We'll see in a later video 432 00:19:53,070 --> 00:19:56,040 how we can implement a stable version of quicksort 433 00:19:56,040 --> 00:20:00,348 which also has O(n log n) complexity time complexity 434 00:20:00,348 --> 00:20:03,350 but has O(n) space complexity. 435 00:20:03,350 --> 00:20:04,973 And that one will be stable. 436 00:20:06,070 --> 00:20:08,910 And just to remind you here's the curve 437 00:20:08,910 --> 00:20:12,100 for O(n log n) and you see 438 00:20:12,100 --> 00:20:14,220 that that grows much more slowly 439 00:20:14,220 --> 00:20:15,907 than the curve for O (n squared). 440 00:20:17,100 --> 00:20:21,073 So O(n log n) is much faster than O(n squared). 441 00:20:22,440 --> 00:20:23,500 So in summary, 442 00:20:23,500 --> 00:20:26,683 quicksort is a recursive divide-and-conquer algorithm. 443 00:20:27,710 --> 00:20:30,743 It has O(n log n) time complexity. 444 00:20:31,630 --> 00:20:35,210 In the unstable implementation that we've seen here. 445 00:20:35,210 --> 00:20:37,860 We have O(1) space complexity 446 00:20:39,930 --> 00:20:41,850 and in its original design, 447 00:20:41,850 --> 00:20:43,680 it's not stable but if we willing 448 00:20:43,680 --> 00:20:45,480 to increase the space complexity 449 00:20:45,480 --> 00:20:48,970 to O(n) it can be implemented as a stable algorithm. 450 00:20:48,970 --> 00:20:51,600 And we'll see that in a later video. 451 00:20:51,600 --> 00:20:52,480 That's all for now. 452 00:20:52,480 --> 00:20:53,313 Thanks.