Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:05,210 --> 00:00:06,280 So we're going to kick off 2 2 00:00:06,280 --> 00:00:10,000 our look at sort algorithms by starting with bubble sort. 3 3 00:00:10,000 --> 00:00:12,044 I want to say right up front that this 4 4 00:00:12,044 --> 00:00:14,770 algorithm's performance degrades quickly 5 5 00:00:14,770 --> 00:00:17,850 as the number of items you need to sort grows, 6 6 00:00:17,850 --> 00:00:20,330 but it's a commonly taught algorithm 7 7 00:00:20,330 --> 00:00:23,170 and you might hear about it so will take a look at it 8 8 00:00:23,170 --> 00:00:25,860 and it will get us warmed up for the rest of this section. 9 9 00:00:25,860 --> 00:00:27,610 So I'm going to start out by explaining 10 10 00:00:27,610 --> 00:00:29,570 how the algorithm works. 11 11 00:00:29,570 --> 00:00:31,580 So I have an array on this screen, 12 12 00:00:31,580 --> 00:00:34,140 it's an array of length seven 13 13 00:00:34,140 --> 00:00:36,710 so we can store seven integers. 14 14 00:00:36,710 --> 00:00:41,710 At index 0 we have 20, at index 1 35, at index 2 -15. 15 15 00:00:42,580 --> 00:00:44,610 You can see the rest of the array there 16 16 00:00:44,610 --> 00:00:47,800 and we want to use bubble sort to sort this array. 17 17 00:00:47,800 --> 00:00:49,640 Now the way that bubble sort works 18 18 00:00:49,640 --> 00:00:51,090 and you're going to see that this is 19 19 00:00:51,090 --> 00:00:53,960 pretty common with sort algorithms is 20 20 00:00:53,960 --> 00:00:56,470 as the algorithm progresses, 21 21 00:00:56,470 --> 00:01:00,760 it partitions the array into a sorted partition 22 22 00:01:00,760 --> 00:01:03,200 and an unsorted partition 23 23 00:01:03,200 --> 00:01:06,010 and this is a logical partitioning so 24 24 00:01:06,010 --> 00:01:09,840 we don't create completely separate array instances 25 25 00:01:09,840 --> 00:01:12,110 and we an array instance that contains 26 26 00:01:12,110 --> 00:01:13,970 what we've sorted so far and another 27 27 00:01:13,970 --> 00:01:16,350 array instance that contains unsorted numbers. 28 28 00:01:16,350 --> 00:01:19,810 No, everything is done when it comes to bubble sort 29 29 00:01:19,810 --> 00:01:22,350 using the array that we're sorting 30 30 00:01:22,350 --> 00:01:24,850 and we partition the array logically 31 31 00:01:24,850 --> 00:01:25,770 and you're going to see this when 32 32 00:01:25,770 --> 00:01:27,890 we go through the algorithm in just a minute. 33 33 00:01:27,890 --> 00:01:31,780 So when we start the algorithm for this array, 34 34 00:01:31,780 --> 00:01:34,610 we're going to have a field that 35 35 00:01:34,610 --> 00:01:37,360 we're going to call unsorted partition index 36 36 00:01:37,360 --> 00:01:41,340 and when we start this will be 6 37 37 00:01:41,340 --> 00:01:44,730 because the entire array is the 38 38 00:01:44,730 --> 00:01:47,210 unsorted partition when we start out 39 39 00:01:47,210 --> 00:01:49,100 because we haven't sorted anything yet. 40 40 00:01:49,100 --> 00:01:53,660 So 6, it will be the last index of the unsorted partition. 41 41 00:01:53,660 --> 00:01:56,290 Alright, so the implementation that I'm going to show you 42 42 00:01:56,290 --> 00:01:58,990 starts at the left of the array, or at index 0, 43 43 00:01:58,990 --> 00:02:02,110 so that's what I is and what we do 44 44 00:02:02,110 --> 00:02:04,980 is we compare the elemented index 0 45 45 00:02:04,980 --> 00:02:06,280 with the elemented index 1 46 46 00:02:07,330 --> 00:02:10,090 and if the elemented index 0 is greater 47 47 00:02:10,090 --> 00:02:14,510 than the elemented index 1, we swap the elements. 48 48 00:02:14,510 --> 00:02:16,350 If it's less we don't do anything 49 49 00:02:16,350 --> 00:02:19,230 because of course we want to move larger elements 50 50 00:02:19,230 --> 00:02:22,270 towards the end of the array or towards the right 51 51 00:02:22,270 --> 00:02:24,560 because we're sorting in ascending order. 52 52 00:02:24,560 --> 00:02:29,050 So in this case 20 is less than 35 53 53 00:02:29,050 --> 00:02:31,430 so we don't do any swapping 54 54 00:02:31,430 --> 00:02:34,630 and then what we're going to do is increment I to 1. 55 55 00:02:34,630 --> 00:02:37,070 So now we're going to look at 56 56 00:02:37,070 --> 00:02:38,780 the element at position 1 57 57 00:02:38,780 --> 00:02:42,030 and compare it with the element at position 2 58 58 00:02:42,030 --> 00:02:45,543 and in this case 35 is greater than -15, 59 59 00:02:46,510 --> 00:02:47,863 so we swap them. 60 60 00:02:48,740 --> 00:02:51,350 So now -15 will be at position 1 61 61 00:02:51,350 --> 00:02:53,620 and 35 will be at position 2 62 62 00:02:53,620 --> 00:02:55,760 and we increment I to 2. 63 63 00:02:55,760 --> 00:02:57,430 So now we're going to compare the 64 64 00:02:57,430 --> 00:03:01,420 element at index 2 with the elemented index 3. 65 65 00:03:01,420 --> 00:03:05,710 35 is greater than 7 so we swap them 66 66 00:03:05,710 --> 00:03:08,350 and we increment I to 3. 67 67 00:03:08,350 --> 00:03:11,100 So now we're going to compare the elemented index 3 68 68 00:03:11,100 --> 00:03:13,530 with the elemented index 4. 69 69 00:03:13,530 --> 00:03:16,630 35 is less than 55 so we don't do anything 70 70 00:03:16,630 --> 00:03:19,320 we just increment I to 4 71 71 00:03:19,320 --> 00:03:22,000 and then we compare 55 to 1, 72 72 00:03:22,000 --> 00:03:23,700 that's the elemented position 4 73 73 00:03:23,700 --> 00:03:26,010 with the elemented position 5. 74 74 00:03:26,010 --> 00:03:28,960 55 is greater than 1 so we swap them 75 75 00:03:29,800 --> 00:03:32,420 and we increment I to 5 76 76 00:03:32,420 --> 00:03:36,380 and finally we compare 55 to -22 77 77 00:03:36,380 --> 00:03:41,380 and of course 55 is greater than -22 so we swap them 78 78 00:03:42,060 --> 00:03:44,910 and at this point I is equal to 79 79 00:03:44,910 --> 00:03:49,100 the last unsorted partition index so we stop. 80 80 00:03:49,100 --> 00:03:53,610 We have completed the first traversal of the array 81 81 00:03:53,610 --> 00:03:56,210 and at the end of that traversal, 82 82 00:03:56,210 --> 00:04:00,800 the last element in the array is in its correct position 83 83 00:04:00,800 --> 00:04:03,830 and so at this point the greatest element in the array 84 84 00:04:03,830 --> 00:04:07,850 will be at index array length minus one 85 85 00:04:10,080 --> 00:04:13,000 and for our array length minus one is 6. 86 86 00:04:13,000 --> 00:04:16,230 So at this point what we're going to do is 87 87 00:04:16,230 --> 00:04:21,150 we're going to set the unsorted partition index to 5 88 88 00:04:21,150 --> 00:04:24,910 because we now consider position 6 to be sorted 89 89 00:04:24,910 --> 00:04:29,070 and so the logical partition is going to be between 90 90 00:04:29,070 --> 00:04:32,350 the elemented index 5 and the elemented index 6. 91 91 00:04:32,350 --> 00:04:35,520 Everything from index 5 down to the front 92 92 00:04:35,520 --> 00:04:38,050 of the array is in the unsorted partition 93 93 00:04:38,050 --> 00:04:42,160 and everything at array index 6 and to the right, 94 94 00:04:42,160 --> 00:04:44,110 and in this case there isn't anything to the right, 95 95 00:04:44,110 --> 00:04:46,830 everything there is in the sorted partition. 96 96 00:04:46,830 --> 00:04:48,890 So on the next traversal, 97 97 00:04:48,890 --> 00:04:53,630 we can see that 55 is now in the sorted partition 98 98 00:04:53,630 --> 00:04:56,080 and we set I back to zero 99 99 00:04:56,080 --> 00:04:59,290 because we want to repeat the process we just did 100 100 00:04:59,290 --> 00:05:02,400 and the unsorted partition index is now 5. 101 101 00:05:02,400 --> 00:05:05,860 So we start all over again we go OK 102 102 00:05:05,860 --> 00:05:09,040 the element at array index 0 103 103 00:05:09,040 --> 00:05:12,080 is it greater than the element array index 1 104 104 00:05:12,080 --> 00:05:14,870 and it is and so we swap them 105 105 00:05:14,870 --> 00:05:16,820 and we increment I to 1 106 106 00:05:16,820 --> 00:05:17,840 and then we say 107 107 00:05:17,840 --> 00:05:20,710 is the array element at index 1 108 108 00:05:20,710 --> 00:05:22,930 greater than the array element at index 2? 109 109 00:05:22,930 --> 00:05:27,220 Yes it is so we swap them and we increment I to 2. 110 110 00:05:27,220 --> 00:05:29,470 We say is the element at index 2 111 111 00:05:29,470 --> 00:05:31,210 greater than the elemented index 3? 112 112 00:05:31,210 --> 00:05:35,090 No it isn't so we just increment I to 3. 113 113 00:05:35,090 --> 00:05:37,480 Then we compare the elemented index 3 114 114 00:05:37,480 --> 00:05:39,630 to the elemented index 4. 115 115 00:05:39,630 --> 00:05:42,730 35 is greater than one so we swap them, 116 116 00:05:42,730 --> 00:05:44,700 I get incremented to 4 . 117 117 00:05:44,700 --> 00:05:48,860 35 is greater than -22 so we swap them. 118 118 00:05:48,860 --> 00:05:52,150 I gets incremented to 5 and now I equals 119 119 00:05:52,150 --> 00:05:55,200 the unsorted partition index so we stop. 120 120 00:05:55,200 --> 00:06:00,120 And at this point, 35 and 55 are in their correct positions 121 121 00:06:00,120 --> 00:06:04,610 and we set the unsorted partition index to 4. 122 122 00:06:04,610 --> 00:06:07,610 So now everything in array index 0 123 123 00:06:07,610 --> 00:06:11,430 to array index 4 is in the unsorted partition 124 124 00:06:11,430 --> 00:06:14,650 and everything from array index 5 125 125 00:06:14,650 --> 00:06:17,950 up to the end of the array is in the sorted partition 126 126 00:06:17,950 --> 00:06:19,720 and we've set I back to zero 127 127 00:06:19,720 --> 00:06:21,600 because we're now going to repeat the process. 128 128 00:06:21,600 --> 00:06:24,040 Now I'm not going to go through the other traversals, 129 129 00:06:24,040 --> 00:06:26,630 they'll operate the exact same way. 130 130 00:06:26,630 --> 00:06:28,370 We're gonna to keep incrementing I and 131 131 00:06:28,370 --> 00:06:31,220 we're gonna keep comparing the elemented I 132 132 00:06:31,220 --> 00:06:33,640 with its neighbour and swap the elements 133 133 00:06:33,640 --> 00:06:37,210 if its neighbour is less than the elemented I 134 134 00:06:37,210 --> 00:06:40,900 until the sorted partition is the entire array 135 135 00:06:40,900 --> 00:06:41,990 and then we're done. 136 136 00:06:41,990 --> 00:06:44,780 Now this is called a bubble sort because depending on 137 137 00:06:44,780 --> 00:06:47,930 which way you're sorting, in our case the larger 138 138 00:06:47,930 --> 00:06:50,870 values in the array will bubble up to the end of the array 139 139 00:06:50,870 --> 00:06:52,840 and another way of looking at it is to flip 140 140 00:06:52,840 --> 00:06:55,460 the array vertically so we take the array 141 141 00:06:55,460 --> 00:06:58,310 and we flip it counterclockwise so that 142 142 00:06:58,310 --> 00:07:00,610 array element zero is at the bottom and 143 143 00:07:00,610 --> 00:07:02,640 array element 6 is at the top 144 144 00:07:02,640 --> 00:07:03,930 and another way of looking at it 145 145 00:07:03,930 --> 00:07:05,480 is saying that the larger values are 146 146 00:07:05,480 --> 00:07:07,190 bubbling up to the top of the array. 147 147 00:07:07,190 --> 00:07:09,050 Now as I said there are some variations 148 148 00:07:09,050 --> 00:07:11,870 where the array is sorted from right to left 149 149 00:07:11,870 --> 00:07:14,290 so the traversal goes from right to left 150 150 00:07:14,290 --> 00:07:16,570 and sometimes the smaller elements are bubbled 151 151 00:07:16,570 --> 00:07:17,720 to the front of the array 152 152 00:07:17,720 --> 00:07:19,090 rather than the larger elements 153 153 00:07:19,090 --> 00:07:20,870 being bubbled to the back of the array 154 154 00:07:20,870 --> 00:07:22,820 but the same steps are used, 155 155 00:07:22,820 --> 00:07:24,360 it's the same algorithm. 156 156 00:07:24,360 --> 00:07:27,170 So that's bubble sort and so now let's take a look at 157 157 00:07:27,170 --> 00:07:29,290 how this algorithm performs. 158 158 00:07:29,290 --> 00:07:32,120 First of all, it's an in-place algorithm. 159 159 00:07:32,120 --> 00:07:33,500 Now what do I mean by that? 160 160 00:07:33,500 --> 00:07:37,010 Well as I said we're logically partitioning the array. 161 161 00:07:37,010 --> 00:07:39,790 We don't have to create another array 162 162 00:07:39,790 --> 00:07:41,580 in order to perform this sort 163 163 00:07:41,580 --> 00:07:43,160 and so when it comes to memory, 164 164 00:07:43,160 --> 00:07:45,410 this is an in-place algorithm. 165 165 00:07:45,410 --> 00:07:49,240 Now we do, as you see when we look at the implementation, 166 166 00:07:49,240 --> 00:07:52,470 we do create some local variables but that's OK. 167 167 00:07:52,470 --> 00:07:53,990 It's an in-place algorithm. 168 168 00:07:53,990 --> 00:07:56,190 If the extra memory that you need 169 169 00:07:56,190 --> 00:07:59,110 doesn't depend on the number of items you're sorting. 170 170 00:07:59,110 --> 00:08:02,230 So we're going to create a few local variables, for example, 171 171 00:08:02,230 --> 00:08:04,600 to store the last sorted partition 172 172 00:08:04,600 --> 00:08:07,280 and to store I, for example, but 173 173 00:08:07,280 --> 00:08:09,870 that doesn't mean it's not an in-place algorithm. 174 174 00:08:09,870 --> 00:08:12,390 If the extra memory you're using 175 175 00:08:12,390 --> 00:08:14,050 doesn't increase as the number 176 176 00:08:14,050 --> 00:08:16,330 of items in the array increases, 177 177 00:08:16,330 --> 00:08:18,640 then it's still an in-place algorithm. 178 178 00:08:18,640 --> 00:08:21,060 It's OK to use a few extra variables. 179 179 00:08:21,060 --> 00:08:24,530 Now this algorithm has O to the n square time complexity. 180 180 00:08:24,530 --> 00:08:26,680 It's a quadratic algorithm 181 181 00:08:26,680 --> 00:08:31,280 so that means that it will take 100 steps to sort 10 items, 182 182 00:08:31,280 --> 00:08:34,260 10,000 steps to sort 100 items, 183 183 00:08:34,260 --> 00:08:37,690 1,000,000 steps to sort 1,000 items. 184 184 00:08:37,690 --> 00:08:41,030 So as you can see this algorithm really degrades quickly. 185 185 00:08:41,030 --> 00:08:43,510 Now how do we get O to the n squared? 186 186 00:08:43,510 --> 00:08:45,490 Well, we'll talk about this a little more 187 187 00:08:45,490 --> 00:08:46,760 in the next video when we take 188 188 00:08:46,760 --> 00:08:48,450 a look at the implementation. 189 189 00:08:48,450 --> 00:08:49,653 So I'll see you there. 16368