Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,598 --> 00:00:03,181 (upbeat music) 2 2 00:00:05,270 --> 00:00:08,630 Okay so let's implement the quick sort algorithm 3 3 00:00:08,630 --> 00:00:11,370 using the implementation we went through on the slides. 4 4 00:00:11,370 --> 00:00:14,700 We're going to code two methods, one called quick sort 5 5 00:00:14,700 --> 00:00:16,850 and one called partition. 6 6 00:00:16,850 --> 00:00:20,420 So let's start with the quick sort method first. 7 7 00:00:20,420 --> 00:00:24,487 So we'll say public static void, quick sort 8 8 00:00:24,487 --> 00:00:27,840 and we're gonna pass the array we wanna sort, 9 9 00:00:27,840 --> 00:00:32,840 the start index, and the end index. 10 10 00:00:33,340 --> 00:00:36,010 And as we saw on the slides, the end index 11 11 00:00:36,010 --> 00:00:41,010 will be one greater than the last valid index in the array. 12 12 00:00:41,530 --> 00:00:45,170 So the first thing we're gonna do is check whether 13 13 00:00:45,170 --> 00:00:48,490 end minus start is less than two. 14 14 00:00:48,490 --> 00:00:50,760 Because if end minus start is less than two, 15 15 00:00:50,760 --> 00:00:53,180 we're dealing with a one element array, 16 16 00:00:53,180 --> 00:00:56,840 so we don't have to do anything, we just return. 17 17 00:00:56,840 --> 00:00:59,080 If we're dealing with more than one element 18 18 00:00:59,080 --> 00:01:03,370 than what we want to do is figure out where the pivot 19 19 00:01:03,370 --> 00:01:05,730 will belong in the sorted array. 20 20 00:01:05,730 --> 00:01:09,810 In other words, what will be the index of the pivot 21 21 00:01:09,810 --> 00:01:13,360 when the array is sorted, what is it's sorted position 22 22 00:01:13,360 --> 00:01:16,860 and so we're gonna say int pivot index equals 23 23 00:01:16,860 --> 00:01:19,193 and we're gonna partition this array. 24 24 00:01:20,630 --> 00:01:22,800 And we'll write the partition method in a minute. 25 25 00:01:22,800 --> 00:01:26,670 So what this will return is the position 26 26 00:01:26,670 --> 00:01:29,250 of the element in the sorted array, 27 27 00:01:29,250 --> 00:01:30,870 so it's corrected sorted position. 28 28 00:01:30,870 --> 00:01:34,150 So in the slides we had 20 as the pivot 29 29 00:01:34,150 --> 00:01:37,610 and eventually the pivot ended up in position four 30 30 00:01:37,610 --> 00:01:39,950 and so what this would return is four, 31 31 00:01:39,950 --> 00:01:42,310 so it's basically returning the position 32 32 00:01:42,310 --> 00:01:46,240 at the pivot and at that position everything to the left 33 33 00:01:46,240 --> 00:01:48,040 of the pivot will be smaller than the pivot 34 34 00:01:48,040 --> 00:01:50,350 and everything to the right will be larger. 35 35 00:01:50,350 --> 00:01:54,840 And after that, we want to do the same thing 36 36 00:01:54,840 --> 00:01:57,660 with the left array and the right array. 37 37 00:01:57,660 --> 00:02:00,090 So all the elements that are smaller than the pivot 38 38 00:02:00,090 --> 00:02:01,980 and all the elements that are larger than the pivot. 39 39 00:02:01,980 --> 00:02:03,530 So we're gonna call quick sort, 40 40 00:02:04,430 --> 00:02:09,040 with start as the start index and the pivot index 41 41 00:02:09,040 --> 00:02:13,510 as the end and then we're gonna call a quick sort 42 42 00:02:13,510 --> 00:02:18,400 with the same input away, pivot index plus one 43 43 00:02:18,400 --> 00:02:21,770 as the start index and end as the end index. 44 44 00:02:21,770 --> 00:02:25,070 So what we're saying here is in this step, 45 45 00:02:25,070 --> 00:02:28,610 we have put the pivot into it's correct sorted position 46 46 00:02:28,610 --> 00:02:32,130 and we have repositioned the elements such as everything 47 47 00:02:32,130 --> 00:02:34,250 to the left of the pivot is smaller than the pivot 48 48 00:02:34,250 --> 00:02:36,230 and everything to the right of the pivot is greater 49 49 00:02:36,230 --> 00:02:40,330 than the pivot and then we wanna do the quick sort the left 50 50 00:02:40,330 --> 00:02:43,670 sub-array and we wanna quick sort the right sub-array. 51 51 00:02:43,670 --> 00:02:47,010 And once we've done that, the entire array will be sorted. 52 52 00:02:47,010 --> 00:02:49,410 Now of course these are recursive calls, 53 53 00:02:49,410 --> 00:02:53,370 so what actually happens is when we call this quick sort 54 54 00:02:53,370 --> 00:02:55,520 it will deal with the left sub-array 55 55 00:02:55,520 --> 00:02:57,830 but then it's going to make a recursive call 56 56 00:02:57,830 --> 00:03:01,250 to then deal with the left array of that sub-array, 57 57 00:03:01,250 --> 00:03:04,430 et cetera until it's completely handled, 58 58 00:03:04,430 --> 00:03:07,780 the left sub-array and then and only then, 59 59 00:03:07,780 --> 00:03:09,930 will we start working on the right sub-array. 60 60 00:03:09,930 --> 00:03:12,690 So keep in mind what happens with recursion 61 61 00:03:12,690 --> 00:03:15,860 and if you need to go back and review the video 62 62 00:03:15,860 --> 00:03:17,930 on recursive methods. 63 63 00:03:17,930 --> 00:03:20,020 Okay so let's write the partition method. 64 64 00:03:20,020 --> 00:03:23,940 So we'll say public static int, this is going to return 65 65 00:03:23,940 --> 00:03:26,410 the correct position of the pivot 66 66 00:03:26,410 --> 00:03:30,190 in the sorted array, partition, we're gonna accept 67 67 00:03:30,190 --> 00:03:35,190 an input array, a start index and an end index. 68 68 00:03:37,630 --> 00:03:40,310 So I'm gonna put a note here that says this is using 69 69 00:03:40,310 --> 00:03:45,310 the first element as the pivot, as we saw in the slides. 70 70 00:03:45,570 --> 00:03:48,400 So we're gonna start out by saying that the pivot 71 71 00:03:48,400 --> 00:03:51,210 is equal to input start. 72 72 00:03:51,210 --> 00:03:55,630 Now of course this is the start element in the array 73 73 00:03:55,630 --> 00:03:57,760 or sub-array that we're passing. 74 74 00:03:57,760 --> 00:04:00,390 So it's not necessarily index zero. 75 75 00:04:00,390 --> 00:04:05,390 Later on in our example, we have put 20 here 76 76 00:04:05,530 --> 00:04:08,880 as the first pivot index and so the right sub-array 77 77 00:04:08,880 --> 00:04:12,770 would be starting at index five and so that one 78 78 00:04:12,770 --> 00:04:16,020 would actually be the pivot when we call 79 79 00:04:16,020 --> 00:04:18,730 partition with this right sub-array. 80 80 00:04:18,730 --> 00:04:20,350 And then as we did in the slides, 81 81 00:04:20,350 --> 00:04:24,347 we're gonna set I to start and we're gonna set J to end. 82 82 00:04:25,328 --> 00:04:26,800 And now we're going to do the traversal, 83 83 00:04:26,800 --> 00:04:30,340 so remember that I is going to traverse from left to right 84 84 00:04:30,340 --> 00:04:34,160 and J is going to be traversing from right to left 85 85 00:04:34,160 --> 00:04:38,150 and we want to stop when I and J cross each other. 86 86 00:04:38,150 --> 00:04:40,940 So we're gonna while I less than J 87 87 00:04:40,940 --> 00:04:44,600 because if I is greater than J, it means they have crossed. 88 88 00:04:44,600 --> 00:04:46,640 Okay, so what we're going to do in here 89 89 00:04:46,640 --> 00:04:50,410 is we're first going to use J to look for elements 90 90 00:04:50,410 --> 00:04:52,490 that are less than the pivot. 91 91 00:04:52,490 --> 00:04:55,630 So we're gonna say while I is less than J 92 92 00:04:55,630 --> 00:04:58,400 because we wanna stop if I and J cross, 93 93 00:04:58,400 --> 00:05:01,790 so if J crosses I we wanna stop 94 94 00:05:01,790 --> 00:05:06,520 and while input minus minus J 95 95 00:05:06,520 --> 00:05:09,660 is greater than equal to the pivot, 96 96 00:05:09,660 --> 00:05:11,010 that's all we wanna do. 97 97 00:05:11,010 --> 00:05:13,610 This is any empty loop, I'm gonna put a note here 98 98 00:05:13,610 --> 00:05:16,943 to say note empty loop body. 99 99 00:05:18,700 --> 00:05:22,120 And so we're not doing anything within the body of the loop 100 100 00:05:22,120 --> 00:05:26,080 so we're just basically using the loop to keep decrementing 101 101 00:05:26,080 --> 00:05:28,780 J until we either find an element that's less 102 102 00:05:28,780 --> 00:05:31,930 than the pivot or J crosses I. 103 103 00:05:31,930 --> 00:05:34,820 So what do we do when we fall out of this loop then? 104 104 00:05:34,820 --> 00:05:37,930 Well we've gotta make sure we didn't 105 105 00:05:37,930 --> 00:05:40,600 fall out of it because J crossed I. 106 106 00:05:40,600 --> 00:05:45,480 So if J hasn't crossed I, if I is still less than J, 107 107 00:05:45,480 --> 00:05:48,920 then we want to move the element at J 108 108 00:05:48,920 --> 00:05:52,060 into position I because basically we have found 109 109 00:05:52,060 --> 00:05:54,400 the first element that is less than the pivot 110 110 00:05:54,400 --> 00:05:57,050 and so we wanna move that towards the front of the array. 111 111 00:05:57,050 --> 00:06:01,960 And so we're gonna say input I equals input J. 112 112 00:06:03,990 --> 00:06:06,820 And if you're confused about this, go back and review 113 113 00:06:06,820 --> 00:06:08,420 the last video with the slides, 114 114 00:06:08,420 --> 00:06:11,010 but essentially we're saying we've used J 115 115 00:06:11,010 --> 00:06:14,260 to find the first element that is less than the pivot 116 116 00:06:14,260 --> 00:06:16,210 and we wanna put all the elements that are less 117 117 00:06:16,210 --> 00:06:18,320 than the pivot to the left of the pivot 118 118 00:06:18,320 --> 00:06:21,030 and so we're going to move that element at J, 119 119 00:06:21,030 --> 00:06:23,370 the one that we found that's smaller than the pivot, 120 120 00:06:23,370 --> 00:06:25,290 we're gonna move it to position I 121 121 00:06:25,290 --> 00:06:28,060 and on the first iteration I is actually at zero. 122 122 00:06:28,060 --> 00:06:31,530 So if you'll remember the slides, the first pivot value 123 123 00:06:31,530 --> 00:06:35,969 was 20 and we're moving backwards and we found minus 22 124 124 00:06:35,969 --> 00:06:39,150 and we moved minus 22 into position zero. 125 125 00:06:39,150 --> 00:06:42,910 Okay so now we wanna alternate and go to I. 126 126 00:06:42,910 --> 00:06:45,720 We wanna traverse the array from left to right, 127 127 00:06:45,720 --> 00:06:48,690 looking for the first element that's greater than the pivot. 128 128 00:06:48,690 --> 00:06:51,050 So we're gonna say while I is less than J, 129 129 00:06:51,050 --> 00:06:55,000 'cause once again we wanna stop if I crosses J 130 130 00:06:55,000 --> 00:07:00,000 and input plus plus I is less than or equal to the pivot 131 131 00:07:04,280 --> 00:07:06,180 and once again this is an empty loop 132 132 00:07:07,130 --> 00:07:10,303 and I'll put a note there 'cause it's easy to miss. 133 133 00:07:12,200 --> 00:07:15,450 And so this time we're gonna be moving from left to right 134 134 00:07:15,450 --> 00:07:18,640 and we're looking for a value that's greater than the pivot 135 135 00:07:18,640 --> 00:07:21,280 because when we find a value that's greater than the pivot 136 136 00:07:21,280 --> 00:07:23,500 we wanna move it to the right of the pivot. 137 137 00:07:23,500 --> 00:07:26,300 And so once again, we're gonna check when we drop out 138 138 00:07:26,300 --> 00:07:28,670 of the loop whether we've dropped out because I 139 139 00:07:28,670 --> 00:07:31,070 has crossed J and if that's not the case 140 140 00:07:31,070 --> 00:07:33,330 then we've dropped out because we found an element 141 141 00:07:33,330 --> 00:07:34,207 that's greater than the pivot 142 142 00:07:34,207 --> 00:07:37,120 and so we wanna move it to position J. 143 143 00:07:37,120 --> 00:07:42,120 Input J equals input I and it's okay to do that, 144 144 00:07:43,040 --> 00:07:45,120 we're not gonna be losing any data 145 145 00:07:45,120 --> 00:07:47,840 because in the previous loop, we've already moved 146 146 00:07:47,840 --> 00:07:50,310 what was at input J and so at this point, 147 147 00:07:50,310 --> 00:07:53,830 it's safe to assign to input I and in the next iteration 148 148 00:07:53,830 --> 00:07:56,480 of this loop it's safe to overwrite input I 149 149 00:07:56,480 --> 00:07:57,980 because we've already moved it. 150 150 00:07:57,980 --> 00:07:59,570 So it's the fact that we're alternating 151 151 00:07:59,570 --> 00:08:02,930 between I and J and which direction we're traversing in 152 152 00:08:02,930 --> 00:08:05,250 that lets us do these types of assignments 153 153 00:08:05,250 --> 00:08:06,810 without losing any data. 154 154 00:08:06,810 --> 00:08:08,290 Now one important thing to note here, 155 155 00:08:08,290 --> 00:08:10,900 we're using the prefix decrement 156 156 00:08:10,900 --> 00:08:14,080 and the prefix increment operator so what this means 157 157 00:08:14,080 --> 00:08:17,590 is when we execute this statement, we'll decrement J 158 158 00:08:17,590 --> 00:08:19,960 and then we'll use the result as the index 159 159 00:08:19,960 --> 00:08:23,560 and recall that end will always be one greater 160 160 00:08:23,560 --> 00:08:26,040 than the last index of the array 161 161 00:08:26,040 --> 00:08:30,290 and so if we didn't decrement we'd get an index outta bounds 162 162 00:08:30,290 --> 00:08:33,100 exception, if we pass the entire array in 163 163 00:08:33,100 --> 00:08:36,640 or we'd actually be indexing one element past the end 164 164 00:08:36,640 --> 00:08:38,670 of the sub-array that we wanna work with. 165 165 00:08:38,670 --> 00:08:41,450 And it's the same thing here, when we first come in, 166 166 00:08:41,450 --> 00:08:44,640 I is start, I is the pivot, we wanna start with the first 167 167 00:08:44,640 --> 00:08:47,910 element after the pivot and so we're always gonna be, 168 168 00:08:47,910 --> 00:08:51,090 we wanna increment first and then use the index. 169 169 00:08:51,090 --> 00:08:54,320 And then on subsequent iterations, we'll want to increment 170 170 00:08:54,320 --> 00:08:56,620 first because we've already handled what's at I. 171 171 00:08:56,620 --> 00:08:59,200 So whenever we enter this loop, we've already handled 172 172 00:08:59,200 --> 00:09:01,640 the element at I and so we wanna increment 173 173 00:09:01,640 --> 00:09:03,940 and then use the index, we don't wanna use I 174 174 00:09:03,940 --> 00:09:06,380 or we're gonna be looking at something we've already handled 175 175 00:09:06,380 --> 00:09:07,470 and that's not gonna work. 176 176 00:09:07,470 --> 00:09:09,560 Okay, so when we drop out of this loop, 177 177 00:09:09,560 --> 00:09:13,180 I has crossed J and that means that we've finished moving 178 178 00:09:13,180 --> 00:09:15,840 elements that are smaller than the pivot to the left 179 179 00:09:15,840 --> 00:09:17,820 sub-array and elements that are larger 180 180 00:09:17,820 --> 00:09:19,540 than the pivot to the right sub-array 181 181 00:09:19,540 --> 00:09:24,540 and so at this point, the value of J will be the index 182 182 00:09:25,290 --> 00:09:27,460 where we want to insert the pivot 183 183 00:09:27,460 --> 00:09:29,520 and so that's all we have left to do 184 184 00:09:29,520 --> 00:09:34,520 and so we'll say input J, J not I, equals the pivot 185 185 00:09:35,910 --> 00:09:39,010 and then we have to return J because remember what we're 186 186 00:09:39,010 --> 00:09:43,170 returning from this method is the index where we inserted 187 187 00:09:43,170 --> 00:09:47,270 the pivot because that's how we're dividing the array 188 188 00:09:47,270 --> 00:09:51,210 and we need that to then call quick sort for the left array 189 189 00:09:51,210 --> 00:09:53,010 and quick sort for the right array. 190 190 00:09:53,010 --> 00:09:54,860 And you'll notice that when we called quick sort 191 191 00:09:54,860 --> 00:09:57,380 for the left array, we passed the pivot index 192 192 00:09:57,380 --> 00:10:00,740 because as I said, the end index is always going to be 193 193 00:10:00,740 --> 00:10:05,740 one greater than the last valid index in the partition 194 194 00:10:06,570 --> 00:10:10,310 in the array, the sub-array that we wanna partition next 195 195 00:10:10,310 --> 00:10:13,190 and so we really, for the left sub-array, 196 196 00:10:13,190 --> 00:10:18,050 we'll go from index start to pivot index minus one. 197 197 00:10:18,050 --> 00:10:21,690 And so we pass pivot index 'cause we wanna pass one greater 198 198 00:10:21,690 --> 00:10:23,920 than the last index we're interested in. 199 199 00:10:23,920 --> 00:10:26,510 And that's it, that's our quick sort algorithm. 200 200 00:10:26,510 --> 00:10:31,250 Keep in mind that this is recursive so when we come in here 201 201 00:10:31,250 --> 00:10:34,300 we call quick sort on the first left sub-array, 202 202 00:10:34,300 --> 00:10:39,300 this is not gonna return until the first left sub-array, 203 203 00:10:39,420 --> 00:10:43,557 this sub-array here, remember the first pivot element is 20 204 204 00:10:43,557 --> 00:10:46,760 and we end up inserting it here, so the first left sub-array 205 205 00:10:46,760 --> 00:10:51,310 that we're gonna call this with is this sub-array here. 206 206 00:10:51,310 --> 00:10:53,740 This quick sort call is not gonna return 207 207 00:10:53,740 --> 00:10:57,410 until this entire thing has been quick sorted 208 208 00:10:57,410 --> 00:11:00,350 and so by the time this call returns, 209 209 00:11:00,350 --> 00:11:02,860 all of this will be sorted and the same thing goes 210 210 00:11:02,860 --> 00:11:05,750 for this quick sort, by the time it returns, 211 211 00:11:05,750 --> 00:11:07,810 this whole sub-array will have been sorted. 212 212 00:11:07,810 --> 00:11:10,803 So let's run this to make sure it actually works. 213 213 00:11:13,690 --> 00:11:17,450 And of course I did not, doesn't work because 214 214 00:11:17,450 --> 00:11:19,790 I haven't actually called quick sort. 215 215 00:11:19,790 --> 00:11:23,120 So we're getting here the unsorted array. 216 216 00:11:23,120 --> 00:11:25,630 So we're gonna call quick sort, we're gonna pass 217 217 00:11:25,630 --> 00:11:29,030 our int array, we're gonna pass zero for start 218 218 00:11:29,030 --> 00:11:32,570 and we're gonna pass, should be int array, 219 219 00:11:32,570 --> 00:11:37,570 zero for start and int array dot length as the end index. 220 220 00:11:37,910 --> 00:11:39,853 So let's give this another shot. 221 221 00:11:41,670 --> 00:11:43,270 And now we have our sorted array. 222 222 00:11:43,270 --> 00:11:45,810 It always helps when you actually call the sort method. 223 223 00:11:45,810 --> 00:11:50,810 So minus 22, minus 15, one, seven, 20, 35, and 55. 224 224 00:11:53,560 --> 00:11:55,460 So if you're having trouble understanding what's 225 225 00:11:55,460 --> 00:11:58,160 going on here, go back to the slides 226 226 00:11:58,160 --> 00:12:00,930 and the key point to remember is that we're alternating 227 227 00:12:00,930 --> 00:12:04,810 between I and J, we're alternating between traversing 228 228 00:12:04,810 --> 00:12:08,080 from right to left, looking for smaller elements 229 229 00:12:08,080 --> 00:12:10,850 and going from left to right looking for larger elements 230 230 00:12:10,850 --> 00:12:14,510 and because we're alternating, we can do all of this 231 231 00:12:14,510 --> 00:12:17,010 in place without losing any data. 232 232 00:12:17,010 --> 00:12:19,870 And if you're having trouble understanding the recursive 233 233 00:12:19,870 --> 00:12:24,520 nature of it, go back and review the video on recursion. 234 234 00:12:24,520 --> 00:12:27,090 So that's it for quick sort, that's the second divide 235 235 00:12:27,090 --> 00:12:29,160 and conquer algorithm we've see, 236 236 00:12:29,160 --> 00:12:31,430 but we're not out of sort algorithms yet. 237 237 00:12:31,430 --> 00:12:33,163 So I'll see you in the next video. 22160