YT YouTube2Text

YouTube2Text → Transcripts → Quick Sort For Beginners | Strivers A2Z DSA Course

Quick Sort For Beginners | Strivers A2Z DSA Course — Transcript

by take U forward · 6,431 words · 867 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 is another video from the
0:08Strivers A to Z DSA course just in case
0:10you don't know about this and for the
0:12first time here this is world's most
0:14in-depth DS algo course why do I say
0:17that because you can go over the entire
0:19internet you can buy any of the paid
0:21courses in the market none of them will
0:23be covering any DS algo stuff in such
0:27depth this course has 456 modules and
0:31you'll be covering 400 plus problems in
0:34this particular course itself so once
0:36you complete the course you will be
0:38ready for any of the DS algorithms in
0:41any of the companies in any part of the
0:42world that is my guarantee to you so in
0:45this video we will be learning about
0:47quick sort what about these couple of
0:49topics now these couple of topics are
0:51very self-explanatory so what I will be
0:53doing is I'll be adding notes to them so
0:55that once you go through the entire
0:56notes you will be able to understand
0:58that by yourself a video is not required
1:01for these couple of topics so that's why
1:02I will not be adding videos so in this
1:05video we will be talking about quick
1:07sort so without waiting let's get
1:09started quick sort algorithm what does
1:12the algorithm do very obvious to guess
1:13yes it does sort any of the given data
1:17structure in an ascending order but if
1:20you do some minor tweaks to it yes if
1:23you do some minor tweaks to it it'll be
1:25also sorting it in an descending order
1:28so in this video I'll be teaching you
1:30the quick sort algorithm that sorts the
1:33given data structure in an ascending
1:35order in depth so that you can do the
1:37minor tweaks by yourself and you can
1:39sort the data structure in a descending
1:42order as well so what will be the flow
1:44of the lecture very simple first will be
1:46explaining the algorithm then I'll be
1:48telling you the intuition behind every
1:50step of the algorithm once we are done
1:52with that we'll be going and writing the
1:54pseudo code now remember one thing I'll
1:56be adding the pseudo code in such a way
1:58that you can code it in C plus plus Java
2:00python or any of the programming
2:01languages you code in and so this
2:03tutorial is going to be language
2:06independent and then we will be doing a
2:08dry run on the pseudocode so that the
2:10recursion is clear on your head once
2:13these three steps are done we'll be
2:15moving to the online compiler and
2:17compiling it so that you get an essence
2:19of the online compiler post that I'll be
2:21discussing the time complexity and the
2:23space complexity as well
2:26so you must be thinking let's drive a
2:28bit we already know about the merge sort
2:32algorithm which has a Time complexity of
2:34n log n and it has a space complexity of
2:37bigo of n where we use an extra
2:40temporary array y pixel so quick sort
2:44has a Time complexity similar to
2:46moisture and login but doesn't use us
2:48any extra temporary array yes it uses
2:51recursion stack space but no temporary
2:54array so quick sort is slightly better
2:57than merge sort but
2:59does that mean you don't need to know
3:00Marshall no you need to because there
3:02are a lot of problems which can be
3:04solved just by using merge and we will
3:08be seeing that in the arrays playlist
3:09when we will be solving problems related
3:11to more short term it's very important
3:12that you understand all the Sorting
3:14algorithms because you never know in an
3:16interview the interviewer might ask you
3:18any of the Sorting algorithms might ask
3:20you any question that might be similar
3:22to a particular sorting algorithm so do
3:24not skip any of the Sorting algorithms
3:26that is what my recommendation to you
3:28will be so let's get into the
3:31explanation of the algorithm and we will
3:32be using this particular array as an
3:34example to understand the algorithm so
3:37the first step of the algorithm is very
3:39simple if you are given an array the
3:42first step is very simple pick a paper
3:45remember this pick a paper what is a
3:49paper pivot can be any element in the
3:51array any element
3:53can be the first element
3:54can be the last can be the median can be
3:58the random or can be any element by your
4:01choice any element by your chart there
4:03is no particular rule to pick up effort
4:06no particular Rule now
4:08once you have picked the pivot so for an
4:11example we say that we will be following
4:13the first two and we'll be picking up
4:14the pivot as the first element of Any
4:18Given array to us so I'll be like okay
4:20we're given this array so we will be
4:22picking up the pivot as poor that is my
4:26job I'll say Okay given this array so
4:28I'll be picking pivot as 4 first element
4:31at the ending one after that
4:33pick that element and place it in its
4:36correct place in the sorted array what
4:38does it mean now this array is unsorted
4:41agreed
4:43but if I have to ask you what is the
4:45sorted array can I say the sorted array
4:47will be one two three four five six
4:49seven nine
4:50can I and if I have to write it will it
4:52be something like 1 2 3 4 5 6 7 9. and
4:57if I ask you what is the correct place
4:58of food
5:00so I have to ask you what is the correct
5:02place of 4 you'll be saying correct
5:04place of 4 is this which is the fourth
5:07place it is currently lying at the first
5:09place but actually the correct place of
5:114 is at the fourth piece that is what
5:13you'll do you'll pick up four and you'll
5:15say
5:16picked up an element and place it in its
5:19correct place and just take it and place
5:21it in its correct place that is what you
5:22have to do pick up a paper and place it
5:25in its correct place
5:27now how will that help let's understand
5:30I said pick a paper so you pick the four
5:33and you pleased it in its correct Place
5:36done then you picked up six for an
5:38example just for an exam and you placed
5:41it at its correct place which is this
5:43then you picked up two and placed it at
5:46its correct place then you picked the
5:47five and placed it as at its correct
5:49Pace then you picked up seven and place
5:52it at its correct please and you picked
5:54up nine and placed it added Skype please
5:57then you picked up one and placed it at
5:59his connect place and he picked up three
6:00and placed it at its correct please will
6:04the array be sorted at the end of the
6:06day that is the reason the intuition was
6:09very simple pick up a pivot and pivot
6:11can be anything doesn't matter what you
6:13pick because at the end of the day if
6:16you're putting them into its correct
6:17place and every element is put the array
6:20will be sorted it doesn't matter what
6:21you pick as long as you're putting them
6:24into the correct place at the end of the
6:26day if I've picked up every element the
6:28area will be sorted that's the reason
6:30any of them will work but we will go
6:33with first element you can go with the
6:34last median whatever you wish to Okay so
6:37we've understood the algorithm pick up a
6:39paper and place
6:41it in its correct place in the sorted
6:43array but what happens to other elements
6:45so the rulers the uh step number two is
6:47very simple
6:48smaller on the left remember this
6:51smaller on the left
6:55and large on the right how I'll explain
6:58you that
6:59afterwards but as of now just understand
7:01the explanation and the intuition of the
7:03algorithm small on the left and the
7:06larger on the right so what are the
7:07smallest is six smaller no so six will
7:10go on the right it's two smaller yes on
7:13the left is five smaller no greater so
7:16goes on the right is 7 smaller no it
7:18goes on the right is nine smaller no
7:20goes on the right is one smaller yes
7:22it's three smaller years so if you see
7:26can I see I have two one three
7:29and I have six five seven nine so these
7:32are greater
7:34and these are smaller
7:36and can I say after one step after one
7:42step can I say this that one element is
7:47at its correct place in the array I can
7:49so what is left can I say the left
7:52portion
7:53is still an unsorted and the right
7:56portion is still unsorted now why is the
7:59step what is the intuition behind
8:01smaller on the left and larger on the
8:03right if you think if you think in a
8:06very logical manner a four is at its
8:09correct place the left guys to the four
8:12in the sorted array will be smaller and
8:15the right guys will be greater that's
8:17why it's logical to say smaller go on
8:21the left and larger go on the right so
8:23that's the intuition behind the step two
8:25you have understood the intuition behind
8:27both the steps now you what you need to
8:30do is repeat these steps repeat these
8:32steps again and again and how do you do
8:34that very simple can I say four is done
8:36what is left the left portion and the
8:39right portion let's take the left
8:41portion two one three can I say it's an
8:43individual array it is so let's take
8:46that individual array two one three and
8:48let's again apply the same books what is
8:51of step one pick a paper what is our
8:53rule
8:54first element
8:56let's go and pick up the first element
8:57as the pivot
8:58two if I ask you the correct order
9:01if I have to write the sorted out array
9:03can I say this will be the sorted array
9:05can I say the correct order of two will
9:07be
9:08here
9:09thereby
9:11step two correct order I put it I've
9:13picked up every word and put it into the
9:15correct order step two
9:17small on the left so one is smaller on
9:20the left T is larger on the right so can
9:24I say 2 is done and we are left with one
9:27and three so again two smaller arrays
9:30but whenever an array has one element
9:33no need to do anything why one element
9:36is sorted in itself so can I say at the
9:40end you made this array to one two three
9:42so at the original places this will
9:45change this will change and this will
9:47change so the left guy got sorted that's
9:51the time for the right guy six five
9:52seven nine so let's do it for the right
9:55guys well six five seven nine
9:57so I'll write it six five seven nine
10:00rule one on the sari yes so I did it
10:04very simple four was done did the same
10:07algorithm on the left did the same
10:09algorithm on the right so kind of
10:10recursion kind of get you get an idea of
10:12recursion take the array get the paper
10:15do everything then call it for the left
10:17call it for the right kind of you're
10:20getting this yes next what's the next
10:23stop for the right direction six five
10:25seven eight what's your favorite
10:27six you have to hypothetically again
10:29same rule hypothetically you have to
10:31write it what will be five six seven
10:33eight so what's the correct order of six
10:35yes this one smaller on the
10:39larger on the right
10:41so can I say two arrays again five seven
10:44nine so can I hypothetically say that
10:47six was placed at its correct place so
10:50I'll go ahead and say
10:52six was placed at its correct place
10:54right and can I say five can I say five
10:58is a single array 5 is also placed at
11:01its correct place I can what is left
11:03this seven nine so again another array
11:06so let's take the seven nine as another
11:08array again pick up and pivot seven is
11:11the pivot what's the correct place of
11:12paper
11:137 itself and the other one is nine which
11:16is the greater so on the right so 7 is
11:20placed again go ahead and say 7 is done
11:24and now 9 is the single element so
11:26that's also done so at the end can I see
11:29this is also sorted so at the end can I
11:33say the array automatically did it for
11:36all the elements and each of them is at
11:39its correct place can I say that I can
11:41thereby the quick sort algorithm works
11:45this is the explanation and the
11:47intuition done
11:50explanation and the intuition it's very
11:53simple if I have to explain it in a
11:55shorter way pick up a pivot place it in
11:58its correct Place smaller on the left
12:00larger on the right and now the question
12:02comes how do you do this in a code how
12:05do you do this in the code so this is
12:07what we will be understanding in the
12:09pseudo code because picking a pivot is
12:12very easy because first element is kind
12:14of easy but now you might be thinking
12:15but how do you please the four in its
12:18correct place because by naked eye it's
12:20very simple this is the sorted way so
12:22you are seeing four here so you're
12:23saying 4 will be here how do you code it
12:25that's where you have to understand the
12:28algorithm in depth this other thing that
12:30you have to understand in order to do
12:31the pseudo code so if you carefully see
12:34this is the entire array right and once
12:37you have placed four you go for the left
12:39and you go for the right now the next
12:42doubt that might be coming up to your
12:43mind is but striver we have an entire
12:45array and then you're placing the pivot
12:47at its correct please then you're going
12:49to the left and going to the right so do
12:51you create new arrays no we'll be using
12:54the concept of low and high that we used
12:57in the merge sort instead of building
13:00new arrays we'll be using pointers to
13:03explain that okay
13:05the left array is from here to here the
13:08right array is from here to here we'll
13:09be using kind of pointers so let's
13:12understand the explanation in terms of
13:14pseudo code so that we can code so
13:16before going to the pseudo code let's
13:18understand how do we perform these
13:20couple of steps using a bit of variables
13:24and code logic so that we can actually
13:26write the pseudo code so imagine you're
13:28given this particular array and you have
13:30to apply quick sort to it and this is an
13:32unsorted array so will you be carrying
13:34this entire array logically doesn't make
13:37sense why because in the future you know
13:39these arrays will be broken down into
13:42smaller steps so we have to recreate new
13:44arrays so we will not be doing that
13:46instead of that we will be creating low
13:48pointer which will be pointing to the
13:49zeroth index which is the first time and
13:52we'll be keeping an high pointer which
13:53will be pointing to the last cat so what
13:56does low and high mean it means the
13:58array is from here to here very simple
14:00now what did I see what's the payment so
14:04if pivot is very simple a pivot will be
14:05the array of loom
14:08why we said paper will be the first
14:10element so the first element in the
14:12array is array of flow so first step is
14:15done
14:16that was picking up a pivot what's the
14:18next step placing the pivot in its
14:21correct place right so let's do it how
14:24do you do that in order to do that you
14:26take a i Pointer Place it at the lower
14:30or the leftmost part of the array
14:33and then take a j and place it to the
14:36right most part of the area done now you
14:39say okay let's find
14:42the first element which is greater than
14:47my Pivot
14:49because
14:50if it's smaller than it is at the
14:53correct place but if it is greater then
14:55then we will find it so let's find
14:57is 4 greater than the pivot no because
15:00what's your favorite now if I have to
15:01write the pivot the pivot is 4 so is 4
15:04greater than the pivot no is 6 greater
15:07than the pivot yes so what you will do
15:09is you will say Okay 6 is greater than
15:11the paper so you'll stop at six so your
15:14I pointer
15:15stops at six and then you will go and
15:18say okay let's find the first element
15:20that is smaller than the pivot from the
15:23right
15:24I'll say three are you smaller than the
15:26paper he says yes I am so I'll stop
15:29because 3 is smaller
15:31so you have figured out the first guy
15:33who is greater than the paper on the
15:35left and the first guy was smaller than
15:37the pivot on the right
15:40so you just have a swap so it's a 3 and
15:43you say six so you just swap them done
15:47with the swap what is the next job that
15:49you will do next job again come back and
15:52do the same thing figured out the first
15:55element from the left which is greater
15:58than the pivot is 3 greater than the
15:59pivot no so just go ahead is
16:032 greater than the paper no go ahead is
16:065 greater than the pivot yes 5 is
16:08greater than the pivot so I has stopped
16:11at a element which is greater than the
16:14pivot now go to the right and find the
16:16first element that is smaller than pivot
16:18is 6 smaller than pivot no so move
16:22is one smaller than the pivot yes stop
16:26so five
16:28and one will swap one and five swapped
16:33perfect
16:34let's again continue the same step
16:37we say okay on the left find the first
16:40who is greater is one greater
16:43is one greater than pivot
16:45no is 7 greater than pivot yes we stop
16:49there
16:51so it stops at seven on the right find
16:54the first who is lesser than pivot
17:00so we move is 9 less than paper no we
17:05move is 7 lesser than paper no we move
17:08is
17:093 is 1 lesser than pivot yes and we stop
17:14and we stop
17:15so we stop here the J stops here like J
17:19goes here J goes here and J then stops
17:22here so apparently we stopped at a
17:25position where J has crossed I it has
17:30crossed I you stop you do not swap
17:32anymore do not swap it anymore which
17:34means you are in the territory you are
17:37in the territory where if you see
17:39everything is smaller than the pivot and
17:42on the right you are at a territory
17:44where everything seven nine five six is
17:47greater than pivot so you stop what's
17:50the last job you'll do since you stopped
17:52at one you just take this four and you
17:54place it here so you basically say
17:56okay one and four goes here so if you
18:00see what happens is one three two four
18:03is that it's gonna Place seven nine five
18:06six
18:08as super sum
18:10that's very simple and we are done with
18:12this yes that's
18:14that is how easy it was so once you have
18:17placed your pivot at the correct index
18:20in the sorted array can I call this as
18:23the partition index why can I call this
18:26as a partition index very simple the
18:29reason being
18:30this is where
18:32it's at the correct order in the sorted
18:34array this is not in the correct order
18:38and this is not in the correct order
18:39it's a kind of partition left is still
18:43to be done and the right is still to be
18:45done so that is why you call it as a
18:46partition so can I say as of now the low
18:50was pointed here and the high was
18:51pointed here can I see the new array
18:54that you have to sort according to the
18:56same algorithm is from here to here and
19:00it's from here to here so can I see the
19:02new array one array will be low to
19:04partition minus one
19:07and the other array will be partition
19:09plus one comma high this is where the
19:13this array is this and this array is
19:15this so what you do is perform a quick
19:17sort again and perform a quick sort
19:19again on this that's it and on this
19:22array again repeat the same angle and
19:24once you have done this you will be able
19:27to completely sort the array right so I
19:30think I've understood the explanation
19:31the intuition and kind of the algorithm
19:33as well as of now it's time to write the
19:36pseudo code the pseudo code is going to
19:37be very simple we say quick sort and we
19:40know it will be given an array and we
19:43know the array in the array the area
19:46that we have to sort will be from low to
19:48high
19:48that is something which we definitely
19:50know and we know we will only sort the
19:52array if it has more than one elements
19:55that means a flow is lesser than high
19:58because if low is equal to high in that
20:01case assume high is here which means
20:03this is the array one element is already
20:05sorted so if low is lesser than high
20:08that means it has more than one elements
20:10thereby we will be sorting it
20:13and this is what kind of the algorithms
20:16gesture will look like
20:18if low is lesser than I what do we do
20:21imagine you're given this array what did
20:23we do at first
20:25I figured out the pivot
20:27put it at its correct place and then
20:30sorted the left half and then the right
20:32half so what did we do at the first step
20:35place the pivot at its correct place and
20:37found out where it was placed and then
20:40called for the left and then called for
20:41the right so can I say okay let's call a
20:44function let's call a function which
20:47will do that so I'll tell the function
20:49that for this array low to high please
20:53find out a pivot place it at its correct
20:56place and tell me where you placed it
20:58like for this case you will be placing
21:00it here tell me where you placed it and
21:02I'll call that as partition index
21:05partition index
21:08done
21:09once I've placed it at its correct place
21:12I'll have other guys because after the
21:15algorithm after the function has taken
21:17place
21:18how will it look like it looked like
21:20something like two
21:21one three and this side will look like
21:24six
21:25five seven nine
21:27after the function has taken place
21:30so now you have to sort this portion of
21:32the array and this portion of the array
21:34and the partition index is here so can I
21:36again call it
21:38quick sort go for the left now which is
21:41from which is the array but in this
21:44array take from low to partition index
21:47minus one
21:48and in the right array take it from
21:52partition index plus 1 comma high again
21:56the lines can swap this can be at the
21:58first and then this can also be there it
22:00doesn't matter even if you swap it like
22:03this it's still okay because you have to
22:04sort the left and the right or the right
22:07and then the left any any way works as
22:10long as you are sorting it this is
22:12simple because
22:13the recursion will do its job because
22:15precaution has been called for this so
22:17again it will do a stop quite simple but
22:21the question comes up okay he understood
22:23till here but how do we write the
22:26function let's understand how do you
22:28write the function the function remember
22:30alighted with maybe a yellow
22:32the function has taken an array and has
22:36taken a low and has taken a high
22:39and you know it has to find a pivot and
22:41in our case the pivot is very simple we
22:44were saying the paper to be array of
22:46flow which is the first element
22:49and what did we do at every step if you
22:51remember we first kept I here and we
22:54kept a g here so let's do that so we
22:56said I is equal to array of low
22:59perfect
23:00or or maybe just just write it for the
23:03index I is at low and G is at high this
23:06is something which we said and what did
23:08we do
23:09we kind of said okay if I is here which
23:12is the first element greater than pivot
23:15and we've stopped here
23:17and then we swapped and we kept on doing
23:19this kept on doing this till
23:21I cross J and we had a left and a right
23:24so we kind of write okay
23:27keep on doing this
23:30so we keep repeating the steps now what
23:33are the steps
23:35find out because I was here
23:38find out the first guy that's greater
23:42than the pivot so okay while
23:46array of I is lesser than array of pivot
23:50that means it's okay this is not the guy
23:53that I'm looking for a 4 is less than
23:56equal to 4 I'm not looking for you I'm
23:58looking for someone greater than you so
24:00this is a correct condition and
24:02obviously I cannot exceed the arrays
24:05boundary which is definitely High
24:09it cannot exceed the RS boundary if
24:11that's the case we say okay I plus plus
24:15that means it keeps on going keeps on
24:17going till it doesn't finds an element
24:20greater so the moment it is at six the
24:22while loop will stop because that's
24:24where it has to and similarly from the
24:26right
24:28similarly from the right we say array of
24:31J from the right what do you need to
24:33find someone who is smaller so if this
24:36guy is greater than pivot
24:38if this guy is greater than pivot then
24:42what you will do is you will say Okay J
24:44again since you're going left
24:47just say this
24:49and you will say Okay J minus
24:53so what these lines will do is this will
24:56find the first element which is greater
25:00than the pivot and this will find the
25:01first element that is lesser than pivot
25:03and at the end of the day remember if
25:06they haven't crossed if they haven't
25:09crossed if you remember then you swap
25:11them you say array of I and array of J
25:15to be swapped quite simple
25:18quite simple and then you can close this
25:20this while loop gets closed here
25:23very very simple so if I have to show
25:26you the algorithm again
25:27let's do a dragon
25:29what happens first time I stops here and
25:32J stops here so 6 and 3 gets swept six
25:35and three next I will stop here next J
25:39will be stopping here so next one and
25:42five get swept next I goes and stops at
25:46seven because seven is greater than 4
25:50but J kind of stops here J goes here
25:53doesn't stops because 9 is greater J
25:55goes here doesn't stop because 7 is
25:57greater J goes your stops so if you see
26:00J has crossed i j has crossed I because
26:04J is at one so if J crosses I do not
26:07swap anymore because you are already at
26:10the left half three two one and you're
26:13already at the right half seven nine
26:16five and six you're already at the
26:18correct hubs so you do not do a swapping
26:21if they have cross they are already in
26:23the correct zones so at the end of the
26:25day where is J J is at here and Louis at
26:28here so that end of the day when this
26:31has this has crossed the Stop and we say
26:34okay it's time for the pivot to come
26:36it's correct please so swap the pivot
26:39which is the first element
26:41with the array of J which is the last
26:43element of the left index which is the
26:46last element of the left index so just
26:48swap it and this will come here and this
26:51will go here
26:52quite simple So eventually what you will
26:54get is
26:58three two one perfect that so once
27:02you've done this what do you need to do
27:04you need to tell them the partition
27:06index and you know the index is nothing
27:08but J because that's where the pivot
27:10came in so returns a this is how the
27:12function will look like quite simple
27:14this is how the function will look like
27:16again repeating find the first element
27:18greater than pivot find the first
27:21element smaller than paper swap again
27:23keep doing the same thing till you have
27:26an left and right once you have that
27:28just swap with the last level so if you
27:31are if you're able to understand this
27:32it's pretty much sharp also before going
27:35into the code I'll just like to mention
27:36one thing this portion is something
27:38which we have to be careful about and
27:41this portion is something again which we
27:43have to be careful about why because
27:45when you write this and you're doing I
27:46plus plus this might exceed the low to
27:50high array boundary because you are
27:53standing at the last and you're checking
27:54for the last and then then you're moving
27:56it might exceed the boundary so this
27:58instead of high will be high minus one
28:00this instead of low will be low plus one
28:02and there is other doubt that might come
28:05into your head why are we doing lesser
28:08than equal to and greater here now
28:11imagine you add 4 and you place three
28:15one two on the left and let's say five
28:17six seven nine on the right Boris please
28:20what if there was another four then he
28:22would have either place four on the left
28:24or either on the right so I will say on
28:28the left we will place everything lesser
28:30than equal to on the right we'll Place
28:32everything greater than equal to that's
28:34why we are finding greater and we are
28:37finding lesser over here got it why
28:39because you have to decide where do you
28:42put the equal to guys like if there is
28:44someone equal to weight you place them
28:46you have to decide on that as well so
28:49you place it on the left in that case
28:50you do it like this if you place it on
28:52the right then you have to do the vice
28:53versa I hope that does make sense so I
28:56can say that we are done with the pseudo
28:58code and the dry run as well because
28:59while I was writing the code I was doing
29:01the dragon as well and now going back to
29:03the recursive Dragon for these couple of
29:05things I'll recommend you to watch my
29:08merge sort video because in that I've
29:11explained how these couple of things uh
29:14split the arrays and how individual
29:16stuffs work so just in case you are not
29:17aware how the recursion Works merge sort
29:21tutorial is a classic example where I've
29:23done the entire Dragon so that you
29:24understand recursion in depth how sub
29:28problems are solved and everything
29:29by the way before moving uh to coding it
29:33in an online compiler I just wanted to
29:35quickly tell you something this is a
29:37divide and conquer algorithm because
29:39we're kind of dividing it and when you
29:42divide it every part is getting solved
29:44by itself so that's why divide and then
29:47you conquer basically solve so it's a
29:50divide and conquer algorithm
29:52now coming into the online compiler will
29:54be quickly coding the quick sort
29:56algorithm by the way the problem link is
29:58in the description make sure you uh code
30:01it as well and submit so coming to over
30:03here uh we have to return a vector so
30:06assume we have a quick sort we say array
30:09is 0 and array dot size minus one at the
30:12end of the day we are returning the
30:13array itself because we have to return
30:14it and now let's write the void quick
30:17sort and Vector end and then array and
30:20then IND low Indy high and we know if
30:24low is lesser than high then only we do
30:26it like for one elements or that we will
30:29not do it and we have to get the
30:30partition index and for that we can call
30:33the partition function
30:35and the partition function can take
30:37array low and high
30:39and then we can call the quick sort for
30:41array and low P index minus 1 and we can
30:45also call the quick sort for array P
30:48index plus 1 comma High that's it that
30:51is what I will do and over here we can
30:53say partition and we can say vector and
30:56array and we can take the low we can
30:59take the high and can I say that the
31:02pivot will be array of low we can say
31:05the array I will be this we can say the
31:07J pointer will be this if you remember
31:09well enough and we can just go on till
31:10ILS then J and we know that we have to
31:13go on
31:14till finding the first element that is
31:17greater than pivot on the left so we go
31:20on till it is less than equal to and we
31:23stop at lesser than high minus 1 so that
31:26it doesn't crosses the boundary when we
31:27do I plus plus and we also on the right
31:31have to find the element that is smaller
31:33so we go on till it is greater than
31:36pivot not equal to because the equal to
31:39guys will be on the left and then we go
31:41on the same reason low plus 1 that we do
31:44not cross it and at the end of the day
31:47if they haven't crossed let's take the
31:50right guys put them onto the left and in
31:52the left guys put them on to the right
31:53the swap of array of I array of J
31:56perfect at the end once everything is
31:58done we know J will be at the last of
32:01the left so swap the pivot which is at
32:04array of low with the last of the left
32:06and since the pivot goes to J we say
32:08that's the partition index that's how
32:10you can write the partition once you've
32:12done this you can quickly go and run
32:15this all right it's giving me time limit
32:17exceeded why is that happening
32:21because I've written less than equal to
32:23it will be greater than equal to
32:24my bad it All Passes Now quickly let's
32:27submit it and see if it's running
32:29absolutely fine
32:30it is so now moving back uh to the iPad
32:33to discuss the time complexity so the
32:37time complexity of this particular
32:39algorithm is n log n y is it n log n
32:44again the same reason as merge sort
32:47because every time you're kind of
32:50splitting them into two halves now over
32:52here the halves are for sure getting
32:55into like something and something then
32:57again this is getting into something and
32:58something so it's kind of not getting
33:01equally split as in most shot but
33:04they're getting into a couple of halves
33:06so this half will be going on like the
33:08height of the tree if you remember the
33:10more short video will be log base to n
33:12that's how uh because 2 to the power
33:14something log base to n and y n because
33:18every partition every this function is
33:22going through the entire array itself so
33:24it's a big O of n for everything so n
33:27cross it log n and the space complexity
33:29we are not using any extra space yes
33:31there is a recursion stack space but
33:33let's not compute it so the this is the
33:36time complexity in the space complexity
33:37I did not explain any login in depth
33:40because this is a continuous course I'm
33:43assuming you have seen the merge sort
33:45video where I've discussed in depth
33:47about n login so go back and watch it
33:49because over here we perform the similar
33:52kind of recursion calls so it's very UNL
33:54like this being big of n is self
33:57explaining why big often because you're
33:59moving I from low till high and you're
34:03moving J from I to low that's a b go off
34:06and it's a very obvious case and for
34:08these couple of things it's log n so
34:11comes from my shot I've explained that
34:13over there so the time complexity is l
34:15login and the space complexity is Big of
34:18one not taking recursive stack space
34:20into account so that's the time
34:21complexity and space complexity so with
34:24this I can say I have wrapped up more
34:26shot as well and the couple of notes
34:27will be added very very soon so guys
34:30with this we complete step two of
34:32Strivers A to Z DSA course the next
34:35thing will be step three where we will
34:36be starting with the arrays playlist so
34:38guys I hope you have understood the
34:39quick sort algorithm in depth so just in
34:42case you did please make sure you hit
34:43that like button and if you're new to
34:45our Channel what are you doing kill that
34:47subscribe button right away and to
34:49continue our tradition do comment
34:51understood so that I understand that you
34:52have understood everything and also as
34:54an assignment yes as an assignment you
34:57have to write this code for descending
34:59and you have to paste that code in the
35:01comments I'll be checking out the
35:02comments for sure and here with this
35:04I'll be wrapping up this video let's
35:06read in some other videos till then bye
35:07bye take care
35:10don't ever forget your golden I will

About this transcript

This page contains the full transcript of Quick Sort For Beginners | Strivers A2Z DSA Course by take U forward, generated from the public captions YouTube serves with the video. The transcript has 6,431 words across 867 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.