Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,365 --> 00:00:02,753 (bright music) 2 2 00:00:02,753 --> 00:00:05,330 (keyboard clicking) 3 3 00:00:05,330 --> 00:00:07,360 Okay, so let's implement shell sort. 4 4 00:00:07,360 --> 00:00:08,500 I've created a project. 5 5 00:00:08,500 --> 00:00:12,260 I'm using package academy.learnprogramming.shellsort. 6 6 00:00:12,260 --> 00:00:14,040 I've added the usual intArray, 7 7 00:00:14,040 --> 00:00:16,540 the code for printing out the array 8 8 00:00:16,540 --> 00:00:19,300 and we don't need the swap method for this 9 9 00:00:19,300 --> 00:00:21,630 because insertion sort doesn't use swap 10 10 00:00:21,630 --> 00:00:23,630 and this is just, essentially, 11 11 00:00:23,630 --> 00:00:26,010 a variation on insertion sort. 12 12 00:00:26,010 --> 00:00:26,860 So let's go. 13 13 00:00:26,860 --> 00:00:29,190 So the first loop we're gonna have 14 14 00:00:29,190 --> 00:00:31,160 is the one that's going to initialise 15 15 00:00:31,160 --> 00:00:32,900 the gap value that we're using 16 16 00:00:32,900 --> 00:00:35,100 and then reduce it on each iteration. 17 17 00:00:35,100 --> 00:00:38,120 So we'll say for int gap equals 18 18 00:00:39,014 --> 00:00:40,537 intArray 19 19 00:00:40,537 --> 00:00:41,750 .length over two. 20 20 00:00:41,750 --> 00:00:44,090 Because remember, we're going to start 21 21 00:00:44,090 --> 00:00:47,120 with intArray, a gap of intArray.length over two. 22 22 00:00:47,120 --> 00:00:48,940 Which for this array, will be seven over two 23 23 00:00:48,940 --> 00:00:50,113 which is three. 24 24 00:00:51,050 --> 00:00:52,130 And then we're gonna keep going 25 25 00:00:52,130 --> 00:00:54,010 as long the gap is greater is zero 26 26 00:00:54,010 --> 00:00:55,410 because if the gap is zero, 27 27 00:00:55,410 --> 00:00:58,850 then that means that we're gonna be comparing elements 28 28 00:00:58,850 --> 00:00:59,730 against themselves. 29 29 00:00:59,730 --> 00:01:02,210 So we need a gap of one. 30 30 00:01:02,210 --> 00:01:05,470 For the final iteration, remember for shell sort, 31 31 00:01:05,470 --> 00:01:08,410 the final iteration always has to have a gap of one 32 32 00:01:08,410 --> 00:01:10,620 because we want the final iteration 33 33 00:01:10,620 --> 00:01:13,540 to essentially be insertion sort. 34 34 00:01:13,540 --> 00:01:16,150 And on each iteration, we're going to divide 35 35 00:01:16,150 --> 00:01:17,853 the gap value by two. 36 36 00:01:19,000 --> 00:01:20,540 And so on the first iteration, 37 37 00:01:20,540 --> 00:01:22,570 our gap value will be seven over two 38 38 00:01:22,570 --> 00:01:23,590 which is three. 39 39 00:01:23,590 --> 00:01:26,370 On the second iteration, it'll be three over two 40 40 00:01:26,370 --> 00:01:27,330 which is one. 41 41 00:01:27,330 --> 00:01:30,150 So the second iteration will be essentially 42 42 00:01:30,150 --> 00:01:31,303 an insertion sort. 43 43 00:01:32,800 --> 00:01:34,690 So now we're going to code 44 44 00:01:34,690 --> 00:01:37,730 the actual comparing and shifting. 45 45 00:01:37,730 --> 00:01:41,110 And as you'll see, and I'll show you this afterwards, 46 46 00:01:41,110 --> 00:01:42,280 that what we're gonna code here 47 47 00:01:42,280 --> 00:01:44,440 is essentially insertion sort. 48 48 00:01:44,440 --> 00:01:45,840 It's gonna look slightly different 49 49 00:01:45,840 --> 00:01:47,640 because it's using gap. 50 50 00:01:47,640 --> 00:01:50,010 But it's essentially insertion sort, 51 51 00:01:50,010 --> 00:01:52,690 and we'll compare the two implemetations, 52 52 00:01:52,690 --> 00:01:55,820 the two sets of code in a minute. 53 53 00:01:55,820 --> 00:01:59,653 So I'm gonna say four int i equals gap. 54 54 00:02:00,600 --> 00:02:02,910 I less than intArray.length 55 55 00:02:02,910 --> 00:02:04,410 because we're gonna want to look 56 56 00:02:04,410 --> 00:02:06,133 at all the elements in the array. 57 57 00:02:07,880 --> 00:02:09,760 I plus plus. 58 58 00:02:09,760 --> 00:02:13,280 And we're gonna start out as we did with insertion sort. 59 59 00:02:13,280 --> 00:02:15,310 We're gonna assign 60 60 00:02:15,310 --> 00:02:16,940 a newElement field 61 61 00:02:16,940 --> 00:02:18,250 with intArray i. 62 62 00:02:19,110 --> 00:02:23,930 Intarray i is the value that we're going to be looking at. 63 63 00:02:23,930 --> 00:02:26,790 So that's essentially intArray gap. 64 64 00:02:26,790 --> 00:02:29,140 And we're gonna use j 65 65 00:02:29,140 --> 00:02:31,850 to do the traversing. 66 66 00:02:31,850 --> 00:02:36,150 So we're gonna say while j is greater than equal to the gap 67 67 00:02:36,150 --> 00:02:39,260 because if j becomes less than the gap, 68 68 00:02:39,260 --> 00:02:42,960 that means that we've hit the front of the array. 69 69 00:02:42,960 --> 00:02:43,793 And 70 70 00:02:44,773 --> 00:02:47,910 intArray, j minus gap 71 71 00:02:47,910 --> 00:02:50,010 is greater than newElement. 72 72 00:02:51,160 --> 00:02:52,170 Well what do we wanna do? 73 73 00:02:52,170 --> 00:02:56,460 We wanna shift the element at intArray j minus gap 74 74 00:02:56,460 --> 00:02:58,480 up gap positions. 75 75 00:02:58,480 --> 00:03:02,100 So we're gonna say intArray j 76 76 00:03:02,100 --> 00:03:03,735 equals 77 77 00:03:03,735 --> 00:03:05,200 intArray 78 78 00:03:05,200 --> 00:03:06,963 j minus gap. 79 79 00:03:08,470 --> 00:03:09,930 And so what we're saying here, 80 80 00:03:09,930 --> 00:03:11,490 if we were doing the, 81 81 00:03:11,490 --> 00:03:13,620 we're starting out with a gap of three, 82 82 00:03:13,620 --> 00:03:14,980 so we're starting at seven, 83 83 00:03:14,980 --> 00:03:16,620 just as we did with the slides. 84 84 00:03:16,620 --> 00:03:19,220 And in the first iteration, we're gonna compare seven 85 85 00:03:19,220 --> 00:03:21,330 to j minus gap, right? 86 86 00:03:21,330 --> 00:03:24,620 Because we're going to assign seven to newElement. 87 87 00:03:24,620 --> 00:03:27,680 J is gonna start at three. 88 88 00:03:27,680 --> 00:03:30,370 And we're gonna say if intArray j minus gap 89 89 00:03:30,370 --> 00:03:33,290 while our gap for the first iteration is three. 90 90 00:03:33,290 --> 00:03:35,520 So if intArray zero which is 20, 91 91 00:03:35,520 --> 00:03:38,200 is greater than seven which it is, 92 92 00:03:38,200 --> 00:03:41,160 then we wanna shift seven up three positions. 93 93 00:03:41,160 --> 00:03:44,700 So we're going to assign intArray j which is three. 94 94 00:03:44,700 --> 00:03:48,380 So intArray three with intArray three minus three 95 95 00:03:48,380 --> 00:03:49,470 which intArray zero. 96 96 00:03:49,470 --> 00:03:52,000 So we're essentially gonna take what's at position zero 97 97 00:03:52,000 --> 00:03:54,090 and assign it into position three. 98 98 00:03:54,090 --> 00:03:55,893 And then once we've done that, 99 99 00:03:57,850 --> 00:04:00,920 we wanna subract the gap from j 100 100 00:04:00,920 --> 00:04:05,602 because we're saying that now we're going to want to compare 101 101 00:04:05,602 --> 00:04:09,620 newElement with whatever comes three positions over. 102 102 00:04:09,620 --> 00:04:12,060 Well, we've hit the front of the array at this point. 103 103 00:04:12,060 --> 00:04:13,650 We'll loop and we'll say, 104 104 00:04:13,650 --> 00:04:15,910 well j has to be greater than or equal to the gap 105 105 00:04:15,910 --> 00:04:17,910 and it isn't because at this point, it's zero. 106 106 00:04:17,910 --> 00:04:21,060 And that's because there's no elements to the right here. 107 107 00:04:21,060 --> 00:04:23,710 So first, we wanna compare seven against 20. 108 108 00:04:23,710 --> 00:04:26,100 If we could, we'd then compare seven against 109 109 00:04:26,100 --> 00:04:28,400 whatever occurs three places in front of 20, 110 110 00:04:28,400 --> 00:04:29,360 but there is nothing. 111 111 00:04:29,360 --> 00:04:31,240 And so we're gonna drop out here. 112 112 00:04:31,240 --> 00:04:33,100 And what do we wanna do at this point? 113 113 00:04:33,100 --> 00:04:34,690 Just like with insertion sort, 114 114 00:04:34,690 --> 00:04:36,830 while we're basically saying we found 115 115 00:04:36,830 --> 00:04:40,230 the insertion point for seven when we drop out. 116 116 00:04:40,230 --> 00:04:43,160 And so we're going to assign intArray j 117 117 00:04:45,010 --> 00:04:46,480 with newElement. 118 118 00:04:46,480 --> 00:04:48,260 And this should look somewhat familiar 119 119 00:04:48,260 --> 00:04:49,370 because this is essentially 120 120 00:04:49,370 --> 00:04:51,550 what we were doing with insertion sort. 121 121 00:04:51,550 --> 00:04:53,510 And so, after we've done that, 122 122 00:04:53,510 --> 00:04:55,160 we loop back around to this loop 123 123 00:04:55,160 --> 00:04:57,230 and i would become four. 124 124 00:04:57,230 --> 00:04:59,090 So it would become 55. 125 125 00:04:59,090 --> 00:05:01,390 J would become four and then what would happen 126 126 00:05:01,390 --> 00:05:04,320 is it's gonna compare 55 against 35. 127 127 00:05:04,320 --> 00:05:05,850 And it's not gonna do anything 128 128 00:05:05,850 --> 00:05:08,570 because 55's greater than 35. 129 129 00:05:08,570 --> 00:05:10,260 And at that point, once again, 130 130 00:05:10,260 --> 00:05:12,220 it's gonna wanna jump ahead three places 131 131 00:05:12,220 --> 00:05:14,810 and there's nothing so we're gonna just loop around. 132 132 00:05:14,810 --> 00:05:16,330 I will become five, 133 133 00:05:16,330 --> 00:05:19,860 so it's gonna compare one against minus 15. 134 134 00:05:19,860 --> 00:05:22,910 And because one is greater than minus 15, 135 135 00:05:22,910 --> 00:05:24,980 it's not gonna do anything, it's gonna loop around. 136 136 00:05:24,980 --> 00:05:27,270 And once again, it's gonna wanna compare to whatever's 137 137 00:05:27,270 --> 00:05:29,470 three spaces over and there isn't anything, 138 138 00:05:29,470 --> 00:05:30,660 so we're gonna loop back. 139 139 00:05:30,660 --> 00:05:33,600 I will become six, so minus 22. 140 140 00:05:33,600 --> 00:05:36,850 We're gonna compare minus 22 against whatever's here. 141 141 00:05:36,850 --> 00:05:38,733 Now it's not seven anymore, it's 20 142 142 00:05:38,733 --> 00:05:40,960 because we moved 20 here. 143 143 00:05:40,960 --> 00:05:43,290 Minus 22 is less than 20, 144 144 00:05:43,290 --> 00:05:44,123 so 145 145 00:05:44,123 --> 00:05:46,780 we're gonna shift 20 here. 146 146 00:05:46,780 --> 00:05:49,000 And then we're gonna compare minus 22 147 147 00:05:49,000 --> 00:05:50,600 to whatever's three spaces over. 148 148 00:05:50,600 --> 00:05:52,310 And this time, we do have something 149 149 00:05:52,310 --> 00:05:54,010 three positions over. 150 150 00:05:54,010 --> 00:05:55,520 We actually have seven here 151 151 00:05:55,520 --> 00:05:57,310 because on the very first iteration, 152 152 00:05:57,310 --> 00:05:59,350 we moved seven to the front. 153 153 00:05:59,350 --> 00:06:01,430 Minus 22 is less than seven, 154 154 00:06:01,430 --> 00:06:04,560 so we'll shift seven back to where it was originally was 155 155 00:06:04,560 --> 00:06:06,670 and then at this point, it's gonna wanna compare 156 156 00:06:06,670 --> 00:06:09,220 three spaces over and there isn't anything. 157 157 00:06:09,220 --> 00:06:10,730 We've hit the front of the array 158 158 00:06:10,730 --> 00:06:12,880 and so we'll assign minus 22 here. 159 159 00:06:12,880 --> 00:06:14,700 And at that point, we'll loop around, 160 160 00:06:14,700 --> 00:06:18,590 i will become seven and it'll fail this condition. 161 161 00:06:18,590 --> 00:06:22,180 And so we'll drop out, loop back around to the gap loop. 162 162 00:06:22,180 --> 00:06:23,820 Reduce the gap to one 163 163 00:06:23,820 --> 00:06:26,620 and at this point, when we enter this code, 164 164 00:06:26,620 --> 00:06:29,230 we're essentially doing an insertion sort. 165 165 00:06:29,230 --> 00:06:30,640 And that's how 166 166 00:06:30,640 --> 00:06:33,760 shell sort optimises insertion sort. 167 167 00:06:33,760 --> 00:06:35,960 So let's run this to make sure it's working. 168 168 00:06:38,020 --> 00:06:39,440 And we get 169 169 00:06:39,440 --> 00:06:42,589 the usual minus 22, minus 15, 170 170 00:06:42,589 --> 00:06:43,801 one, seven, 171 171 00:06:43,801 --> 00:06:44,809 20, 172 172 00:06:44,809 --> 00:06:45,642 35, 173 173 00:06:45,642 --> 00:06:46,890 and 55. 174 174 00:06:46,890 --> 00:06:49,790 So let's go out to a couple of slides for a minute 175 175 00:06:49,790 --> 00:06:52,280 to compare the code for insertion sort 176 176 00:06:52,280 --> 00:06:54,023 with the code for shell sort. 177 177 00:06:58,010 --> 00:07:01,830 Okay, so here's the code that we wrote for insertion sort. 178 178 00:07:01,830 --> 00:07:03,630 And we can see that here we're starting 179 179 00:07:03,630 --> 00:07:05,610 with a the first unsorted index as one. 180 180 00:07:05,610 --> 00:07:09,870 We assign newElement with whatever's at that value. 181 181 00:07:09,870 --> 00:07:11,440 We have i and then of course, 182 182 00:07:11,440 --> 00:07:13,470 we loop through all the elements 183 183 00:07:13,470 --> 00:07:16,070 to the end of the array and if possible, 184 184 00:07:16,070 --> 00:07:18,100 we shift elements to the right. 185 185 00:07:18,100 --> 00:07:19,930 And if we drop out of this loop, 186 186 00:07:19,930 --> 00:07:23,050 then we have found the insertion position for newElements. 187 187 00:07:23,050 --> 00:07:25,640 So we assign newElement to i. 188 188 00:07:25,640 --> 00:07:27,130 Here's shell sort. 189 189 00:07:27,130 --> 00:07:29,370 And if you ignore this part for a minute, 190 190 00:07:29,370 --> 00:07:31,760 you'll see that this code is pretty much the same. 191 191 00:07:31,760 --> 00:07:34,360 The only difference is, instead of using one, 192 192 00:07:34,360 --> 00:07:36,330 we're using whatever the gap value is. 193 193 00:07:36,330 --> 00:07:39,500 So in the first iteration we're gonna use three. 194 194 00:07:39,500 --> 00:07:43,610 And once again, if we go back to insertion sort, 195 195 00:07:43,610 --> 00:07:45,510 we're gonna assign intArray 196 196 00:07:45,510 --> 00:07:48,120 first unsorted index to newElement. 197 197 00:07:48,120 --> 00:07:50,920 While in shell sort, we assign whatever's at i, 198 198 00:07:50,920 --> 00:07:53,230 the gap value to newElement. 199 199 00:07:53,230 --> 00:07:55,160 We assign i to j. 200 200 00:07:55,160 --> 00:07:57,260 It's pretty similar to what we're doing here 201 201 00:07:57,260 --> 00:08:00,120 except the loop is taking care of assigning i. 202 202 00:08:00,120 --> 00:08:02,080 Here, we need a different index 203 203 00:08:02,080 --> 00:08:06,860 because we don't wanna be changing i as we traverse 204 204 00:08:06,860 --> 00:08:08,890 the, not the sorted partition, 205 205 00:08:08,890 --> 00:08:11,570 but the part of the array that we're looking for 206 206 00:08:11,570 --> 00:08:13,480 in insertion position four. 207 207 00:08:13,480 --> 00:08:15,320 And then we say in shell sort, 208 208 00:08:15,320 --> 00:08:17,130 while j is great or equal to gap 209 209 00:08:17,130 --> 00:08:20,300 and intArray j minus gap is greater than newElement, 210 210 00:08:20,300 --> 00:08:23,840 as long as that's true, we're going to shift 211 211 00:08:23,840 --> 00:08:26,090 the elements that we're comparing against. 212 212 00:08:26,090 --> 00:08:30,080 We're gonna shift it up the array by gap positions 213 213 00:08:30,080 --> 00:08:33,500 and then we need to decrease the position 214 214 00:08:33,500 --> 00:08:36,670 of the next element that we look at by the gap 215 215 00:08:36,670 --> 00:08:38,520 because we always want to be looking at 216 216 00:08:38,520 --> 00:08:40,910 the element that's gap positions away. 217 217 00:08:40,910 --> 00:08:43,320 And this very similar to what we're doing here. 218 218 00:08:43,320 --> 00:08:44,450 We're saying the same thing, 219 219 00:08:44,450 --> 00:08:46,340 as long as we haven't hit the front. 220 220 00:08:46,340 --> 00:08:49,000 And this is saying, as long as we haven't hit the front 221 221 00:08:49,000 --> 00:08:52,290 and as long as the element we're looking at in the, 222 222 00:08:52,290 --> 00:08:53,951 for shell sort 223 223 00:08:53,951 --> 00:08:55,330 it's not really the sorted partition, 224 224 00:08:55,330 --> 00:08:58,350 but the element we're looking at that's gap positions away, 225 225 00:08:58,350 --> 00:08:59,840 is greater than newElement. 226 226 00:08:59,840 --> 00:09:01,170 And back in insertion sort, 227 227 00:09:01,170 --> 00:09:03,550 as long as the element we're looking at is greater than 228 228 00:09:03,550 --> 00:09:06,680 newElement, we wanna do the shifting. 229 229 00:09:06,680 --> 00:09:08,170 And here, we wanna do the shifting. 230 230 00:09:08,170 --> 00:09:10,150 And here, because we're using a gap, 231 231 00:09:10,150 --> 00:09:12,260 we have to calculate the next index 232 232 00:09:12,260 --> 00:09:14,230 we wanna look at differently. 233 233 00:09:14,230 --> 00:09:16,620 We can't just decrement it by one 234 234 00:09:16,620 --> 00:09:18,720 as we are with insertion sort 235 235 00:09:18,720 --> 00:09:20,920 because we're assuming a gap of one here. 236 236 00:09:20,920 --> 00:09:22,540 And then when we drop out of this loop, 237 237 00:09:22,540 --> 00:09:25,180 we assign newElement to intArray i. 238 238 00:09:25,180 --> 00:09:26,980 And here, when we drop out of the loop, 239 239 00:09:26,980 --> 00:09:29,600 we assign newElement to intArray j. 240 240 00:09:29,600 --> 00:09:33,910 So I think if you take a look at these two sets of code, 241 241 00:09:33,910 --> 00:09:36,680 here's insertion sort again and here's shell sort, 242 242 00:09:36,680 --> 00:09:39,580 you can see that we're doing the same thing 243 243 00:09:39,580 --> 00:09:42,230 inside here as we're doing with insertion sort. 244 244 00:09:42,230 --> 00:09:44,330 It's just that we're examining elements 245 245 00:09:44,330 --> 00:09:47,720 that are farther away, except on the final iteration. 246 246 00:09:47,720 --> 00:09:50,440 On the final iteration, when the gap is one, 247 247 00:09:50,440 --> 00:09:53,120 what we're doing in here is exactly the same thing 248 248 00:09:53,120 --> 00:09:54,780 as what we're doing in here. 249 249 00:09:54,780 --> 00:09:57,510 And so the final iteration when the gap is one, 250 250 00:09:57,510 --> 00:09:59,720 we're essentially doing it in insertion sort. 251 251 00:09:59,720 --> 00:10:01,580 And that's what shell sort does, 252 252 00:10:01,580 --> 00:10:03,370 but of course, with shell sort, 253 253 00:10:03,370 --> 00:10:06,570 in the final iteration we've already moved 254 254 00:10:06,570 --> 00:10:10,190 several of the elements closer to their sorted positions 255 255 00:10:10,190 --> 00:10:12,280 and so there's going to be a lot less shifting 256 256 00:10:12,280 --> 00:10:13,520 that has to take place. 257 257 00:10:13,520 --> 00:10:15,720 And that's how shell sort improves 258 258 00:10:15,720 --> 00:10:17,460 on the insertion sort algorithm. 259 259 00:10:17,460 --> 00:10:20,220 And as I mentioned, you can also use the same idea 260 260 00:10:20,220 --> 00:10:21,960 to improve on bubble sort. 261 261 00:10:21,960 --> 00:10:24,510 You do some preliminary work. 262 262 00:10:24,510 --> 00:10:27,300 So instead of examining neighbours and swapping them, 263 263 00:10:27,300 --> 00:10:29,760 you'll exam elements that are further apart 264 264 00:10:29,760 --> 00:10:31,570 and swap them if necessary. 265 265 00:10:31,570 --> 00:10:33,850 And so by the time you get down to the bubble sort 266 266 00:10:33,850 --> 00:10:35,900 where you're using a gap of one, 267 267 00:10:35,900 --> 00:10:37,800 there'll be a lot less swapping to do. 268 268 00:10:37,800 --> 00:10:39,080 So that's shell sort. 269 269 00:10:39,080 --> 00:10:42,060 That's what the shell sort algorithm does 270 270 00:10:42,060 --> 00:10:46,400 for insertion sort and it can also do it for bubble sort. 271 271 00:10:46,400 --> 00:10:47,950 I'll see you in the next video. 22633