Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,138 --> 00:00:02,721 (techno music) 2 2 00:00:05,330 --> 00:00:06,400 All right, so in this video, 3 3 00:00:06,400 --> 00:00:09,840 we're going to take a look at the selection sort algorithm. 4 4 00:00:09,840 --> 00:00:12,050 Now this algorithm divides the array 5 5 00:00:12,050 --> 00:00:14,330 into sorted and unsorted partitions 6 6 00:00:14,330 --> 00:00:16,030 just like bubble sort does. 7 7 00:00:16,030 --> 00:00:18,657 And what we do is we traverse the array 8 8 00:00:18,657 --> 00:00:21,050 and we look for the largest element 9 9 00:00:21,050 --> 00:00:22,900 in the unsorted partition. 10 10 00:00:22,900 --> 00:00:24,590 And when we find it, 11 11 00:00:24,590 --> 00:00:29,080 we swap it with the last element in the unsorted partition. 12 12 00:00:29,080 --> 00:00:31,070 And at that point, 13 13 00:00:31,070 --> 00:00:35,110 that swapped element will be its correct sorted position. 14 14 00:00:35,110 --> 00:00:36,620 And so just like with bubble sort, 15 15 00:00:36,620 --> 00:00:38,160 at the beginning of the algorithm, 16 16 00:00:38,160 --> 00:00:40,470 the entire array is unsorted 17 17 00:00:40,470 --> 00:00:43,010 so the last unsorted index is six 18 18 00:00:43,010 --> 00:00:44,490 and just like with bubble sort 19 19 00:00:44,490 --> 00:00:48,410 we're going to grow the sorted partition from right to left. 20 20 00:00:48,410 --> 00:00:52,360 We're going to initialise a largest field to zero 21 21 00:00:52,360 --> 00:00:54,520 so when we start we say you know what, 22 22 00:00:54,520 --> 00:00:58,600 20 is the largest element that we know about so far, 23 23 00:00:58,600 --> 00:01:02,129 so whatever is at position zero will be the largest element. 24 24 00:01:02,129 --> 00:01:04,120 And we're going to start 25 25 00:01:04,120 --> 00:01:07,550 by comparing the element at position one 26 26 00:01:07,550 --> 00:01:09,030 to whatever is at position zero, 27 27 00:01:09,030 --> 00:01:11,190 so we're gonna start with i equal to one. 28 28 00:01:11,190 --> 00:01:15,260 We're going to use i to traverse the unsorted partition 29 29 00:01:15,260 --> 00:01:17,830 and find the largest element 30 30 00:01:17,830 --> 00:01:20,130 and so these are our initial values. 31 31 00:01:20,130 --> 00:01:22,090 The last unsorted index is six 32 32 00:01:22,090 --> 00:01:25,550 because the entire array is unsorted, i is one. 33 33 00:01:25,550 --> 00:01:27,650 We're gonna start our traversal here 34 34 00:01:27,650 --> 00:01:30,070 and we've initialised the largest. 35 35 00:01:30,070 --> 00:01:33,220 The largest will contain the index of the largest element. 36 36 00:01:33,220 --> 00:01:36,840 Then the unsorted partition, that's initialised to zero. 37 37 00:01:36,840 --> 00:01:40,440 So we're going to compare 35 to 20 and we're gonna say hey, 38 38 00:01:40,440 --> 00:01:43,110 35 is larger than 20 and because of that, 39 39 00:01:43,110 --> 00:01:45,450 we're going to change largest to one 40 40 00:01:45,450 --> 00:01:48,080 and then we're gonna increment i to two 41 41 00:01:48,080 --> 00:01:52,550 and we're gonna compare minus 15 to the largest element 42 42 00:01:52,550 --> 00:01:53,800 which is now at position one 43 43 00:01:53,800 --> 00:01:57,230 and we're gonna say well minus 15 is less than 35 44 44 00:01:57,230 --> 00:01:59,460 so we're just gonna increment i to three. 45 45 00:01:59,460 --> 00:02:02,080 We're gonna compare seven to the largest element 46 46 00:02:02,080 --> 00:02:03,880 which is still at position one. 47 47 00:02:03,880 --> 00:02:08,020 Seven is less than 35 so we just increment i to four. 48 48 00:02:08,020 --> 00:02:11,150 We're now gonna compare 55 to 35 49 49 00:02:11,150 --> 00:02:14,010 and 55 is greater than 35 50 50 00:02:14,010 --> 00:02:17,760 so at this point we're going to change largest to four 51 51 00:02:17,760 --> 00:02:21,010 because the largest element we found so far 52 52 00:02:21,010 --> 00:02:23,800 in the unsorted partition is at index four 53 53 00:02:23,800 --> 00:02:26,240 and we increment i to five. 54 54 00:02:26,240 --> 00:02:28,250 We compare one to 55. 55 55 00:02:28,250 --> 00:02:32,530 Well, one is less than 55 so we just increment i to six. 56 56 00:02:32,530 --> 00:02:35,090 We compare minus 22 to 55. 57 57 00:02:35,090 --> 00:02:38,780 Minus 22 is less than 55 so we don't do anything. 58 58 00:02:38,780 --> 00:02:43,140 And at this point, i is equal to the last unsorted index 59 59 00:02:43,140 --> 00:02:46,760 and so we have completed our first traversal of the array. 60 60 00:02:46,760 --> 00:02:48,910 So we're going to swap the largest element 61 61 00:02:48,910 --> 00:02:50,800 that we found in the unsorted partition 62 62 00:02:50,800 --> 00:02:54,220 and that's at position four with the last element 63 63 00:02:54,220 --> 00:02:56,890 in the unsorted partition and that's at position six. 64 64 00:02:56,890 --> 00:02:59,980 So what we're gonna do is swap 55 and minus 22 65 65 00:02:59,980 --> 00:03:02,547 and we have now completed our first traversal. 66 66 00:03:02,547 --> 00:03:07,460 And at this point, 55 is in its correct sorted position 67 67 00:03:07,460 --> 00:03:10,920 and so we're gonna decrement last unsorted index to five 68 68 00:03:10,920 --> 00:03:13,470 and we're gonna re-initialize i to one 69 69 00:03:13,470 --> 00:03:15,370 and we're going to say the largest element 70 70 00:03:15,370 --> 00:03:18,780 in the unsorted partition is at position zero 71 71 00:03:18,780 --> 00:03:20,360 and we repeat the process. 72 72 00:03:20,360 --> 00:03:23,100 So we're going to compare 35 against 20. 73 73 00:03:23,100 --> 00:03:27,300 35 is greater than 20 so we're gonna set largest to one. 74 74 00:03:27,300 --> 00:03:29,360 Now we increment i to two 75 75 00:03:29,360 --> 00:03:32,310 and we compare minus 15 against 35 76 76 00:03:32,310 --> 00:03:34,740 'cause 35 is now the largest element. 77 77 00:03:34,740 --> 00:03:38,700 Minus 15 is less than 35 so we just increment i to three. 78 78 00:03:38,700 --> 00:03:42,720 Seven is less than 35 so we just increment i to four. 79 79 00:03:42,720 --> 00:03:47,370 Minus 22 is less than 35 so we just increment i to five 80 80 00:03:47,370 --> 00:03:51,090 and of course one is less than 35 and at this point, 81 81 00:03:51,090 --> 00:03:53,530 i equals the last unsorted index 82 82 00:03:53,530 --> 00:03:56,400 so we have completed our second traversal of the array. 83 83 00:03:56,400 --> 00:03:58,010 And what we wanna do at this point 84 84 00:03:58,010 --> 00:04:02,440 is swap the largest element, which is at position one, 85 85 00:04:02,440 --> 00:04:06,330 with the last element in the unsorted partition, 86 86 00:04:06,330 --> 00:04:08,340 which is at index five, 87 87 00:04:08,340 --> 00:04:11,580 and so we're going to swap 35 and one. 88 88 00:04:11,580 --> 00:04:13,320 And at this point, 89 89 00:04:13,320 --> 00:04:18,240 35 and 55 are in their correct sorted positions 90 90 00:04:18,240 --> 00:04:22,990 and we decrement the last unsorted index 91 91 00:04:22,990 --> 00:04:25,910 and so now the last unsorted index 92 92 00:04:25,910 --> 00:04:28,500 of the unsorted partition is four 93 93 00:04:28,500 --> 00:04:32,600 and we would re-initialize largest to zero 94 94 00:04:32,600 --> 00:04:34,270 and that should be a one. 95 95 00:04:34,270 --> 00:04:37,890 We should re-initialize i to one. 96 96 00:04:37,890 --> 00:04:39,650 And we're just gonna repeat the process. 97 97 00:04:39,650 --> 00:04:41,560 We're gonna compare one to 20, 98 98 00:04:41,560 --> 00:04:44,330 largest is gonna remain zero, et cetera, 99 99 00:04:44,330 --> 00:04:46,210 until the entire array is sorted 100 100 00:04:46,210 --> 00:04:48,190 and so this is how selection sort works 101 101 00:04:48,190 --> 00:04:50,990 and it's called selection sort because on each traversal 102 102 00:04:50,990 --> 00:04:53,080 where it's selecting the largest element 103 103 00:04:53,080 --> 00:04:56,150 and removing it into the sorted partition. 104 104 00:04:56,150 --> 00:04:58,900 So selection sort is an in-place algorithm. 105 105 00:04:58,900 --> 00:05:00,610 It doesn't use any extra memory. 106 106 00:05:00,610 --> 00:05:01,970 As I said with bubble sort, 107 107 00:05:01,970 --> 00:05:04,130 it's okay to use a few extra fields 108 108 00:05:04,130 --> 00:05:06,470 as long as the extra memory you're using 109 109 00:05:06,470 --> 00:05:09,260 doesn't depend on the number of items you're sorting, 110 110 00:05:09,260 --> 00:05:11,160 it's an in-place algorithm. 111 111 00:05:11,160 --> 00:05:13,330 It's a quadratic algorithm 112 112 00:05:13,330 --> 00:05:16,460 so it has a time complexity of O to the n squared 113 113 00:05:16,460 --> 00:05:20,220 because we have n elements in the array 114 114 00:05:20,220 --> 00:05:23,770 and for each element we traverse n elements, 115 115 00:05:23,770 --> 00:05:25,820 so it's quadratic. 116 116 00:05:25,820 --> 00:05:29,190 However, it doesn't require as much swapping as bubble sort. 117 117 00:05:29,190 --> 00:05:33,160 You'll notice that we only swap once per traversal 118 118 00:05:33,160 --> 00:05:36,780 and so selection sort will usually perform better 119 119 00:05:36,780 --> 00:05:37,640 than bubble sort. 120 120 00:05:37,640 --> 00:05:40,340 I say usually because depending on 121 121 00:05:40,340 --> 00:05:42,620 you might have an array that's almost sorted 122 122 00:05:42,620 --> 00:05:44,930 and so bubble sort doesn't have to swap that much, 123 123 00:05:44,930 --> 00:05:48,330 but in the average case, all other things being equal, 124 124 00:05:48,330 --> 00:05:50,630 generally selection sort will perform better. 125 125 00:05:50,630 --> 00:05:54,240 However, selection sort is an unstable algorithm 126 126 00:05:54,240 --> 00:05:55,580 and you can see why, right? 127 127 00:05:55,580 --> 00:05:58,120 Because if we have duplicate elements, 128 128 00:05:58,120 --> 00:06:00,710 there's no guarantee that their original order 129 129 00:06:00,710 --> 00:06:02,980 relative to each other will be preserved 130 130 00:06:02,980 --> 00:06:04,080 because on each pass, 131 131 00:06:04,080 --> 00:06:06,140 we swapped the largest element 132 132 00:06:06,140 --> 00:06:08,890 with whatever is occupying the last position 133 133 00:06:08,890 --> 00:06:10,370 in the unsorted partition 134 134 00:06:10,370 --> 00:06:12,890 and so it's very possible 135 135 00:06:12,890 --> 00:06:15,290 that we could take the second duplicate value 136 136 00:06:15,290 --> 00:06:18,230 and move it in front of its twin. 137 137 00:06:18,230 --> 00:06:21,800 So because of that, selection sort is an unstable algorithm. 138 138 00:06:21,800 --> 00:06:24,330 So if you need a stable sort algorithm, 139 139 00:06:24,330 --> 00:06:26,650 then you don't wanna be using selection sort. 140 140 00:06:26,650 --> 00:06:29,200 Okay, so that's it for the theory. 141 141 00:06:29,200 --> 00:06:31,680 Let's move on and implement selection sort. 142 142 00:06:31,680 --> 00:06:33,180 Ill see you in the next video. 12440