Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,218 --> 00:00:05,218 (lively music) (keyboard clacking) 2 2 00:00:05,900 --> 00:00:07,480 So, let's implement Selection Sort. 3 3 00:00:07,480 --> 00:00:10,380 Now as I said, when I implemented bubble sort, 4 4 00:00:10,380 --> 00:00:13,390 I'm not going to create the projects on screen anymore, 5 5 00:00:13,390 --> 00:00:15,070 so I've created a new project, 6 6 00:00:15,070 --> 00:00:16,650 I'm putting the code into package 7 7 00:00:16,650 --> 00:00:19,460 academy.learnprogramming.selectionsort. 8 8 00:00:19,460 --> 00:00:22,360 I've added our array, I've added the code 9 9 00:00:22,360 --> 00:00:25,240 to print the array and I've added the swap method 10 10 00:00:25,240 --> 00:00:27,370 that I wrote in the bubble sort video, 11 11 00:00:27,370 --> 00:00:29,150 so if you didn't watch that video 12 12 00:00:29,150 --> 00:00:31,890 or you need a review of what this method is doing, 13 13 00:00:31,890 --> 00:00:33,610 you can go back and watch that video, 14 14 00:00:33,610 --> 00:00:36,250 so let's get cracking on selection sort. 15 15 00:00:36,250 --> 00:00:39,640 So, we're gonna say for int lastUnsortedIndex 16 16 00:00:42,994 --> 00:00:46,469 equals and once again, this will be intArray.length 17 17 00:00:46,469 --> 00:00:50,608 minus one because at the beginning of the implementation, 18 18 00:00:50,608 --> 00:00:53,269 the entire array is unsorted, 19 19 00:00:53,269 --> 00:00:54,770 it's in the unsorted partition 20 20 00:00:54,770 --> 00:00:59,480 and so, the lastUnsortedIndex will be the last valid index 21 21 00:00:59,480 --> 00:01:01,170 in the array which is six. 22 22 00:01:01,170 --> 00:01:02,593 Now it's length minus one. 23 23 00:01:03,670 --> 00:01:05,570 And we wanna keep going 24 24 00:01:06,570 --> 00:01:09,970 as long as the lastUnsortedIndex is greater than zero. 25 25 00:01:09,970 --> 00:01:12,900 Once it hits zero, that means the entire array is sorted 26 26 00:01:12,900 --> 00:01:16,090 and we're going to decrement this on each iteration, 27 27 00:01:16,090 --> 00:01:17,820 so this is starting out exactly 28 28 00:01:17,820 --> 00:01:20,940 the same way bubble sort started. 29 29 00:01:20,940 --> 00:01:25,930 So, we're gonna initialise our largest index to zero, 30 30 00:01:25,930 --> 00:01:29,700 so right now we're saying that in the unsorted partition, 31 31 00:01:29,700 --> 00:01:31,970 the largest element is at position zero 32 32 00:01:31,970 --> 00:01:33,970 'cause we haven't actually looked at anything yet 33 33 00:01:33,970 --> 00:01:37,760 and then we're gonna say for int i equals one, 34 34 00:01:37,760 --> 00:01:42,760 i is less than or equal to the lastUnsortedIndex, 35 35 00:01:42,810 --> 00:01:47,010 i++ and what we wanna do 36 36 00:01:47,010 --> 00:01:50,420 is we want to traverse the unsorted partition 37 37 00:01:50,420 --> 00:01:52,920 and look for the largest element, 38 38 00:01:52,920 --> 00:01:54,520 so we're going to start at one 39 39 00:01:54,520 --> 00:01:56,540 'cause we've initialised largest to zero, 40 40 00:01:56,540 --> 00:02:00,370 so we wanna say is the element at position one greater 41 41 00:02:00,370 --> 00:02:02,820 than the largest element that we know about so far? 42 42 00:02:02,820 --> 00:02:05,250 Because if it is, then we need to update largest 43 43 00:02:05,250 --> 00:02:07,880 and we're gonna do that until we hit the end 44 44 00:02:07,880 --> 00:02:09,720 of the unsorted partition. 45 45 00:02:09,720 --> 00:02:11,220 Now, unlike with bubble sort, 46 46 00:02:11,220 --> 00:02:14,980 we do need to check the element in the last position, 47 47 00:02:14,980 --> 00:02:17,910 in bubble sort, we didn't need the equals 48 48 00:02:17,910 --> 00:02:21,350 because we were comparing i against i plus one 49 49 00:02:21,350 --> 00:02:23,800 and so, the last index we wanted to check 50 50 00:02:23,800 --> 00:02:26,900 was lastUnsortedIndex minus one 51 51 00:02:26,900 --> 00:02:29,080 against lastUnsortedIndex 52 52 00:02:29,080 --> 00:02:31,990 but here we wanna compare every element 53 53 00:02:31,990 --> 00:02:33,130 against whatever's largest, 54 54 00:02:33,130 --> 00:02:35,540 so we need to compare this last element as well. 55 55 00:02:35,540 --> 00:02:37,880 So, that's what the equals is doing here 56 56 00:02:37,880 --> 00:02:39,630 and so, that's what we wanna do. 57 57 00:02:39,630 --> 00:02:41,850 We wanna say if intArray i 58 58 00:02:43,040 --> 00:02:46,850 is greater than intArray largest 59 59 00:02:46,850 --> 00:02:50,430 because that's the largest element we know about so far, 60 60 00:02:50,430 --> 00:02:53,480 then we wanna update largest to i. 61 61 00:02:53,480 --> 00:02:56,630 So, we're gonna compare 35 against 20 62 62 00:02:56,630 --> 00:02:58,940 on this first iteration. 63 63 00:02:58,940 --> 00:03:00,690 35 is bigger than 20 64 64 00:03:00,690 --> 00:03:03,440 and so, largest is gonna get updated to one 65 65 00:03:03,440 --> 00:03:04,760 and then on the next iteration, 66 66 00:03:04,760 --> 00:03:06,970 we're gonna be comparing against 35 67 67 00:03:06,970 --> 00:03:09,720 because that's the largest element we found so far. 68 68 00:03:09,720 --> 00:03:11,970 So, once we drop out of this loop, 69 69 00:03:11,970 --> 00:03:13,040 what do we wanna do? 70 70 00:03:13,040 --> 00:03:17,000 Well, we wanna swap the largest element that we found 71 71 00:03:17,000 --> 00:03:20,570 with the last element in the unsorted partition, 72 72 00:03:20,570 --> 00:03:23,863 so with the element that's sitting at lastUnsortedIndex. 73 73 00:03:25,520 --> 00:03:29,540 And so, we can use our handy swap method to do that, 74 74 00:03:29,540 --> 00:03:31,860 so we'll pass intArray 75 75 00:03:31,860 --> 00:03:36,783 and we'll pass largest and lastUnsortedIndex. 76 76 00:03:39,230 --> 00:03:40,063 And that's it. 77 77 00:03:40,063 --> 00:03:42,570 We have implemented selection sort. 78 78 00:03:42,570 --> 00:03:45,680 So, once again, if you're having trouble understanding this, 79 79 00:03:45,680 --> 00:03:47,150 review the last video 80 80 00:03:47,150 --> 00:03:49,530 where we go through this by hand with the slide. 81 81 00:03:49,530 --> 00:03:53,110 So, the outer loop is the one that's increasing 82 82 00:03:53,110 --> 00:03:55,070 the sorted partition by one, 83 83 00:03:55,070 --> 00:03:57,020 it's growing it from right to left 84 84 00:03:57,020 --> 00:03:58,580 and the inner loop is the one 85 85 00:03:58,580 --> 00:04:01,000 that's looking for the largest element 86 86 00:04:01,000 --> 00:04:02,970 and then once we've looked at all the elements 87 87 00:04:02,970 --> 00:04:04,830 and we know which one is the largest, 88 88 00:04:04,830 --> 00:04:07,780 at that point, we're gonna swap the largest element 89 89 00:04:07,780 --> 00:04:11,220 with the last element in the unsorted partition 90 90 00:04:11,220 --> 00:04:13,390 and when we look back around, 91 91 00:04:13,390 --> 00:04:14,470 of course at that point, 92 92 00:04:14,470 --> 00:04:17,140 we have grown the sorted partition by one 93 93 00:04:17,140 --> 00:04:20,240 and so, we subtract one from the lastUnsortedIndex. 94 94 00:04:20,240 --> 00:04:23,343 So, let's run this, let's see if this actually works. 95 95 00:04:26,540 --> 00:04:27,430 And it does. 96 96 00:04:27,430 --> 00:04:28,630 Here's our sorted array. 97 97 00:04:28,630 --> 00:04:33,337 Minus 22, minus 15, one, seven, 20, 35 and 55. 98 98 00:04:34,480 --> 00:04:36,253 And I'll just close this off. 99 99 00:04:37,140 --> 00:04:39,830 Now as I said, this is a quadratic algorithm, 100 100 00:04:39,830 --> 00:04:40,880 O to the n squared 101 101 00:04:40,880 --> 00:04:42,530 and once again, we have two loops 102 102 00:04:42,530 --> 00:04:44,070 and I said that that's a hint 103 103 00:04:44,070 --> 00:04:47,160 because usually each loop can be considered n 104 104 00:04:47,160 --> 00:04:49,440 and so, we have n times n 105 105 00:04:49,440 --> 00:04:51,770 and that gives us O to the n squared. 106 106 00:04:51,770 --> 00:04:54,070 So, that's selection sort. 107 107 00:04:54,070 --> 00:04:56,010 On each traversal of the array, 108 108 00:04:56,010 --> 00:04:57,720 it selects the largest value 109 109 00:04:57,720 --> 00:05:00,580 and it adds it into the sorted partition. 110 110 00:05:00,580 --> 00:05:02,143 I'll see you in the next video. 9410