1 00:00:01,470 --> 00:00:03,080 Hey, guys, what's up? 2 00:00:03,719 --> 00:00:10,080 So in the last video, we talked about Selection's art and this video, we will learn what is the Mozart 3 00:00:10,080 --> 00:00:10,770 algorithm? 4 00:00:11,190 --> 00:00:13,110 OK, so let's take an example. 5 00:00:13,410 --> 00:00:15,000 So suppose my is. 6 00:00:20,670 --> 00:00:26,130 So my ED elements are, let's say, five, four, three. 7 00:00:27,120 --> 00:00:34,560 One and two, so this is my area, so where the resources compare adjacent. 8 00:00:35,720 --> 00:00:43,190 So compare to descent, so for will be compared with five now in the final four, should come before 9 00:00:43,190 --> 00:00:43,640 five. 10 00:00:43,670 --> 00:00:45,740 OK, and started at four. 11 00:00:45,750 --> 00:00:46,930 Should come before five. 12 00:00:47,390 --> 00:00:48,710 Let's call it J. 13 00:00:50,200 --> 00:00:52,210 And this will be Jellison. 14 00:00:53,760 --> 00:00:59,590 OK, so this for sure to come before 5:00, so what I will do, I will swipe. 15 00:01:00,060 --> 00:01:01,660 So this will become four. 16 00:01:01,680 --> 00:01:03,330 And this will become five. 17 00:01:05,250 --> 00:01:09,150 My because in the final four should come before five. 18 00:01:10,260 --> 00:01:11,400 Now, compare this to. 19 00:01:13,330 --> 00:01:16,520 Three should come before five, so strap again. 20 00:01:16,540 --> 00:01:18,530 So three and five. 21 00:01:19,240 --> 00:01:22,410 Now again, compare what should come before five. 22 00:01:23,260 --> 00:01:24,070 So when. 23 00:01:25,150 --> 00:01:29,350 Five now compare again to should come before five. 24 00:01:29,860 --> 00:01:33,630 So, again, no swapping, so two and five. 25 00:01:34,150 --> 00:01:36,880 So this is my new ADI. 26 00:01:40,990 --> 00:01:41,860 So for. 27 00:01:43,380 --> 00:01:43,860 Three. 28 00:01:45,760 --> 00:01:46,270 When? 29 00:01:47,870 --> 00:01:48,230 To. 30 00:01:49,330 --> 00:01:56,470 And five, so this is my new area now, I will do the same look, compare for entry. 31 00:01:58,080 --> 00:02:02,850 Today should come before 4:00, so step three and four. 32 00:02:03,600 --> 00:02:04,410 Now compare. 33 00:02:05,500 --> 00:02:14,130 One should come before four, so one and four now compared four and two to should come before four, 34 00:02:14,740 --> 00:02:17,980 so swept through two and four. 35 00:02:18,790 --> 00:02:21,580 Now compare four and five. 36 00:02:21,610 --> 00:02:23,800 So four should come before five do nothing. 37 00:02:24,680 --> 00:02:26,720 OK, so do nothing. 38 00:02:26,790 --> 00:02:27,070 OK. 39 00:02:28,240 --> 00:02:29,530 Now, our new is. 40 00:02:31,070 --> 00:02:32,540 So when you raise. 41 00:02:42,070 --> 00:02:42,550 Three. 42 00:02:43,640 --> 00:02:44,180 When? 43 00:02:45,250 --> 00:02:47,350 Two for. 44 00:02:48,370 --> 00:02:49,090 And five. 45 00:02:50,630 --> 00:02:51,980 OK, so compar. 46 00:02:53,370 --> 00:02:56,010 One should come before three, so swapper. 47 00:02:57,850 --> 00:02:58,660 Now compare. 48 00:02:59,900 --> 00:03:02,360 Those should come before 3:00, so Swapper. 49 00:03:04,450 --> 00:03:05,290 Now compare. 50 00:03:06,250 --> 00:03:07,150 So this is correct. 51 00:03:07,200 --> 00:03:13,920 OK, three should appear before four, so do nothing now compare four shall come before five. 52 00:03:14,650 --> 00:03:15,520 So do nothing. 53 00:03:16,840 --> 00:03:18,400 Now, our final array's. 54 00:03:20,090 --> 00:03:22,700 So this is our new Eddie. 55 00:03:26,600 --> 00:03:27,080 One. 56 00:03:28,090 --> 00:03:29,860 Two, three. 57 00:03:30,900 --> 00:03:33,240 Four and five. 58 00:03:34,700 --> 00:03:37,130 So this is auditoria, and this is my final answer. 59 00:03:38,150 --> 00:03:41,270 So what if you will follow the same approach, SVREP? 60 00:03:42,820 --> 00:03:47,860 So they compare, compare what will happen, they are a degradation, do nothing. 61 00:03:49,190 --> 00:03:56,440 Compare, they are the correct position, do nothing, compare, do nothing, compare, do nothing. 62 00:03:56,930 --> 00:03:58,590 So this is my ordinary. 63 00:03:59,420 --> 00:04:06,730 So my question to you is, how many times do we have to show how many times we have to do all this? 64 00:04:07,490 --> 00:04:10,600 So in this case, I was having five elements. 65 00:04:11,420 --> 00:04:15,330 So if I am having five elements, how many times I have did so? 66 00:04:15,380 --> 00:04:16,010 First time. 67 00:04:16,430 --> 00:04:17,269 Second time. 68 00:04:20,970 --> 00:04:26,490 And third time, so I did three times, so after doing three times, I got my answer. 69 00:04:27,070 --> 00:04:34,500 OK, so if the number of elements was five after doing three times, I got my final answer. 70 00:04:36,150 --> 00:04:36,570 Now. 71 00:04:38,860 --> 00:04:41,170 Now, let us consider the worst case. 72 00:04:42,180 --> 00:04:48,690 So what will happen in the worst case, so what will happen in the worst case, my area will be reversed, 73 00:04:48,690 --> 00:04:55,400 sorted, so reverse order means my area will be sorted in reverse order. 74 00:04:55,410 --> 00:05:02,210 So for three, two and one, so my atoms sorted in reverse order. 75 00:05:02,370 --> 00:05:04,140 So this will be the worst case. 76 00:05:04,170 --> 00:05:06,570 OK, so this is worst case. 77 00:05:07,750 --> 00:05:14,260 Now ahead, we will try to understand that for any limits, how many times we have to do something so 78 00:05:14,260 --> 00:05:23,680 compare and step three and four compare and strap so to full compare. 79 00:05:23,680 --> 00:05:29,920 And so when and for the first time, for the first time, I knew it is. 80 00:05:32,580 --> 00:05:34,500 Three to. 81 00:05:35,610 --> 00:05:49,910 When and so this is my new editor, come back and sweep, compare and sweep, come back and do nothing. 82 00:05:50,430 --> 00:05:51,330 So second time. 83 00:05:53,120 --> 00:05:54,290 Now adays. 84 00:05:55,800 --> 00:05:56,280 So. 85 00:05:58,120 --> 00:05:59,590 My ETA is to. 86 00:06:00,690 --> 00:06:03,270 Then one, then three. 87 00:06:04,280 --> 00:06:05,180 And then for. 88 00:06:07,260 --> 00:06:16,050 So compare and swap, so when we come here to come here, come here, do nothing, compare, do nothing. 89 00:06:16,470 --> 00:06:17,280 So third time. 90 00:06:17,820 --> 00:06:19,170 So after doing three times. 91 00:06:22,430 --> 00:06:29,640 So after doing three times, I got my final answer, my record sorted, one, two, three and four. 92 00:06:30,380 --> 00:06:32,530 OK, so my add is sorted. 93 00:06:33,080 --> 00:06:35,450 So this was the worst case. 94 00:06:36,290 --> 00:06:43,340 And I have to do three times the number of elements are four, so I have to do three times. 95 00:06:45,410 --> 00:06:52,010 OK, so this wrapping things I have to do three times so we can also say like this that. 96 00:06:55,050 --> 00:06:56,490 For sorting in numbers. 97 00:06:58,020 --> 00:07:06,840 For sorting in numbers, what to do is short and minus one numbers short and minus one numbers, you 98 00:07:06,840 --> 00:07:11,640 want to sort end numbers, I'm saying you habibti sort and minus one numbers. 99 00:07:11,970 --> 00:07:14,100 So if and minus the numbers are sorted. 100 00:07:14,130 --> 00:07:21,090 That means if they are at their calculation, then the last number will also be at its current position. 101 00:07:21,120 --> 00:07:26,640 OK, so that is the reason for any calls for I have to do the stabbing two times. 102 00:07:27,250 --> 00:07:27,580 Why? 103 00:07:27,840 --> 00:07:29,730 Because for sorting in numbers. 104 00:07:29,730 --> 00:07:36,330 If we start and minus one numbers then the last number will automatically get it correct position. 105 00:07:39,010 --> 00:07:40,240 So it is very simple. 106 00:07:41,020 --> 00:07:45,940 First of all, how many times do we have to do this wrapping things and minus one times so count to 107 00:07:45,940 --> 00:07:50,150 close one count less than what it was two and minus one times. 108 00:07:50,170 --> 00:07:53,570 We have to do this Sappington and the count plus plus. 109 00:07:54,950 --> 00:07:58,390 OK, now I will start from zero. 110 00:07:58,480 --> 00:07:59,760 I have to start from zero. 111 00:07:59,770 --> 00:08:01,270 The zapping you can see here. 112 00:08:03,130 --> 00:08:06,760 The thing was that starting from zero, and this is and minus one. 113 00:08:08,080 --> 00:08:14,590 OK, so the will start from so this is G and this will be the final value of G. 114 00:08:16,090 --> 00:08:22,930 So Jay will go from this to this David Hotel and minister to minus two, because I'm comparing Jay and 115 00:08:22,930 --> 00:08:31,030 Jay plus one, if you will take Jay here, then Jay plus one will become and and if you will. 116 00:08:31,030 --> 00:08:31,420 Right. 117 00:08:31,420 --> 00:08:35,400 LFN, that will give you segmentation fault. 118 00:08:38,640 --> 00:08:48,330 So they will start from zero, G will go to second last position and C++, so what I was doing if. 119 00:08:49,940 --> 00:08:59,930 If Jay is greater than F.J. plus one I am comparing to our descent values, then what I will do, I 120 00:08:59,930 --> 00:09:00,470 will slap. 121 00:09:01,880 --> 00:09:04,520 Slap, A.J., and the object lesson. 122 00:09:07,600 --> 00:09:09,130 So this is all that we have to do. 123 00:09:09,850 --> 00:09:10,240 OK? 124 00:09:11,400 --> 00:09:12,790 So Vion minus two. 125 00:09:13,260 --> 00:09:19,200 So if the value of Jay and minus two and minus two, so this value will become and minus one. 126 00:09:19,410 --> 00:09:19,860 Correct. 127 00:09:20,250 --> 00:09:22,740 Now put Jaquiss and minus one. 128 00:09:23,580 --> 00:09:28,110 So if you put Ajin minus one this value will become and because. 129 00:09:28,110 --> 00:09:28,950 And minus one. 130 00:09:29,460 --> 00:09:30,000 Plus one. 131 00:09:30,000 --> 00:09:33,660 So this value will become and and you are doing aof and. 132 00:09:35,740 --> 00:09:36,680 Segmentation fault. 133 00:09:36,700 --> 00:09:39,790 So that is the reason I will go to hell and Minnesota. 134 00:09:41,960 --> 00:09:42,400 OK. 135 00:09:44,290 --> 00:09:45,710 So this is all that we have to do. 136 00:09:46,150 --> 00:09:46,750 So if. 137 00:09:47,770 --> 00:09:50,800 So this is my job and this is Jay plus one. 138 00:09:51,280 --> 00:09:52,540 So I believe it should happen. 139 00:09:52,540 --> 00:09:59,120 The value at the J should be less than value plus one to get element sorted in ascending order. 140 00:09:59,500 --> 00:10:06,670 So if Jay is bigger, if it's bigger than swamp, then we have to swap. 141 00:10:08,100 --> 00:10:09,960 OK, so let us write the code. 142 00:10:11,280 --> 00:10:14,910 So one more thing before writing, or have you noticed one thing here? 143 00:10:16,640 --> 00:10:23,750 So if you look carefully, the biggest value in forced arbitration reaches its correct position, so 144 00:10:23,750 --> 00:10:31,520 five is the biggest value in the area and then one five reach its correct position in second iteration, 145 00:10:31,550 --> 00:10:35,720 the second largest value reached its correct position. 146 00:10:36,410 --> 00:10:42,320 Similarly, in the third iteration, the third largest value got its correct position. 147 00:10:42,620 --> 00:10:44,140 And similarly, there are two. 148 00:10:44,150 --> 00:10:47,180 And then when you can see here also. 149 00:10:48,640 --> 00:10:56,170 So in the first iteration, the largest value got its correct position in the second iteration, the 150 00:10:56,170 --> 00:11:02,740 second largest value got the second largest value, got its correct position in the third iteration, 151 00:11:03,040 --> 00:11:05,650 the third largest value got its correct position. 152 00:11:05,770 --> 00:11:07,360 OK, so you can see. 153 00:11:09,310 --> 00:11:15,490 In the first iteration, so first iteration, largest value will come, largest value will reach, and 154 00:11:16,420 --> 00:11:21,880 in the second attrition, the second largest value will reach at its correct position. 155 00:11:22,870 --> 00:11:27,580 Third iteration, the third largest value will reach at its highest position. 156 00:11:27,910 --> 00:11:31,360 OK, so my error is getting started in this way. 157 00:11:33,780 --> 00:11:35,670 So this is my unsorted. 158 00:11:37,760 --> 00:11:45,120 And this part is sorted, so the sorted is in this way in case of selection's. 159 00:11:46,490 --> 00:11:47,510 So if you remember. 160 00:11:48,870 --> 00:11:57,030 And selection sort, what we did was, if you are standing here, find the smallest value in the right 161 00:11:57,030 --> 00:11:59,280 hand side and put that value here. 162 00:11:59,730 --> 00:12:07,200 So in first iteration, the smallest value will reach added position in the second iteration, the second 163 00:12:07,200 --> 00:12:11,820 the smallest value will reach at its correct position in attrition. 164 00:12:12,060 --> 00:12:16,050 The third smallest value will reach at its correct position. 165 00:12:16,560 --> 00:12:22,340 So any selection, sort of what is happening might add is getting sorted in this way. 166 00:12:23,100 --> 00:12:27,420 So it is getting started in this way and this part is unsorted. 167 00:12:29,160 --> 00:12:34,920 And in case of bubble my is getting sorted in this way and this part is unsorted. 168 00:12:37,660 --> 00:12:46,280 So this is sort of my area is my area is getting sorted in this way, first and largest value, the 169 00:12:46,340 --> 00:12:52,060 second largest, then third largest and her first port smallest value, then the second smallest value, 170 00:12:52,060 --> 00:12:54,910 then third smallest value, then for smallest value and so on. 171 00:12:57,290 --> 00:13:00,910 I guess that's why the call for Assad to the court is very simple. 172 00:13:02,140 --> 00:13:07,320 How many times do we have to perform this webbing and minus one times, OK? 173 00:13:07,350 --> 00:13:07,560 Why? 174 00:13:07,710 --> 00:13:09,910 Because we have already seen the worst case. 175 00:13:10,420 --> 00:13:14,080 In worst case, if the value of friend goes forward with three times. 176 00:13:14,440 --> 00:13:16,240 So we have to do and minus one times. 177 00:13:17,360 --> 00:13:23,810 And they will start from zero, I will start campaigning from zero, I will come back and plus one since 178 00:13:23,810 --> 00:13:27,520 I am using their platform, so the maximum they will be on minister. 179 00:13:27,860 --> 00:13:33,330 OK, that maximum level, they will be in minus two because I am comparing David J plus one. 180 00:13:35,180 --> 00:13:36,460 OK, so for J. 181 00:13:36,500 --> 00:13:37,650 Question minus two. 182 00:13:37,700 --> 00:13:38,060 This way. 183 00:13:38,060 --> 00:13:39,050 Lewis and minus one. 184 00:13:40,080 --> 00:13:43,590 So if it's good, then lesson, then I will do something. 185 00:13:45,160 --> 00:13:46,240 So right outside the cold. 186 00:13:47,680 --> 00:13:50,020 So let us nameless, faceless babble sort. 187 00:13:55,240 --> 00:13:56,980 So there was Art and Art CBB. 188 00:14:11,730 --> 00:14:13,560 So let us take input from the user. 189 00:14:17,140 --> 00:14:29,040 So far, and I equals zero, I lost and I plus plus seven if I let us make an error. 190 00:14:30,220 --> 00:14:32,440 So the size of the arrays and. 191 00:14:35,030 --> 00:14:43,330 Now I will write a function, bubbles or so bubble, what bubbles heart will take as input, so bubbles, 192 00:14:43,460 --> 00:14:49,570 it will take two things it and the size of the eddy and it will start my eddy. 193 00:14:49,880 --> 00:14:51,050 So my heart is ordered. 194 00:14:51,090 --> 00:14:56,210 Now let us print this after Eddy far and die equals zero. 195 00:14:56,210 --> 00:14:59,440 I less than in a plus place. 196 00:15:01,280 --> 00:15:03,080 See I would if I. 197 00:15:05,340 --> 00:15:12,990 OK, so the Court of Appeals thought so this function will return void, OK, because I'm just sorting 198 00:15:12,990 --> 00:15:17,850 that I'm not returning any value to mean so bubble. 199 00:15:19,080 --> 00:15:27,480 So it is taking to things as input first lady and second, the size of the Harry. 200 00:15:31,990 --> 00:15:43,090 So for how many times and minus one times count equals one count less than an hour equals and minus 201 00:15:43,090 --> 00:15:46,480 one count plus plus. 202 00:15:50,160 --> 00:15:59,040 Now, what we have to do, we have to just compare and numbers, so I'm starting from zero G is less 203 00:15:59,040 --> 00:16:01,750 than articles two and minus two. 204 00:16:01,770 --> 00:16:02,910 So this is important. 205 00:16:02,910 --> 00:16:05,080 And minus two J. 206 00:16:05,340 --> 00:16:06,000 Plus plus. 207 00:16:08,940 --> 00:16:11,980 Now, what he will do, he will compare their DNA to numbers. 208 00:16:12,450 --> 00:16:20,880 So if F.J. is greater than of J plus one, then you have to swab. 209 00:16:21,840 --> 00:16:22,740 So swab. 210 00:16:24,700 --> 00:16:29,780 F, G and F, g plus one. 211 00:16:31,270 --> 00:16:33,100 So this is all that we have to do. 212 00:16:33,650 --> 00:16:38,100 OK, so I told you Ariha Pasta, Bio-Reference. 213 00:16:38,110 --> 00:16:44,110 So if I am changing the values of at O'Haire, this changes will be reflected in function men. 214 00:16:44,690 --> 00:16:51,940 OK, so one more time I told you when you pass ETA to a function, then they are passed by reference. 215 00:16:52,270 --> 00:16:59,410 So if you will do changes in the Eddie, those changes will be reflected in the main function in the 216 00:16:59,490 --> 00:17:00,670 calling function. 217 00:17:04,000 --> 00:17:12,520 Certain number of elements are faith and the values are, let's say, five, four, three, two and 218 00:17:12,520 --> 00:17:12,770 one. 219 00:17:13,810 --> 00:17:16,869 So this is my output, which is sorted. 220 00:17:20,400 --> 00:17:27,910 Let's say MPs are five and the elements are five, four, three, one and two. 221 00:17:29,190 --> 00:17:31,500 So again, this is producing the correct output. 222 00:17:33,390 --> 00:17:45,240 So let's say the number of elements are four and the elements are 30, 20, 10 and 50, so elements 223 00:17:45,240 --> 00:17:46,330 are getting started. 224 00:17:47,160 --> 00:17:49,770 So this is how it works. 225 00:17:51,720 --> 00:17:54,660 OK, so now let's discuss one last thing. 226 00:17:57,470 --> 00:18:01,430 So how many steps it takes to start? 227 00:18:02,600 --> 00:18:11,360 So this outer function is running approximately and minus one times, so outer loop is running and minus 228 00:18:11,360 --> 00:18:15,500 one times and inner loop is also running and minus two times. 229 00:18:16,460 --> 00:18:24,260 So a number of steps, a number of steps equals and minus one and two and minus two. 230 00:18:24,860 --> 00:18:26,570 OK, so these are the number of steps. 231 00:18:27,260 --> 00:18:34,440 So if you will multiply them, we will get and squared them, then income and then some constant. 232 00:18:34,850 --> 00:18:38,390 OK, so let's put an inquest into the power six. 233 00:18:38,960 --> 00:18:43,650 So this value will be 10 to the power to this value will return to the power of six. 234 00:18:43,670 --> 00:18:45,200 And this is something constant. 235 00:18:46,040 --> 00:18:51,870 Now tell me in front of this, does it have any significance? 236 00:18:52,430 --> 00:18:52,880 No. 237 00:18:53,650 --> 00:18:58,710 In front of to the power, to oil and to the power six is nothing. 238 00:18:59,100 --> 00:19:04,460 OK, so I can say the number of steps is a close to and square. 239 00:19:05,900 --> 00:19:10,790 OK, so the number of steps is actually called time complexity. 240 00:19:13,210 --> 00:19:19,840 Time, complexity and complexity means how many number of steps your program took to execute. 241 00:19:21,010 --> 00:19:29,690 OK, so this thing is clear, so how we report and complexity, we will write big or record and square. 242 00:19:30,250 --> 00:19:32,950 So this is called time, complexity of bubbles. 243 00:19:33,670 --> 00:19:35,920 So this is the time, complexity of bubbles. 244 00:19:36,940 --> 00:19:39,750 So what was the time complexity of selection start? 245 00:19:40,120 --> 00:19:43,160 So time, complexity of selection, so was also in the square. 246 00:19:44,320 --> 00:19:46,330 OK, so selection's our time. 247 00:19:46,330 --> 00:19:52,210 Complexity was also in the square and the time complexity of bubbles is also and square. 248 00:19:53,930 --> 00:19:56,990 Now, any idea why we calculate time, complexity? 249 00:19:58,320 --> 00:19:58,800 So. 250 00:20:01,630 --> 00:20:03,300 Suppose you want to buy a car. 251 00:20:04,540 --> 00:20:09,430 So what we will check it will check what is the mileage, what is the cost? 252 00:20:11,040 --> 00:20:12,480 How many number of seats? 253 00:20:14,400 --> 00:20:18,090 What is average speed and there are many factors. 254 00:20:18,480 --> 00:20:22,710 OK, so for deciding which car to buy, you will see many factors. 255 00:20:23,500 --> 00:20:26,640 OK, so there are many sorting algorithms. 256 00:20:26,820 --> 00:20:29,340 There are many sorting algorithms. 257 00:20:30,210 --> 00:20:33,720 How we will decide which sorting algorithm is best. 258 00:20:35,100 --> 00:20:42,330 So what we will do, we will find how much time is my program taking to execute the algorithm, which 259 00:20:42,330 --> 00:20:49,300 take the least amount of time, the algorithm which takes the least amount of time, is the best algorithm. 260 00:20:50,190 --> 00:20:57,030 OK, so that is the reason we calculate the complexity of the program to compare to algorithms or to 261 00:20:57,030 --> 00:20:58,360 compare two programs. 262 00:20:59,010 --> 00:21:07,860 So both bubble sort and solutions are both complexity is and where they both take an equal number of 263 00:21:07,860 --> 00:21:09,060 steps to execute. 264 00:21:10,820 --> 00:21:18,430 OK, so actually, time complexity is a very big topic, I have just given you an introduction to time 265 00:21:18,450 --> 00:21:19,070 complexity. 266 00:21:19,430 --> 00:21:21,620 That is why we calculate time complexity. 267 00:21:21,650 --> 00:21:23,990 OK, so this was just an introduction to time. 268 00:21:23,990 --> 00:21:26,600 Complexity and complexity is a big topic. 269 00:21:28,070 --> 00:21:32,770 OK, so this is it for this video, if you have any doubt in the heart, you can ask me. 270 00:21:33,230 --> 00:21:33,800 Thank you.