1 00:00:00,730 --> 00:00:01,750 Welcome back. 2 00:00:01,750 --> 00:00:07,060 Let's now go ahead and write the code to implement the selection sort, which we have discussed in the 3 00:00:07,060 --> 00:00:07,930 previous video. 4 00:00:07,930 --> 00:00:09,700 Now again for this we need a function. 5 00:00:09,700 --> 00:00:12,610 Let's call this function selection sort itself. 6 00:00:14,060 --> 00:00:17,630 Now this function is going to take in the array which is given to us. 7 00:00:17,630 --> 00:00:19,760 And let's call this array numb's. 8 00:00:21,580 --> 00:00:26,830 Now inside the function, what we are going to do is we're going to have a for loop and we'll have two 9 00:00:26,830 --> 00:00:28,150 pointers I and J. 10 00:00:28,180 --> 00:00:34,060 So let I is equal to zero I less than numb's dot length. 11 00:00:36,420 --> 00:00:37,590 I plus, plus. 12 00:00:39,250 --> 00:00:43,720 So we are using AI to traverse or iterate through the array which is given to us. 13 00:00:43,720 --> 00:00:45,550 And now let's have a variable. 14 00:00:45,550 --> 00:00:52,810 Let's call it smallest, because we have to identify the index of the smallest in every pass through 15 00:00:52,810 --> 00:00:53,350 the array. 16 00:00:53,350 --> 00:00:57,340 And then as we discussed, we are going to move the smallest to the friend. 17 00:00:57,340 --> 00:00:59,620 So that's how we are going to implement this. 18 00:00:59,620 --> 00:01:02,620 So initially let the smallest be equal to I. 19 00:01:03,890 --> 00:01:06,470 And then we'll have one more nested for loop over here. 20 00:01:06,470 --> 00:01:13,190 So for let j is equal to I plus one j less than. 21 00:01:14,610 --> 00:01:16,080 Numb's dot length. 22 00:01:18,680 --> 00:01:19,970 J plus plus. 23 00:01:21,410 --> 00:01:26,780 So we are going to check whether numb's at J is less than numb's at smallest. 24 00:01:26,780 --> 00:01:29,600 So if numb's at J. 25 00:01:31,300 --> 00:01:33,640 Less than Numb's at smallest. 26 00:01:36,020 --> 00:01:40,400 If this is the case, then we have to reassign smallest to j. 27 00:01:40,400 --> 00:01:43,220 So we can say smallest is equal to j. 28 00:01:43,820 --> 00:01:44,240 All right. 29 00:01:44,240 --> 00:01:49,850 So once you are out of this so for one value of I we are traversing through the remaining part of the 30 00:01:49,850 --> 00:01:50,210 array. 31 00:01:50,210 --> 00:01:53,870 And we are identifying the lowest value starting from I. 32 00:01:53,870 --> 00:01:54,260 All right. 33 00:01:54,260 --> 00:02:01,670 So once we have identified the smallest now we will just check if I is not equal to the smallest. 34 00:02:02,430 --> 00:02:02,820 Right. 35 00:02:02,820 --> 00:02:05,880 So that means that another index is the smallest. 36 00:02:05,880 --> 00:02:08,850 And then we have to swap I with j with smallest. 37 00:02:08,850 --> 00:02:12,600 So in this case we have to swap I and smallest. 38 00:02:13,410 --> 00:02:13,830 All right. 39 00:02:13,830 --> 00:02:14,700 So let's do that. 40 00:02:14,700 --> 00:02:16,230 So let's use a temporary variable. 41 00:02:16,230 --> 00:02:19,020 So let temp is equal to numb's at I. 42 00:02:20,520 --> 00:02:26,460 And then we can say numb's at I is equal to numb's at smallest. 43 00:02:28,500 --> 00:02:33,690 And numb's at smallest is equal to temp. 44 00:02:34,440 --> 00:02:35,280 And that's it. 45 00:02:35,310 --> 00:02:39,180 Now once we're out of this for loop we just have to return the array. 46 00:02:39,210 --> 00:02:40,440 So return numb's. 47 00:02:40,830 --> 00:02:43,080 And that's the implementation of the selection sort. 48 00:02:43,110 --> 00:02:45,420 Now let's go ahead and test our code. 49 00:02:45,450 --> 00:02:46,830 So let me just run it. 50 00:02:46,830 --> 00:02:48,930 So for this we'll call our function. 51 00:02:48,930 --> 00:02:50,580 And let's pass in an array to it. 52 00:02:50,610 --> 00:02:53,400 Let's say we have 432 and one. 53 00:02:53,910 --> 00:02:55,590 And let's run our code. 54 00:02:57,460 --> 00:03:00,370 And you can see, yes, we are getting one, two, three, four which is sorted. 55 00:03:00,370 --> 00:03:00,700 Right. 56 00:03:00,700 --> 00:03:01,540 So that's working. 57 00:03:01,540 --> 00:03:02,650 Let's try another array. 58 00:03:02,650 --> 00:03:07,870 So let's say we have five over here and we get 12345. 59 00:03:07,870 --> 00:03:10,180 And what if we have duplicate elements. 60 00:03:10,180 --> 00:03:11,650 Let's say we have two also over here. 61 00:03:11,860 --> 00:03:14,080 Then we get 122345. 62 00:03:14,080 --> 00:03:16,420 So yes our selection sort is working. 63 00:03:16,420 --> 00:03:20,650 Now let's take this example and let's just walk through the uh code. 64 00:03:20,650 --> 00:03:23,860 So let me just make this smaller so that it's easy to walk through. 65 00:03:23,860 --> 00:03:27,460 So let's say four three, one and five is given to us. 66 00:03:27,460 --> 00:03:29,470 We can see we are getting one, three, four, five. 67 00:03:29,470 --> 00:03:31,240 So let's see what's happening over here. 68 00:03:31,240 --> 00:03:33,310 So let me grab a pen for this. 69 00:03:34,970 --> 00:03:35,420 All right. 70 00:03:35,420 --> 00:03:40,580 So this is the array 431 and five which is given to us. 71 00:03:40,580 --> 00:03:42,260 And let's write the indices. 72 00:03:42,260 --> 00:03:45,800 So we have 012 and three over here. 73 00:03:45,800 --> 00:03:48,980 Now when we call the function first I is going to point to here. 74 00:03:48,980 --> 00:03:50,480 So I is equal to zero. 75 00:03:50,480 --> 00:03:53,060 And we are inside the for loop. 76 00:03:53,060 --> 00:03:55,760 Now smallest is going to be equal to I which is zero. 77 00:03:55,760 --> 00:03:56,750 So smallest. 78 00:03:58,680 --> 00:03:59,910 Is equal to zero. 79 00:03:59,910 --> 00:04:02,100 And then we have this for loop over here. 80 00:04:02,100 --> 00:04:06,540 So J is going to be equal to I plus one which is zero plus one which is equal to one. 81 00:04:06,540 --> 00:04:07,770 So j is over here. 82 00:04:08,130 --> 00:04:14,580 And then we are checking is numb's at j which is three is three less than numb's at smallest which is 83 00:04:14,580 --> 00:04:15,120 four. 84 00:04:15,150 --> 00:04:16,890 Yes three is less than four. 85 00:04:16,890 --> 00:04:19,980 So we are going to change smallest to j which is one. 86 00:04:19,980 --> 00:04:21,720 So smallest becomes one. 87 00:04:21,720 --> 00:04:23,640 And then again j moves forward. 88 00:04:23,640 --> 00:04:25,080 So J comes over here. 89 00:04:25,080 --> 00:04:31,050 And then we are checking is numb's at j which is one is one less than numb's at smallest which is three. 90 00:04:31,050 --> 00:04:32,310 Yes one is less than three. 91 00:04:32,310 --> 00:04:35,940 So we are going to say smallest is equal to j which is two over here. 92 00:04:35,940 --> 00:04:36,240 Right. 93 00:04:36,240 --> 00:04:38,430 So smallest is going to be equal to two. 94 00:04:38,430 --> 00:04:41,670 And then again we come over here we move j forward. 95 00:04:42,000 --> 00:04:48,780 And then we are checking is numb's at J which is five is five less than numb's at two which is smallest. 96 00:04:48,780 --> 00:04:48,960 Right. 97 00:04:48,960 --> 00:04:50,700 So numb's at smallest is one. 98 00:04:50,700 --> 00:04:51,960 Is five less than one. 99 00:04:51,960 --> 00:04:53,160 No that's not the case. 100 00:04:53,160 --> 00:04:54,750 So we don't update smallest. 101 00:04:54,750 --> 00:04:58,560 And then we come out and over here we are going to check I is equal to zero. 102 00:04:59,160 --> 00:05:01,800 And we are checking whether I is equal to smallest. 103 00:05:01,830 --> 00:05:03,120 No it's not equal right. 104 00:05:03,120 --> 00:05:04,710 So I is not equal to smallest. 105 00:05:04,710 --> 00:05:11,820 So we come inside and we are going to swap the values at I which is four and the value at index smallest 106 00:05:11,820 --> 00:05:12,780 which is two. 107 00:05:12,810 --> 00:05:14,940 So these two values are going to be swapped. 108 00:05:14,940 --> 00:05:19,050 So the array becomes 134 and five. 109 00:05:19,500 --> 00:05:20,910 So this is after one pass. 110 00:05:20,910 --> 00:05:24,540 Now again we come over here and I is going to be incremented. 111 00:05:24,540 --> 00:05:25,860 So I is going to be equal to one. 112 00:05:25,860 --> 00:05:26,760 So this is I. 113 00:05:27,890 --> 00:05:29,930 And again smallest is equal to I. 114 00:05:29,960 --> 00:05:32,780 So smallest is equal to and again this index is one right. 115 00:05:32,870 --> 00:05:34,970 So this is 012 and three. 116 00:05:34,970 --> 00:05:37,100 So smallest is going to be equal to one. 117 00:05:39,880 --> 00:05:40,360 All right. 118 00:05:40,360 --> 00:05:44,530 And then over here, when we come over here, we say j is equal to I plus one. 119 00:05:44,530 --> 00:05:46,900 So let me just clean this up a little bit. 120 00:05:46,930 --> 00:05:49,000 So I j is equal to I plus one. 121 00:05:49,000 --> 00:05:52,570 So we get j is equal to one plus one which is two. 122 00:05:52,600 --> 00:05:54,820 So j is equal to two index two. 123 00:05:54,850 --> 00:05:55,870 So j is over here. 124 00:05:55,870 --> 00:06:02,140 And then we come over here and we are checking is numb's at J which is four is four less than numb's 125 00:06:02,140 --> 00:06:02,980 at smallest. 126 00:06:02,980 --> 00:06:05,260 Smallest is one at one we have three. 127 00:06:05,260 --> 00:06:06,340 Is four less than three. 128 00:06:06,340 --> 00:06:07,720 No that's not the case. 129 00:06:07,720 --> 00:06:10,090 So again we come over here and J is moved ahead. 130 00:06:10,090 --> 00:06:13,900 So we come over here and then J is pointing to five. 131 00:06:13,900 --> 00:06:16,180 Again we check is five less than three. 132 00:06:16,180 --> 00:06:17,260 No that's not the case. 133 00:06:17,260 --> 00:06:20,440 So when we come over here we will see that I is equal to one. 134 00:06:20,440 --> 00:06:22,900 And smallest is also equal to one. 135 00:06:22,900 --> 00:06:23,980 So we don't swap. 136 00:06:23,980 --> 00:06:25,840 We don't come inside over here again. 137 00:06:25,840 --> 00:06:27,970 When we come over here we're going to increment I. 138 00:06:28,950 --> 00:06:31,380 So I now is going to point to two. 139 00:06:32,400 --> 00:06:34,380 Let me just clean this up a little bit. 140 00:06:34,860 --> 00:06:36,870 So I is going to point to two. 141 00:06:36,900 --> 00:06:38,520 So we have I over here. 142 00:06:38,520 --> 00:06:41,880 And then again we say smallest is equal to two. 143 00:06:42,210 --> 00:06:42,750 All right. 144 00:06:42,750 --> 00:06:45,360 We come over here J is going to be equal to three. 145 00:06:45,600 --> 00:06:48,810 Now we are again checking is five less than four. 146 00:06:48,810 --> 00:06:50,040 No that's not the case. 147 00:06:50,040 --> 00:06:51,360 So we don't change this. 148 00:06:51,390 --> 00:06:53,880 We come and then we don't have anything. 149 00:06:53,880 --> 00:06:55,260 J does not have any more place. 150 00:06:55,260 --> 00:06:55,470 Right. 151 00:06:55,470 --> 00:06:57,210 So this is already at index three. 152 00:06:57,210 --> 00:06:59,100 So we come out of this for loop. 153 00:06:59,100 --> 00:07:03,600 And over here we are checking if I is not equal to smallest but they are equal. 154 00:07:03,600 --> 00:07:04,500 So we don't swap. 155 00:07:04,500 --> 00:07:07,170 And again we come over here and I is incremented. 156 00:07:07,170 --> 00:07:08,820 So I comes over here. 157 00:07:09,480 --> 00:07:09,750 All right. 158 00:07:09,750 --> 00:07:12,720 So I is at index three and smallest is three. 159 00:07:12,720 --> 00:07:16,140 And j is going to be equal to I plus one which is four. 160 00:07:16,140 --> 00:07:16,500 Right. 161 00:07:16,500 --> 00:07:18,660 And again this does not this is not true. 162 00:07:18,660 --> 00:07:20,160 So we don't go inside over here. 163 00:07:20,160 --> 00:07:22,440 And we see that I is equal to smallest. 164 00:07:22,440 --> 00:07:23,430 So we don't swap. 165 00:07:23,430 --> 00:07:25,260 And we get 1345. 166 00:07:25,260 --> 00:07:26,970 And we are just returning this over here. 167 00:07:26,970 --> 00:07:28,500 So this is how the function works. 168 00:07:28,500 --> 00:07:32,910 Now let's take a quick look at the space and time complexity of this solution. 169 00:07:32,910 --> 00:07:36,600 The time complexity of this solution is of the order of n square. 170 00:07:36,600 --> 00:07:36,990 Right. 171 00:07:36,990 --> 00:07:39,510 So we can see we have a nested for loop right. 172 00:07:39,510 --> 00:07:42,210 So there is a for loop over here and a for loop over here. 173 00:07:42,210 --> 00:07:45,930 So that's why we have an O of n square time complexity. 174 00:07:45,930 --> 00:07:48,090 And again we have discussed it in the previous video. 175 00:07:48,090 --> 00:07:51,000 If we have four, three two and one right. 176 00:07:51,000 --> 00:07:52,770 So initially I is going to be over here. 177 00:07:52,770 --> 00:07:55,350 And then we are going to have comparisons. 178 00:07:55,350 --> 00:07:59,820 We are going to check this value with these three values to identify which is the smallest. 179 00:07:59,820 --> 00:08:01,380 So we have three comparisons. 180 00:08:01,380 --> 00:08:04,830 And then when I is over here we are going to have two comparisons. 181 00:08:04,830 --> 00:08:07,560 And then when I is over here we are going to have one comparison. 182 00:08:07,560 --> 00:08:13,530 So if this was of size n then the first in the first case we will have n minus one comparisons. 183 00:08:13,530 --> 00:08:15,870 Then we will have n minus two comparisons. 184 00:08:15,870 --> 00:08:18,210 And this will keep happening till one. 185 00:08:18,210 --> 00:08:22,710 So this is a total number of operations which we have to do for this algorithm. 186 00:08:22,710 --> 00:08:28,200 And we have seen that this simplifies to n minus one into n divided by two. 187 00:08:28,200 --> 00:08:32,190 And when you simplify this there is a n square term which is the dominating term. 188 00:08:32,190 --> 00:08:36,120 And that's why the time complexity of this solution is of the order of n square. 189 00:08:36,120 --> 00:08:38,730 And the space complexity is constant space. 190 00:08:38,730 --> 00:08:41,610 Because as you can see, we are not using any extra space. 191 00:08:41,610 --> 00:08:46,140 We are not creating a new array or any any other data structure, etc.. 192 00:08:46,140 --> 00:08:46,350 Right. 193 00:08:46,350 --> 00:08:49,110 So the space complexity over here is O of one.