Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,331 --> 00:00:02,441 (bright music) 2 2 00:00:02,441 --> 00:00:05,370 (keyboard clicking) 3 3 00:00:05,370 --> 00:00:08,220 In this video, we're going to look at Quick Sort. 4 4 00:00:08,220 --> 00:00:11,750 And Quick Sort is another divide and conquer algorithm, 5 5 00:00:11,750 --> 00:00:14,040 just like merge sort. 6 6 00:00:14,040 --> 00:00:16,850 And just like merge sort, we can write it recursively, 7 7 00:00:16,850 --> 00:00:18,210 and we often do. 8 8 00:00:18,210 --> 00:00:20,040 So how does Quick Sort work? 9 9 00:00:20,040 --> 00:00:22,030 Well, Quick Sort 10 10 00:00:22,030 --> 00:00:24,800 chooses a pivot element 11 11 00:00:24,800 --> 00:00:28,090 and then it divides the array into two halves 12 12 00:00:28,090 --> 00:00:30,990 and this division is a logical division. 13 13 00:00:30,990 --> 00:00:33,020 So it chooses a pivot element. 14 14 00:00:33,020 --> 00:00:35,530 It divides the array into two halves. 15 15 00:00:35,530 --> 00:00:39,090 On the left half, it puts elements that are less 16 16 00:00:39,090 --> 00:00:40,700 than the pivot element. 17 17 00:00:40,700 --> 00:00:43,360 And in the right half, for the right subarray, 18 18 00:00:43,360 --> 00:00:47,120 it puts elements that are greater than the pivot element. 19 19 00:00:47,120 --> 00:00:50,450 And so the pivot element will be in the middle, 20 20 00:00:50,450 --> 00:00:52,380 between the two arrays. 21 21 00:00:52,380 --> 00:00:55,890 Everything less than the pivot element will be to the left 22 22 00:00:55,890 --> 00:00:58,200 and everything greater to the pivot element 23 23 00:00:58,200 --> 00:00:59,410 will be to the right. 24 24 00:00:59,410 --> 00:01:02,300 And this is called the partitioning step. 25 25 00:01:02,300 --> 00:01:04,200 So think about this for a minute, 26 26 00:01:04,200 --> 00:01:06,600 if all the elements less than the pivot 27 27 00:01:06,600 --> 00:01:08,790 are placed at its left 28 28 00:01:08,790 --> 00:01:11,010 and all the elements greater than the pivot 29 29 00:01:11,010 --> 00:01:12,960 are placed to its right, 30 30 00:01:12,960 --> 00:01:16,760 that means that after we've finished the partitioning step, 31 31 00:01:16,760 --> 00:01:21,430 the pivot is in its correct sorted position in the array. 32 32 00:01:21,430 --> 00:01:23,880 But, and this is important to note, 33 33 00:01:23,880 --> 00:01:28,240 the left and right subarrays aren't necessarily sorted. 34 34 00:01:28,240 --> 00:01:30,680 We know all the elements in the left subarray 35 35 00:01:30,680 --> 00:01:32,030 are smaller than the pivot 36 36 00:01:32,030 --> 00:01:35,210 and we know that all the elements in the right subarray 37 37 00:01:35,210 --> 00:01:37,120 are larger than the pivot, 38 38 00:01:37,120 --> 00:01:41,720 but those left and right subarrays aren't sorted. 39 39 00:01:41,720 --> 00:01:44,600 And so once we've done this partitioning, 40 40 00:01:44,600 --> 00:01:47,640 we then do the same thing for the left array 41 41 00:01:47,640 --> 00:01:49,600 and the same thing for the right array. 42 42 00:01:49,600 --> 00:01:52,020 In the left array, we're gonna choose a pivot. 43 43 00:01:52,020 --> 00:01:54,950 We're gonna put all the items in the left array 44 44 00:01:54,950 --> 00:01:58,250 that are smaller than the pivot to the left. 45 45 00:01:58,250 --> 00:02:00,470 All the elements in the left subarray 46 46 00:02:00,470 --> 00:02:02,650 that are larger than the pivot to the right. 47 47 00:02:02,650 --> 00:02:04,070 And then we're gonna do the same thing 48 48 00:02:04,070 --> 00:02:05,350 with the right subarray. 49 49 00:02:05,350 --> 00:02:07,160 And then we're gonna repeat the process. 50 50 00:02:07,160 --> 00:02:09,510 So essentially, it's divide and conquer 51 51 00:02:09,510 --> 00:02:10,870 because at each stage, 52 52 00:02:10,870 --> 00:02:13,380 we're sort of doing what we did with merge sort. 53 53 00:02:13,380 --> 00:02:16,430 We're partitioning the array into two 54 54 00:02:16,430 --> 00:02:18,360 around this pivot element. 55 55 00:02:18,360 --> 00:02:20,300 And just as with merge sort, 56 56 00:02:20,300 --> 00:02:22,690 we'll end up partitioning the array into a series 57 57 00:02:22,690 --> 00:02:24,410 of one element arrays. 58 58 00:02:24,410 --> 00:02:27,370 Now because eventually, every element will be chosen 59 59 00:02:27,370 --> 00:02:28,420 as the pivot, 60 60 00:02:28,420 --> 00:02:30,480 eventually every element will be 61 61 00:02:30,480 --> 00:02:32,420 in its correct sorted position. 62 62 00:02:32,420 --> 00:02:35,740 Now unlike merge sort, this is all done in place, 63 63 00:02:35,740 --> 00:02:38,870 so we don't have to create any temporary arrays. 64 64 00:02:38,870 --> 00:02:40,850 So one advantage of Quick Sort 65 65 00:02:40,850 --> 00:02:44,930 is you don't need a lot of memory to do this sort. 66 66 00:02:44,930 --> 00:02:47,730 If you were sorting a really large array, 67 67 00:02:47,730 --> 00:02:51,180 you would be doing the sorting in place with Quick Sort, 68 68 00:02:51,180 --> 00:02:52,860 but with merge sort, you'd have to create 69 69 00:02:52,860 --> 00:02:54,590 a bunch of temporary arrays. 70 70 00:02:54,590 --> 00:02:56,360 So let's take a look at this. 71 71 00:02:56,360 --> 00:02:58,860 Let's go through it with our usual array. 72 72 00:02:58,860 --> 00:03:01,320 In the implementation I'm going to show you, 73 73 00:03:01,320 --> 00:03:04,410 we're always going to choose the first element 74 74 00:03:04,410 --> 00:03:07,650 in the array, or the subarray, as the pivot. 75 75 00:03:07,650 --> 00:03:10,920 So we're going to set the pivot to 20. 76 76 00:03:10,920 --> 00:03:13,650 We're going to set the start index to zero 77 77 00:03:13,650 --> 00:03:15,740 and the end index to seven. 78 78 00:03:15,740 --> 00:03:18,210 And we're gonna make i equal start 79 79 00:03:18,210 --> 00:03:20,090 and j equal end. 80 80 00:03:20,090 --> 00:03:22,410 So we start with minus, minus j. 81 81 00:03:22,410 --> 00:03:25,750 J was, if we go back, j is gonna equal seven, 82 82 00:03:25,750 --> 00:03:26,770 because it equal n. 83 83 00:03:26,770 --> 00:03:29,810 So minus, minus j is gonna equal six. 84 84 00:03:29,810 --> 00:03:31,600 And we're gonna go from right to left, 85 85 00:03:31,600 --> 00:03:33,060 looking for the first element 86 86 00:03:33,060 --> 00:03:35,320 that's less than the pivot element. 87 87 00:03:35,320 --> 00:03:38,090 Minus 22 is less than the pivot element. 88 88 00:03:38,090 --> 00:03:41,820 The pivot element is 20, and so we assign 89 89 00:03:41,820 --> 00:03:44,690 minus 22 to position zero. 90 90 00:03:44,690 --> 00:03:47,680 Now don't worry that we've overwritten 20 91 91 00:03:47,680 --> 00:03:52,030 because remember, we'll have saved 20 in a pivot field. 92 92 00:03:52,030 --> 00:03:54,400 Now at this point, we switch to i. 93 93 00:03:54,400 --> 00:03:56,200 And we add one to i. 94 94 00:03:56,200 --> 00:03:58,030 Now if we go back a couple of slides, 95 95 00:03:58,030 --> 00:04:00,050 i started at zero. 96 96 00:04:00,050 --> 00:04:01,720 So when we add one to i, 97 97 00:04:01,720 --> 00:04:04,560 we're going to be i equal to one. 98 98 00:04:04,560 --> 00:04:06,910 And this time, we're going to go from left to right 99 99 00:04:06,910 --> 00:04:08,700 and we're gonna look for the first element 100 100 00:04:08,700 --> 00:04:10,470 that's greater than the pivot. 101 101 00:04:10,470 --> 00:04:12,530 35 is greater than the pivot 102 102 00:04:12,530 --> 00:04:16,060 and so we're going to assign it to position j. 103 103 00:04:16,060 --> 00:04:18,100 And currently, j is six. 104 104 00:04:18,100 --> 00:04:19,900 And so this is going to happen. 105 105 00:04:19,900 --> 00:04:22,880 Now notice that we've not lost any data 106 106 00:04:22,880 --> 00:04:25,930 because we already moved what was at position six 107 107 00:04:25,930 --> 00:04:28,740 down to position zero. 108 108 00:04:28,740 --> 00:04:32,200 And so by alternating between going from right to left 109 109 00:04:32,200 --> 00:04:33,240 and left to right, 110 110 00:04:33,240 --> 00:04:36,110 we can be sure that we won't lose any data. 111 111 00:04:36,110 --> 00:04:39,130 We're not going to overwrite any positions 112 112 00:04:39,130 --> 00:04:40,940 that haven't already handled. 113 113 00:04:40,940 --> 00:04:43,910 So essentially, j moves from right to left, 114 114 00:04:43,910 --> 00:04:47,010 looking for values that are smaller than the pivot. 115 115 00:04:47,010 --> 00:04:49,170 And i moves from left to right, 116 116 00:04:49,170 --> 00:04:52,530 looking for values that are larger than the pivot. 117 117 00:04:52,530 --> 00:04:55,740 And by doing these alternate assignments, 118 118 00:04:55,740 --> 00:04:58,240 we're never going to overwrite a position 119 119 00:04:58,240 --> 00:05:00,000 that we haven't already handled. 120 120 00:05:00,000 --> 00:05:02,880 So at this point, j is equal to six, 121 121 00:05:02,880 --> 00:05:04,750 and i is equal to one. 122 122 00:05:04,750 --> 00:05:07,980 And we're now going to check whether the values 123 123 00:05:07,980 --> 00:05:10,150 of i and j have crossed each other. 124 124 00:05:10,150 --> 00:05:12,950 If i is less than j, they haven't crossed each other 125 125 00:05:12,950 --> 00:05:16,250 and so, once again, we switch back to j. 126 126 00:05:16,250 --> 00:05:17,840 And we look for the first element 127 127 00:05:17,840 --> 00:05:19,320 that's less than the pivot. 128 128 00:05:19,320 --> 00:05:21,320 So we're gonna subtract one from j. 129 129 00:05:21,320 --> 00:05:24,200 And one is less than the pivot value 130 130 00:05:24,200 --> 00:05:25,500 which is 20. 131 131 00:05:25,500 --> 00:05:28,550 And so we're going to assign to position i. 132 132 00:05:28,550 --> 00:05:30,110 And remember, i is one. 133 133 00:05:30,110 --> 00:05:31,960 So we assign it to position i. 134 134 00:05:31,960 --> 00:05:34,650 And notice, again, that we haven't lost any data 135 135 00:05:34,650 --> 00:05:38,740 because we've already moved 35 from position one. 136 136 00:05:38,740 --> 00:05:40,490 So now we switch back to i 137 137 00:05:40,490 --> 00:05:42,390 and we're going to look for the first element 138 138 00:05:42,390 --> 00:05:43,960 that's greater than the pivot. 139 139 00:05:43,960 --> 00:05:46,730 And this is going to take us all the way to 55 140 140 00:05:46,730 --> 00:05:49,630 because minus 15 is less than the pivot 141 141 00:05:49,630 --> 00:05:51,800 and seven is less than the pivot. 142 142 00:05:51,800 --> 00:05:54,180 And so we eventually hit 55 143 143 00:05:54,180 --> 00:05:55,920 and that's greater than the pivot. 144 144 00:05:55,920 --> 00:05:58,400 So at this point, we're going to assign 55 145 145 00:05:58,400 --> 00:05:59,730 to position j. 146 146 00:05:59,730 --> 00:06:01,030 J is five, 147 147 00:06:01,030 --> 00:06:03,950 so we assign 55 to position five. 148 148 00:06:03,950 --> 00:06:07,510 And once again, because were doing this alternating 149 149 00:06:07,510 --> 00:06:10,700 between i and j, between going from right to left 150 150 00:06:10,700 --> 00:06:13,310 and left to right, we haven't lost any data 151 151 00:06:13,310 --> 00:06:16,220 because we already moved the value of one 152 152 00:06:16,220 --> 00:06:17,660 from position five. 153 153 00:06:17,660 --> 00:06:20,360 So now, we check to see whether i 154 154 00:06:20,360 --> 00:06:21,780 and j have crossed each other. 155 155 00:06:21,780 --> 00:06:24,810 At this point, i is four and j is five. 156 156 00:06:24,810 --> 00:06:26,340 So they have not crossed each other. 157 157 00:06:26,340 --> 00:06:28,500 And so we switch back to j 158 158 00:06:28,500 --> 00:06:30,390 and we look for the first element that's 159 159 00:06:30,390 --> 00:06:31,890 less than the pivot. 160 160 00:06:31,890 --> 00:06:34,250 Now we're gonna find that at position three, 161 161 00:06:34,250 --> 00:06:37,350 but at this point, j has crossed i. 162 162 00:06:37,350 --> 00:06:39,880 Because i is equal to four, 163 163 00:06:39,880 --> 00:06:42,540 so j has kind of jumped over i 164 164 00:06:42,540 --> 00:06:44,640 and is less than i and so we stop. 165 165 00:06:44,640 --> 00:06:45,960 We don't do anything. 166 166 00:06:45,960 --> 00:06:48,340 Now if you'll notice at this point, 167 167 00:06:48,340 --> 00:06:51,280 the value of i will be the sorted position 168 168 00:06:51,280 --> 00:06:52,820 of the pivot value. 169 169 00:06:52,820 --> 00:06:55,410 So right now, i is four. 170 170 00:06:55,410 --> 00:06:57,820 And so we're gonna assign 20 to four. 171 171 00:06:57,820 --> 00:07:00,510 And notice that everything to the left of 20 172 172 00:07:00,510 --> 00:07:02,430 is smaller than 20 173 173 00:07:02,430 --> 00:07:05,620 and everything to the right of 20 is larger than 20. 174 174 00:07:05,620 --> 00:07:09,940 And not only that, 20 is in its correct sorted position 175 175 00:07:09,940 --> 00:07:11,730 in the entire array. 176 176 00:07:11,730 --> 00:07:13,070 If we were to sort this array, 177 177 00:07:13,070 --> 00:07:15,130 20 would end up at position four. 178 178 00:07:15,130 --> 00:07:17,240 So we've completed our first partition 179 179 00:07:17,240 --> 00:07:19,360 and now we're going to repeat this process 180 180 00:07:19,360 --> 00:07:21,070 for the left partition. 181 181 00:07:21,070 --> 00:07:24,220 So for indices zero to three, 182 182 00:07:24,220 --> 00:07:27,440 and the right partition, indices five and six. 183 183 00:07:27,440 --> 00:07:31,010 And we're going to do this until the entire array is sorted 184 184 00:07:31,010 --> 00:07:33,710 because by doing it for the left and right, 185 185 00:07:33,710 --> 00:07:35,470 and of course, once we finish those, 186 186 00:07:35,470 --> 00:07:38,400 we're gonna partition their left and right. 187 187 00:07:38,400 --> 00:07:40,670 And so eventually, every single element 188 188 00:07:40,670 --> 00:07:42,550 gets to be the pivot element. 189 189 00:07:42,550 --> 00:07:44,950 And so eventually, every single element 190 190 00:07:44,950 --> 00:07:47,420 will end up at its correct sorted position. 191 191 00:07:47,420 --> 00:07:50,530 So as I said, Quick Sort is an in-place algorithm. 192 192 00:07:50,530 --> 00:07:52,800 It takes place within the array 193 193 00:07:52,800 --> 00:07:55,020 and that's an advantage over merge sort. 194 194 00:07:55,020 --> 00:08:00,020 Just like merge sort, it's O(nlogn) and that's to the base 2 195 195 00:08:00,300 --> 00:08:02,110 because we're repeatedly partitioning 196 196 00:08:02,110 --> 00:08:04,110 the array into two halves. 197 197 00:08:04,110 --> 00:08:06,310 Now one thing about Quick Sort is, 198 198 00:08:06,310 --> 00:08:11,240 in the worst case, it's actually a quadratic algorithm. 199 199 00:08:11,240 --> 00:08:12,760 But in the average case, 200 200 00:08:12,760 --> 00:08:16,850 it performs with a time complexity of O(nlogn) 201 201 00:08:16,850 --> 00:08:20,070 and most of the time, it performs better than merge sort. 202 202 00:08:20,070 --> 00:08:23,130 Now Quick Sort is an unstable algorithm. 203 203 00:08:23,130 --> 00:08:25,290 And I think you can probably guess why 204 204 00:08:25,290 --> 00:08:28,120 because when we're alternating between i and j, 205 205 00:08:28,120 --> 00:08:31,570 we're swapping, potentially, things from the 206 206 00:08:31,570 --> 00:08:32,920 left to things to the right 207 207 00:08:32,920 --> 00:08:34,970 and things to the right over to the left 208 208 00:08:34,970 --> 00:08:37,820 so we can have elements jumping over each other, 209 209 00:08:37,820 --> 00:08:41,010 there's no guarantee that the relative positioning 210 210 00:08:41,010 --> 00:08:43,250 of duplicate items will be preserved. 211 211 00:08:43,250 --> 00:08:46,430 Now it's important to note that the choice of pivot 212 212 00:08:46,430 --> 00:08:48,880 can have an effect on the time complexity, 213 213 00:08:48,880 --> 00:08:51,630 depending on the data that's being sorted. 214 214 00:08:51,630 --> 00:08:54,460 All right, so that's it for how Quick Sort works. 215 215 00:08:54,460 --> 00:08:56,630 Let's move onto the implementation. 216 216 00:08:56,630 --> 00:08:58,180 I'll see you in the next video. 18353