YT YouTube2Text

YouTube2Text → Transcripts → Sorting - Part 1 | Selection Sort, Bubble Sort, Insertion Sort | Strivers A2Z DSA Course

Sorting - Part 1 | Selection Sort, Bubble Sort, Insertion Sort | Strivers A2Z DSA Course — Transcript

by take U forward · 6,965 words · 889 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:03hey everyone welcome back to the channel
0:04I hope you guys are doing extremely well
0:06so this will be another lecture from the
0:08Strivers a toz DSA course just in case
0:11you for the first time here this course
0:13is India's most yes most indepth course
0:17on DS algo why do I say that the course
0:19has 4506 module you can go to the market
0:24buy any of the paid courses check out
0:26any of the free courses none of those
0:28courses on DS algo will have 456
0:31problems or modules solved so this is
0:35definitely by far one of the most
0:38comprehensive course on DS algo and this
0:40is the only thing that you'll be
0:41requiring if you are preparing for
0:44placements so in the previous videos we
0:46have covered the step one and now we
0:48will be going to step two now the step
0:50two states you have to learn important
0:52sorting techniques in order to start
0:54your journey with Ds algo sorting is
0:57something which you have to know even if
0:59you're going for placements they might
1:01ask you sorting algorithms and the
1:04Sorting one which is Step 2.1 we have
1:06three algorithms selection sort bubble
1:09short insertion sort so if you're
1:12appearing for placements they might ask
1:13you hey can you please tell me the code
1:15for insertion sort and you have to tell
1:17them right and sorting two will be based
1:20on recursion so we'll be covering that
1:22in the next lecture so without waiting
1:25let's start with selection sort so
1:27before moving in the video let me tell
1:29you about learn base so learn B is an
1:30Tech platform that offers you data
1:32science and full stack development
1:33programs dedicated to professionals only
1:35so at learn B you will be getting 100%
1:37live online classes where you can
1:39interact with the faculties directly and
1:41get your doubt Result One Is to one one
1:44thing I did like about learn is you'll
1:45be getting an opportunity to work on
1:47industry based Capstone projects which
1:50will be certified by IBM so you're going
1:52to get a global accreditation which will
1:54be beneficial whenever you present that
1:56project anywhere that's going to be very
1:58very helpful you Al get an one is to one
2:01personal mentorship and you also get a
2:03one is to one daily doubt session where
2:05you can actually get all your doubts
2:07resolved also they have project
2:08innovation Labs across the country in
2:10Kolkata Pune Bangalore Hyderabad and a
2:12lot of other places so you can go over
2:14there and create your projects in the
2:15offline mode as well once you enroll for
2:18any of the courses you three years of
2:19subscription so you can have all the
2:20learning modules and all the videos for
2:223 years in this program you'll also be
2:24getting 100% job assistance by their
2:26dedicated placement cell and in the past
2:29people have got got hikes up to 250% and
2:31they have partnered with more than 250
2:33companies like UI Intel sap and a lot
2:36others Lear B alies have also got placed
2:38in top companies like Amazon t cap gini
2:40Etc so what are you waiting for there's
2:42a link in the description click it and
2:43get your free 1 is to one career
2:45counseling session the question what is
2:48selection sort does the name recommends
2:53selection what do you select we select
2:57minimums remember this as the name name
3:00recommends what do you select we select
3:03minimums so as the name recommends
3:05select minimums so what you will do is
3:08you look at the entire array and you
3:10will say who is the minimum and it
3:12states nine is the minimum so you'll
3:15take that nine and you'll place it here
3:19perfect I place the nine here and if
3:23this nine is the minimum and you're
3:25placing it at the first place where will
3:2713 go 13 says okay no issues I will go
3:31to your place because n has to come at
3:33first and now I'll write the remaining
3:36guys over here that's how you do it so
3:39that is the step one of the algorithm
3:41the step one States get the minimum from
3:44the
3:45entire and youve got the minimum you
3:48place it at the first whoever is at the
3:51first goes to that minimum simple as
3:54that so swapping select minimums and
3:57swap is what the algorithm is all about
4:01this is step one remember this this is
4:03step one what is step two let's see so
4:06the step two states okay I know the
4:09first I know the extreme smallest guy is
4:12at the first now we should select the
4:16next minimum we know one thing if the
4:19minimum is over here this array is
4:21sorted which portion of the array is not
4:24sorted that is this let's find the
4:27minimum can I say in this 13 is the
4:30minimum so if 13 is the minimum I know 9
4:33will stay where 9 is if 13 is the
4:36minimum 13 will come at the first place
4:39it will and if 13 comes here where will
4:4246 go 46 will go to 13 so 46 goes here
4:47and the rest remains as it is perfect
4:50step two done let's do step three so can
4:54I
4:55say after two steps I got the first two
4:58minimums
5:00and this portion of the AR sorted I can
5:03now we are left with this portion what
5:06to do get the next minimum who's the X
5:08minimum
5:1020 as usual 930 stays 20 comes in if 20
5:15is coming in here where will 24 Go 24
5:18will go to 20 so take it to there and
5:22550 to 46 stays step three is completed
5:26let's do step four at step four can you
5:29say that that this portion of the array
5:31is sorted you can which portion is not
5:35this one so in this which is does
5:37minimum 24 place it 9 13 20 24 52 goes
5:44at its place 46 let's do the step five
5:48so can I say at step four this is sorted
5:51and this is unsorted who is the minimum
5:5546 so 9 13 20
5:5824 uh sorry 46 will come
6:02here and 52 will go here now at step
6:06five if this is done do you need to look
6:10like do you need to sort one element one
6:13element will always be sort so
6:15apparently can I say the entire array is
6:17sorted at step five 1 2 3 4 5 six six
6:21elements but actually took five steps to
6:25sort the entire array what I did was get
6:29the minimum
6:30and swap it and swap it then what I did
6:33was get the minimum and swap it then
6:36what I did was get the minimum and swap
6:39it so get the minimum and swap is the
6:43algorithm now the question comes okay
6:46we've understood the algorithm but how
6:48do I implement this in code I'll be
6:52writing the pseudo code so that you can
6:53write it in C++ as well as in Java as
6:56well as in Python so in order to
6:58implement algorithms you have to have
7:01something like observing power let's
7:03start observing what the first
7:06observation in the entire array very
7:09very in the entire array we figured out
7:12the minimum can I say figured out the
7:14minimum and whichever index the minimum
7:17appeared whichever index the minimum
7:19appeared I swapped it with the first guy
7:22zero
7:23thing that's what I did that's why 13 is
7:27here and 9 is here
7:30the 0 to 5 is what I went
7:33next I took this which is from index one
7:37to index 5 and I got the minimum which
7:40is 13 and I swapped it with 46 thereby I
7:44got so I went from 1 to five and the
7:48swapping happened with one and the
7:52minimum
7:53minimum next in this I got the minimum
7:58and the swapping happened
8:00from two so can I say first time swap
8:05happened at index zero and minimum
8:11index next time swap happened at index
8:16one and minimum index and this minimum
8:20index is from the array 0 to n minus one
8:24this minimum index is from the array 1
8:26to n minus one next time can I say
8:28swapping happened
8:30at index two
8:31because till that 0 and one are sorted
8:35and minimum Index this time is from 2 to
8:38n minus one so can I generalize this and
8:41can I say this will go like 0 1 2 till
8:45what are you doing for the last guy are
8:48you swapping the last guy is just still
8:51here you got 46 and you swapped can I
8:54say you'll go till n minus 2 index why n
8:57minus 2 index why because the last index
9:00is n minus one in arrays so can I say
9:05okay spping is happening zero 1 2 and
9:08it'll go till n minus 2 thereby can I
9:12write this as like this a pseudo code
9:15okay zero first time it will go zero
9:18next time one next time two next time
9:20three and it goes on till n-2 and I ++
9:25can I see this the first and whenever I
9:29is 0 I find the minimum from 0 to n
9:34minus one whenever is I is one I find it
9:37from 1 to n minus one whenever I is 2 I
9:41find it from 2 to n minus one so can I
9:44say you need to find the minimum guy
9:47minimum so we know one thing I will be
9:490o 1 2 and there has to be an internal
9:53Loop why because you have to find the
9:54minimum in this range minimum in this
9:57range minimum in this range so the
10:00internal Loop Can You observe something
10:02from 2 to n minus one write the internal
10:04Loop what are you waiting for write the
10:06internal Loop so can I say the internal
10:08Loop will be from Jal to
10:10I till J lesser than
10:14n minus one because that is the last
10:16index until j++ and you need to find the
10:20minimum I know the internal loop as well
10:22I know the internal loop as well now
10:25what is the next thing you have to do in
10:28this range
10:30in this range you have to find the
10:31minimum how do you do it very simple can
10:35I say initially I will keep the mini
10:38just imagine just imagine since your
10:41array is from 0 to n minus one I will
10:43say okay while we start let's consider
10:47this guy to be the small while we start
10:50for this let's consider this guy to be
10:52Min while we start for this let's
10:54consider this guy to be minimum so I
10:56will say hey my minimum PS at index I
11:00itself at index I whoever is the first
11:03guy let let's assume he's the minimum
11:05I'm like okay then I'm saying if array
11:08of J is smaller than array of whatever
11:13minimum index you are
11:15considering what does this mean when I'm
11:18iterating when I'm iterating element by
11:20element I'm saying hey element are you
11:24smaller than what I considered if you
11:27are can I say minimum
11:30okay you are smaller so my minimum
11:32appears at the J index not at this guy I
11:36updated so can I say once you have
11:39iterated can I say once you have
11:40iterated in the entire thing you will
11:43get the minimum index stored at the mini
11:46variable you will you will right so once
11:50this is completed what did we do let's
11:52go back to the algo what did we
11:54do so if you're iterating over here what
11:57will happen let's see minimum initially
12:00is zero the index right the minimum is
12:03zero what happened let's see in
12:05iteration we're taking 13 it's like 13
12:08lesser than 13 because minimum is zero
12:11what happens array of zero lesser than
12:15array of mini because mini is zero it's
12:19not there so it doesn't works next it
12:22goes here array of one lesser than array
12:25of many it's like 46 lesser than
12:29no next time 24 lesser than 13 next time
12:3352 lesser than 13 no next time 20 lesser
12:35than 13 no next time N9 lesser than 13
12:39so the mini gets updated to five so you
12:43know at the fifth index the mini is what
12:45did you do you took the mini index and
12:49you took the ith index and you swab and
12:52you swab so you can just do a
12:55swap you can just do a swap
12:59of whoever wherever is the mini whatever
13:01is the value with the first guy because
13:06if you have to take that mini and place
13:08it at the first first will go to that
13:10mini index the swap is also done simple
13:14as that so by the way how do you swap
13:16two numbers it's very simple imagine I
13:20have array of I and I have array of mini
13:24okay these are the two numbers that I
13:26have to swap imagine this is 15 and and
13:29this is 12 so what I'll do is I will
13:32take a temporary variable that's another
13:34third variable that I'll take and I'll
13:36say array of mini to go there so what
13:40will array of mini what will temporary
13:42have as of now 12 because array of mini
13:46is 12 and that was put in to the
13:48temporary now what I'll do is I'll say
13:51array of mini can you replace yourself
13:54to array of I so what will be the value
13:58of array of
13:59will not be 12 this value will go here
14:02and this will become 15 right now I will
14:05say array of I hey array of I can you
14:09take the value of array of many but it
14:11is replaced to 15 this is where since
14:14you stored in the temporary that works
14:16and he a temporary can you get it the
14:18temporary will get it and this will
14:20become 12 that compl got 12 so this is
14:24the swap that you have to write this is
14:26the pseudo code of swap function so if I
14:29had to code it up imagine I've given the
14:31N I take it as the input then I take
14:34this array of N and then I go across and
14:36I say this so this is basically nothing
14:39but the array input that I'm taking now
14:42I have to write the selection sort so
14:44maybe I can say selection I'll just pass
14:47it into the function I'll pass it let's
14:49write the selection s so void selection
14:53and this will be sort and I'll say let's
14:56take the array and let's take the nend
14:58so so I'm passing this and I'm assuming
15:02this will do it and post this what I'll
15:04do is for I I equal to z i lesser than n
15:08i++ can I print the array values to see
15:11if they are sorted or not okay let's see
15:14if they are sorted or
15:17not and what we can do is we can take
15:19the same example that we took it had six
15:21numbers 13
15:2346 24 52 20 and 99 the same example over
15:30here let's quickly write the
15:33code so whatever pseudo code I did write
15:36that I've converted into code now over
15:38here and if I go across and run this
15:41particular task you will see that this
15:42particular array is sorted over here in
15:44the output.txt so you have understood
15:47the selection sort algorithm in depth
15:49it's time to analyze the time complexity
15:51of this particular algorithm let's see
15:53can I see for the first time when the
15:55loop gets inside this particular Loop
15:59runs for n times exactly yes next time
16:04when it gets in then this actually runs
16:07for one lesser it's it runs for 1 to n
16:09minus one so can I say it runs for n
16:12minus one next time when it gets in it
16:15runs for one lesser so it's like nus 2
16:19next time when it gets in runs for one
16:21lesser nus so so on it kind of runs for
16:25till last last that we run for this is
16:29still here that's for two times so this
16:31is kind of kind of if I just try to take
16:34it to some near near formula stuff can I
16:38say it's something like 1 + 2 + 3 plus
16:41dot do dot till n which is nothing but
16:44the summation of the first n natural
16:46numbers which is n into n + 1 by 2 can I
16:52say this I can if I can say this what is
16:55this
16:57n² Plus n by
17:012 can I say this is how it looks like
17:04and if you remember the time complexity
17:06Remember the Time complexity leure we
17:09did we
17:10ignore smaller things because n by2 in
17:13comparison to n square is very small and
17:16we ignore constant thereby I can say
17:20that the time complexity is near about
17:23beo of n² and this is the best this is
17:28the worst first and this is the average
17:31time complexity for this particular
17:34algorithm so we can say that we have
17:36completed selection s successfully now
17:40it's time to understand bubble shot
17:42bubble shart so when we talk about
17:44Bubble shart you have to remember it
17:46pushes the maximum to the last and
17:48opposite to the selection because
17:50selection s was taking the minimum at
17:52the front if you remember pushes the
17:54maximum to the last how does it do it by
17:57adjacent spping adjacent swapping is the
18:00key over here how how does the algorithm
18:03work let's understand first two elements
18:06Compares are they in the sorted order 13
18:09and 46 they are because 13 is smaller
18:11than 46 do not do anything go to the
18:15next two are they in the sorted order 46
18:18before 24 no swap it
18:24okay
18:2624 24 4
18:29perfect let's go to the next 4652 are
18:33they in the SED order yeah they are why
18:36will you do anything next 50 to 20 are
18:40they in the S order no 20 should be
18:43before take 20 here take 52
18:47here so 20 52 let's go to the next 50 to
18:5319 are they in the sorted no so take
18:56here take here so let's 2 9 and then 52
19:01so can I say after adjacent swaps like
19:06this like this like this like this like
19:10this one complete round of adjacent swap
19:13checkings Do You observe something the
19:16max 52 is at the last the max 52 is at
19:21the last done so the max 52 is at the
19:24last what should be your next step this
19:28this portion of the array is kind of
19:31sorted so I need to work on this perform
19:34the same algorithm again let's do it
19:371324 is it okay it is 24 46 is it okay
19:42is
19:444620 no no no no swap 46 here take 20
19:49here let's swap it 20 46 let's go to the
19:54next 469 are they no no take 9 here take
20:0046
20:01here 9 46 do you compare the last two
20:06there's no point because 52 is already
20:09in the sorted F there's no need you only
20:13do it till here can I say no in this
20:16particular array 46 was the maximum and
20:19it's at the last thereby after two steps
20:23the last two are in the correct orders
20:27so Step One is done step two is done
20:30let's do the step three so this is done
20:32this is done let's do the step three
20:34step three means this portion should be
20:37making sure that the maximum is over
20:40here let's do it 1324 are they they are
20:452420 no no no drop
20:49it 2024 next 249 no no drop
20:55it done in this 24 was the maximum eight
21:00at the last step three done step four
21:05can I say step three means last three
21:07elements done this is left 1320 correct
21:1329 no SWAP SWAP SWAP 920 can I say for
21:19this 20 was the largest and it's at the
21:21last so thereby post step
21:25four this is done next
21:29step five what is step
21:32five this let's do a comparation no ST
21:38913 for this portion 13 was the maximum
21:41and it's at the last so for this portion
21:4413 was the maximum and it's at the last
21:47so
21:49thereby this portion is sorted post step
21:53five do you need to do for a single
21:55element you do not thereby the entire
21:58array is sorted if you see so uh so you
22:01have understood the algorithm but now
22:03the key factor comes in which is
22:05implementing this two code because that
22:08is where the key lies let's try to do
22:11that what are we doing observation is
22:14the key 0 1 2 3 4 5 we're going till the
22:19first step we went everywhere and we
22:23did adjacent component so the for the
22:27first time we can kind of went till 0
22:31till n minus one and we did adjacent
22:34swaps if if it was not in the order next
22:38time we went like 0 to n minus 2 because
22:43the last was s next time we went from 0
22:48to nus 3 next time we went to 0 to nus 4
22:55can I say this is what we are doing and
22:58the next time time 0 to nus 5 and so on
23:01can I say I will just do till 0 to 1 not
23:05till 0 to 0 because one element will not
23:07matter to me if you carefully observe
23:11first Loop should run from here to next
23:14Loop should run from here to here so
23:16kind of can I say I can probably keep
23:19the value of I from nus one till I can I
23:23keep I can so if I do it I = to N - 1
23:29I greater than 1 and IUS one this is
23:31what I
23:32have and internally I can always run the
23:36loop from J equal to Z till J lesser
23:39than I and
23:41j++ is it similar is it similar observe
23:450 to n minus1 0 to n minus1 for the
23:48first time next time I is nus 2 so 0 to
23:51n minus 2 next time I is nus 3 so 0 to
23:54nus 3 so I have made sure the looping is
23:57done what is the next thing that you
23:59doing the next thing is very simple you
24:02take up two elements and you compare you
24:04take up two elements and you compare so
24:06when you're looping from 0 to n minus
24:07one it's kind
24:10of this is J so you're comparing J with
24:13J + 1 and if they're not then you swep
24:16right so you're kind of comparing what
24:18are you
24:19comparing if a of J is kind of greater
24:23than J + 1 it's not in the correct order
24:26then you're saying swap then you're
24:27saying swap both of them
24:29a key thing to notice over a very key
24:32important
24:34thing if you are going from here to here
24:38that is wrong because for 52 it will
24:40have no one to compare with you actually
24:43go from here to
24:46here because of
24:4846 gets compared with J + 1 which is
24:51this you actually Loop till here so what
24:54you can do
24:55is you can go over here and say instead
24:58of going
25:00till I exactly I will go till I minus
25:03one because if I go till here if I go
25:08this will compare this will compare this
25:10will compare this will compare and 4652
25:12will be compared because I'm doing j+
25:15I'm taking the next index I don't need
25:16to go till so you can just go till one
25:19lesser in and if you do not do that what
25:21will happen for 52 it will look for the
25:24next index which is not present and if
25:27you are accessing ing an index which is
25:29not present it will throw a runtime
25:32error remember this if you are accessing
25:35an index which is not present it will
25:38say runtime I did not it's a runtime
25:42that's why it's very important to run
25:43your Loops perfectly that's when you
25:45swap and once you have done this all
25:49steps at the end of the day the array
25:51will be sorted so what we will do is now
25:54we will write void bubble sort we'll do
25:58the same thing array and n and instead
26:02of calling the selection sort we will
26:04say hey bubble so I will just quickly go
26:07and write the same pseudo
26:09code so if you remember this was kind of
26:12array of
26:14J if greater than array of J +
26:191 then you
26:21swap and in order to swap I've already
26:23taught you how to do that swapping you
26:26do this and then you say Okay array of J
26:31+ 1 can you store array of J and in
26:34Array of J can you take the value of the
26:36array of J which is j+ one which is
26:38stored in temporary once you have done
26:41this entire thing the array will be
26:43sorted I'll just go ahead erase this
26:45output.txt and now go across and say to
26:48run it and see if the bubble shot is
26:51actually producing it it is it is
26:54producing so if I have to analyze the
26:57time complex lexity can you analyze the
26:59time complexity for me for this
27:01particular case is quite similar to The
27:04Selection s first time the algorithm
27:07kind of runs for n then for n minus one
27:10then for n minus 2 then for n minus 3 so
27:13kind of it's similar to selection sort
27:15where I say it's n + n minus1 + n minus
27:192 plus so on the last is two it's
27:23something if you just add a one to it
27:25it's similar to sum of N natural numbers
27:28so again n into n + 1 by 2 which is n 2
27:32by 2 + n by 2 smaller constants
27:37dissolved so the complexity is B go of
27:41n² can it be optimized that's my yes it
27:45can be it can be optimized this is the
27:49worst
27:51complexity this is the worst complexity
27:54and you can also call it as the average
27:55complexity in most of the cases this
27:57will be the
27:59most of but imagine if I give you a
28:02array which is something like 2 3 5 15
28:06and 20 if I give you an AR L you'll be
28:09like tror this is sorted yeah it is
28:11sorted so do you run the loop for n
28:14Square do you go across every time every
28:16time no
28:19so what is the
28:21algorithm correct order no
28:24swaps correct order no swaps correct
28:28order no swaps correct order no swap
28:32dude if everything is in the correct
28:34order and you're not performing a swap
28:37if everything is in the correct order
28:39what does it signify the array is in the
28:42ascending order if everything is in the
28:44correct order the array is in the
28:47ascending order so in the first check
28:51you did not find a swap to be done
28:55because everything was in the correct
28:57order so can I say if I do not do any
28:59swaps if I do not do any
29:01swaps that's when I stop I do not per
29:05so it's kind of if no swaps done I don't
29:09need to go if on the first check no swap
29:13is done I don't need to go for this for
29:15this for this for this we stop so the
29:17loop the best case will run for B go of
29:20n if we do some
29:23optimizations let's go and do some
29:25optimization can I say
29:28if I say in did swap equal to zero and
29:33over here if I just can say did swap
29:34equal to one which means if any if at
29:38any moment a swap happened then it's
29:42okay but if did swap at any time
29:46is there was no swap then I break out I
29:51will not go if the array is sorted it
29:53will just check for the first time and
29:56it will break post
29:58it right this also
30:01runs I'll I'll prove you uh this one
30:05I'll prove you this one so I'll give you
30:06an example see 6 5 4 3 2 1 now what I'll
30:11do is I will just go ahead and print
30:14this how many times the array runs okay
30:18and
30:19runs and I'll just give it and you can
30:22see how many times it runs now terminal
30:25and I'll go to run task this is a
30:27descending order and it runs for five
30:29times because the size is six it runs
30:31for five but if I just change it to
30:34something like 1 2 3 4 5 six and now see
30:37how many times the first fall Loop let's
30:42see uh did it one just a
30:46minute SL one okay let's run
30:51it run it did you see something it never
30:55came to this because it it did break
30:58over here so it just ran for the first
31:00did not Swap and broke so can I say can
31:04I say the best time complexity will be
31:08nothing but B go of n the time
31:11complexity for the best of bubble shot
31:14is beo ofen this might be asked in an
31:18interview you have to critically tell
31:20them the use case you have to explain
31:22them in the dry and tell them the worst
31:24and the average might be n square or if
31:27the AR is sorted out I will break out
31:28and I will end up getting a linear time
31:30complexity because the array is already
31:33so so the bubble shot is done now let's
31:35move on to the next one that is the
31:37insertion sort algorithm so talking
31:40about insertion sort you need to
31:42remember one thing it always takes an
31:46element and places it in its correct
31:50position takes an element and places it
31:53in its correct let's start yeah the
31:56algorithm starts with looking at the
31:59first element as an array and you will
32:01say that if this much is the array the
32:05element 14 in a size one array is at the
32:10correct if I look at this much and I ask
32:13you is nine at the correct position
32:16you'll be like no nine apparently should
32:19have been here and 14 should have been
32:20here this is what you do you go to the
32:24next element and you ask on the left
32:26side where 9 should have been and that
32:30is where you take so you basically do it
32:32like this
32:34940
32:36perfect so then you go ahead to this one
32:40and you ask is 15 at the correct
32:42position for a size three and you say
32:46then you go ahead and say is 12 at the
32:48correct position for a size four and you
32:50say no app 12 should have been here 14
32:55should have been here 15 should have
32:57been here
32:58so do you see a pattern it's like 14
33:02will come here and 15 will come every
33:05one right shifts by one and 12 kind of
33:09goes in its correct qu so what you can
33:12do is you can take 12 and you can say
33:15Okay 12 15 15 will come here 12 will go
33:18here then you can say 12 14 so you can
33:2112 here and you can pass 14 here you can
33:24go to the left and SWAP SWAP SWAP till
33:26it can be swapped
33:28till it can be swep so if you do like
33:30this 12 goes here it's like 12 and 15
33:35then 12 14 so 12 goes here and 14 comes
33:39go to the left till it can be can 12 be
33:41swapped with 9 no because that will
33:44distort the order it just goes till here
33:46simple so what will happen it'll be like
33:5012
33:5114 15 perfect next is six if you look at
33:56six where ideally should be six in this
34:00array it should be here 9 should be here
34:0312 should be here 14 should be here 15
34:06should be here so can I do this can I
34:09take this six here but I have to I have
34:11to write shift every one by one how do
34:14you do it you take six you take 15 and
34:17you say Okay swap your sir what happens
34:20is six goes here 15 goes here swept next
34:23you take six 14 14 comes here and six
34:27goes here here next you take 6 12 12
34:30comes here six goes here next you take
34:32six and 9 six goes here 9 comes here
34:36simp if I have to do it it's like 6 15
34:40not in the correct order let's swap it
34:4315 comes here and 6 goes here 14 6 no 6
34:49comes here 14 goes 6 12 no 12 comes here
34:53six goes 69 No 9 comes here six Co
34:59perfect it's like 6 9 12 14 15 so I have
35:02to write it by raising it's like 6 9 12
35:0714 15 perfect I just went down to the
35:11left till it could have been SWAP SWAP
35:14SWAP right next eight in this particular
35:19array where does eight will go where
35:21will eight go in this particular array
35:23where will eight go ask yourself the
35:26answer to that is eight will go here so
35:29if8 has to go here 9 has to go here 12
35:32has to go here 14 has to go here 15 has
35:34to go here so again what do you do 8 15
35:38you say Okay 8 goes here 15 so left can
35:438 14 can8 go till 14 yes 14 comes here 8
35:46goes here can it go more left yes it can
35:498 goes here 12 goes here can it go more
35:51left yes 9 goes here8 goes here is it in
35:54the correct to yes how do you know it
35:56because when you compareed 8 with six it
35:58was not compared D and dusted 689 12
36:02145 689 12 145 remember this 6 8 9 12 14
36:1015 next 13 is the next guy that you are
36:14comparing can I say 13 ideally over here
36:17should have been here so do it again 13
36:22goes here 15 comes here 13 goes here 14
36:25comes here can I do a 13 12
36:28no stop can I say post the last the
36:31array is sorted why because you picked
36:35up every element and you did put it into
36:37its
36:37correct so how did it work I picked up
36:41one first time I picked up the first guy
36:44next time I picked up the second next
36:45time the third next time the fourth next
36:46time the fifth next time the sixth next
36:48time the seventh picked up every guy I'm
36:51running from index 0 to n minus one
36:53that's for sure that's something for
36:56sure I'm running from 0 to n minus
37:01one and what am I doing what am I doing
37:05every guy I'm looking at the left are
37:08you greater swap are you greater Swap
37:11and until I can do it like for 13 I
37:15could do till here till it is possible
37:17on the left so I'll be like okay maybe J
37:20is I and I can keep while J greater than
37:25zero and I can say and and okay hey left
37:29J minus one because the last that you
37:31can compare is still here is still here
37:35that's the last you can compare so
37:37imagine this was not 13 I'll give you an
37:40example if this was like 14 15 and this
37:44is seven the seven would have last gone
37:48here or imagine this was five for an
37:50example if this was five what would have
37:54happened five would have gone like till
37:58here and then five would have got
38:00compared with six five standing here
38:03five standing here would have compared
38:04it on the left that's why you don't go
38:07till zero because right before zero you
38:09do the last comparison that's why and
38:11that's why J minus one the last
38:13comparison if it is greater than a of J
38:17if it is greater that means can you
38:20please swap so I'm not writing the swap
38:23you know how to write you say a of J
38:25minus one and a of G that's what you say
38:29right and that's when it ends and you
38:32can just do a j minus minus over here
38:35because what am I doing is I'm taking
38:38the element and I'm saying left CH left
38:40small left small okay and go left again
38:43come back left small slap again go left
38:46left small go the moment it's not small
38:49stop and go to the next guy why simp so
38:53now time to write insertion s right so
38:56void in
38:57insertion sort in
39:00Array and in N so as usual we can just
39:05do this as insertion s okay and I'll
39:08quickly write the
39:12code until here you know the pseudo code
39:15why J greater than Z why not greater
39:17than equal to imagine if J goes equal to
39:20Z this J minus one like when J is zero J
39:23minus one will be minus time that's all
39:27right so over here you can go ahead and
39:29swap it in temporary equal to AR of J
39:35minus one and then array of J minus one
39:38is array of J and then you can go ahead
39:41and say array of J is equal to Temporary
39:44and once you have swapped let's go more
39:46left so J minus minus now let's go ahead
39:49and quickly run this and see if this is
39:52sorting this particular thing yeah it is
39:53sorting done simple if we analyze the
39:57time time
39:58complexity what will be the time
40:00complexity imagine for
40:03a reversed array like something like
40:08five 4 3 2 1 What's happen for the first
40:13time five no swaps next time it comes to
40:18four and does a swap it's like four five
40:22next time it comes to three does a
40:24complete like three goes here then three
40:27goes here next time it so it's like 3 4
40:305 2 1 next time it comes to two two goes
40:34here two goes here two goes here two
40:36kind of goes here it's like 2 3 4 5 1
40:40next time it comes to one one goes here
40:42one goes here one goes here one goes
40:43here so it's like 1 2 3 4 5 it's kind of
40:46going extreme left to the to the extreme
40:49left this Loop for the first time ran
40:54for zero times when it was at five
40:58when it was at five when it went to four
41:00it sted one place next when it was at
41:04three it swapped two places next when it
41:07was at two it spped three places next it
41:10was when it was at one it went left four
41:13places it's kind of again going into the
41:16similar direction of summation of
41:18natural numbers which is n cross at n +
41:211 by two makes it near about the time
41:23complexity of n squ if you remember the
41:25time complexity class so I can see the
41:28kind of worst case is
41:32n² the average case is also n s but what
41:37about the best case imagine I give you
41:39something like 1 2 3 4 5 1 2 3 4 5 and I
41:45go back to the code and I go back to the
41:48code so imagine it give you a completely
41:51sorted and I go back to the code and
41:53let's see how many times this Loop runs
41:57go to the terminal and try to print it
42:00this Loop will not run a single time
42:02because for one there's no one on the
42:04left for two there's no one on the left
42:06three is already in its correct position
42:07four is already in its correct position
42:09five is already in its correct position
42:11six is already so
42:13this putting them into the correct
42:15position never happens so apparently
42:17only this Loop runs for check a be it's
42:21a b ofen the best case for this is
42:25nothing but beo of n complexity because
42:31there is no swaps that happen everyone
42:33is at its correct order just go to
42:35everyone that is what the time is taken
42:38for in case of insertion s so so with
42:42this I can tick mark insertion sort and
42:44it is completed uh the time is
42:485:29 yes because I do take a lot of
42:51retakes while recording because I want
42:54it to be perfect like a lot of times I
42:57teach two or three times so please uh
43:00please for this effort if you understood
43:02everything do consider hitting that like
43:04button and to follow our ritual please
43:07do comment understood if you understood
43:09everything and if you have doubts you
43:11can definitely put that into the comment
43:12section I'll be uh replying to them and
43:15if you're new to our Channel what are
43:16you waiting for hit that subscribe
43:19button and follow sters A2Z DSA course
43:22share your learnings with the hashtag
43:25and yes if you haven't followed me on
43:26Instagram Twitter LinkedIn all the links
43:29will be in the description make sure you
43:30follow me with this I'll be wrapping up
43:32this video let's put in some other video
43:33till then bye-bye take care whenever
43:36your heart is
43:37broken don't ever forget your
43:40golden I will find a light

About this transcript

This page contains the full transcript of Sorting - Part 1 | Selection Sort, Bubble Sort, Insertion Sort | Strivers A2Z DSA Course by take U forward, generated from the public captions YouTube serves with the video. The transcript has 6,965 words across 889 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.