Analysis of Quick Sort and Problems on It, Programming and Data Structures, CSE, GATE Video Lecture - Computer Science Engineering (CSE)

so taking this quicksort we shall see
some interesting inputs for this so one
interesting input is if the entire input
is in ascending order which means if the
given input is like this one two three
four five six then what happens if you
apply the quicksort what is the total
time required so further just observe
this if I call the partition on this
input partition will take six as the
p-word the last element as the pivot and
as usual J will try to find out an
element which is less than six right J
will start from the first element till
the last but one element and you try to
find out some element which is less than
six and I will stop I will start from
one element less than J all right then
what happens
J has found the element which is lesser
than 6 then I will get incremented then
they will be a swapping which means
exchange a of I add a of j which means
one will be there then J will be
incremented right and now what happens
J is J with J has been incremented and
again we found an element which is less
than 6 then I will be incremented and
again these two will be exchange
exchange means the same element will be
there same thing happens here jay and i
j and i right which means j will keep on
finding an element less than 6 and i
will try to come there and will exchange
it with itself right then J and I so
this is where J is going to stop so
after this stops then we are supposed to
exchange I plus 1 with P word so what is
I plus 1 6 only xj 6 physics so that
nothing is going to change only thing is
after partition six-feet be in its right
position exact correct position then
again we have to call quicksort on the
elements left to that and fix what on
the elements right to that right there
are nothing right therefore if the
element you know if the array is in in
ascending order
if the ascending order input is given
then the total time taken to sort and
element
we'll be first thing is we are applying
the partitioning algorithm which is
going to take order of endtime isn't it
for the partitioning algorithm and now
we got a subproblem whose size is only
one element less this is what we got
right so even if you apply one more time
we get the same thing isn't it and this
is going to happen continuously see if I
apply partitioning on this again this
one will be taken as P vote and this one
will be J will start from here and you
will try to find some element less than
or equal to 5 and I will start from
outside right so initially for an
element which is less than 5 then I will
be incremented and a off I and a object
be exchanged which means 1 will be
exchanged with 1 so 1 is going to be
there all right and then J will they
will again find the next element which
is less than 5 I will be incremented and
exchanged J will again find an element
less than 5 I will be incremented and
exchanged J will be again finding an
element less than 5 I will be
incremented and exchanged so we got we
are going to get the same thing right
only thing is after this again we are
going to see that the size of the
problem is exactly 1 less than the size
of the previous problem therefore this
this rule holds which means T of n equal
to order of n plus order of plus 30 of n
minus 1 if we solve this by putting some
constant C n so in order to solve this
you can put your value C and here and
you can do that back substitution we
have already seen that so we can find
out that this time complexity is order
of n square therefore if the in the
input is in ascending order then the
time taken to sort that is order of n
square let us see one more input which
is in descending order if the input is
in descending order like 6 5 4 3 2 1 if
the input is descending like this then
initially you are going to call fixate
on this then fixed sort is going to call
pivot on this then if you're a sorry
partition on this and partition is going
to pick the last element and
P what right and what will i J do J will
try to find out an element which is less
than less than the P won't so which is
less than 1 so it will scan the entire
list till this part and it will fail to
find any element which is less than 1 so
J is going to stop there and I will be
wherever it was 1 less than J initially
right and finally J is no we are going
to exchange the pivot element with I
plus 1 which means this element will be
exchanged with pivot element 6 right now
this is where the pivot element is
located right so we found out that the
entire problem if the problem given is
of size n then we are going to apply the
partition algorithm partition algorithm
J is going to run from here to here
therefore time taken is order of M after
that the size of the problem is reduced
only by 1 which means T of n minus 1 I
have to solve it again right so even if
you try to solve this again then you
will see the same thing see this now if
I try to solve to apply quicksort from 5
to this 6 then 6 will be taken as the
pivot element initially and J will start
so that it will find the element less
than 6 so initially I will be here 1
less than J now J has found an element
less than 5 then I will be incremented
and these two will this fact if I swap
we are going to get the same then J
willing J will get incremented until
again find an element less than 6 then I
will be incremented and dense fact which
means we get the same then again J will
be incremented and we found an element
less than 6 therefore I will be
incremented and these two elements a of
journey of I have to be swept which
means I get this N and J will be
incremented again J will find an element
less than 6 therefore I will be
incremented and these 2 will be start
again I get the same so J is going to
start from here and it is going
and here and finally what would happen
this P what has to be exchanged with I
plus 1 I plus 1 is same so P what is
this P what location is this right so
now the problem is again divided into n
minus 1 only isn't it if the given
elements were 1 2 3 4 5 then I got a
list of 1 2 3 4 so this rule is
following which means if the given
element sizes with the given array size
is n then I am going to apply
partitioning for which the time taken is
order of n and then the problem size is
reduced exactly by 1 so even if you
solve it it is going to be order of n
square so even if the input is in the
ascending order or in the descending
order the time taken is going to be
order of n square and both the times are
same and one more interesting input is
if all the if all the input you know if
the area contains all the numbers which
are equal which means if I get n this 2
2 2 like this if the entire array
contains the same elements then how are
we going to solve it so first thing is
this last element is going to be pivot
element see if I call the quicksort on
this then quicksort is going to call
partition on this slide so this last
element is chosen as pivot element then
J will try to find an element which is
less than or equal to 2 so J will start
from here and you try to find an element
less than or equal to 2 s it found it
therefore I will be incremented and a of
ayodhya of J will be you know exchange
which means 2 will remain there itself
then J will go to the next element and I
will be incremented right
I mean J has found the element which is
less than or equal to J has found an
element which is less than or equal to 2
therefore I will be incremented and
again exchange which means same then
again J will be incremented and it will
find an element which is less than or
equal to 2 therefore I will be
and swept which means same J will be
incremented it is it has again found the
element less than or equal to two I will
be incremented right and against fact
the same thing is going to happen
finally I plus one has to be exchanged
with the P vote right so which means by
the end of the partition algorithm this
two is going to remain in its same
location which means the partition
algorithm is going to return that the
size of the problem is n minus one so
after one partition algorithm we are
going to if I have to sort n elements in
which all the elements are same then I
am going to apply the partition method
which is going to take order of n time
and then I am going to get a list whose
size is n minus 1 right the same
algorithm therefore it is going to take
order of n square right so either if the
input is ascending or the input is in
the descending order or if all the
elements are going to be same then also
it is going to be vol the input you know
size is going to be same the order of
the time compressed is going to be order
of n square so ascending descending and
same elements all are going to have the
same complexity which is order of n
square so if you analyze the time taken
by this quicksort it is mainly because
of the time taken by the partitioning
algorithm isn't it so what is
partitioning algorithm doing so
partitioning algorithm is going to take
order of n time and it is going to place
exactly one element in its correct
position in worst case what happens is
in order to put every element in its
correct position I might have to call
partition which means I might call
partition n times and every time if it
takes order of and time then it is going
to take order of n square time that is
what is happening here so every time
partitioning algorithm is going to take
see this initially there will be n
elements right then it is going to take
order of n time which means see and time
so why is this happening is I will just
show you so the major part of the time
taken
this quicksort is because of the
partitioning algorithm isn't it now if
the partitioning algorithm is how much
time is it going to take if the input is
of size n then the partition algorithm
is going to take let us say some
constant into n which is nothing but
order of n time right this is the size
of the input then this is the time taken
by partitioning algorithm then what is
it doing it is trying to place one
element in its correct position right
then what is happening in the previous
problem since only one element is
getting placed in the partitioning
algorithm by the partitioning algorithm
and then all the N minus 1 elements are
remaining as it is right then what is
happening is again for the remaining n
minus 1 elements we are again going to
call the partitioning algorithm which is
going to take C into n minus 1 time and
going to put only one element in its
correct position then how many elements
were remaining n minus 2 then again we
are going to call partitioning algorithm
on the complete n minus 2 all right
that is where it is getting like this
but then only one element is going to be
placed so on finally I get one element
all right then if we add all of them it
is going to be order of n square got it
so there also known there are some
proofs we shall see some more problems
and analyze the quicksort time
complexity again so for now you remember
that either it is ascending order or
descending order or the given elements
are same the time complexity taken by
this quicksort is worst case time which
is nothing but order of n square and
what is the best case time best-case
time we have seen that if the partition
algorithm is going to partition the
array array into two equal halves then T
of n in the best case partitioning
algorithm is always going to take order
of n time and in the best case if both
the problems are going to be partitioned
equally nearly equally then we are going
to get n log n time this is the best
case in best case we are going to get n
log n which is close to merge sort and
in worst case we are going to get order
of n square and now just now we have
seen the inputs which will lead to order
of n square
ascending order descending order and
same elements right so let us see what
happens if if it is not you know if
every time we are dividing it like this
1 and n minus 1 sorry 0 1 0 and n minus
1 and then 0 and n minus 2 and then 0
and n minus 3 this is what we have seen
instead of this if there is some ratio
in which we are dividing our the input
into like one tenth of the input one
side and nine by tenth of the input
other side let us see what happens with
that input so in the previous three
examples we have seen that initially n
side was the input and I was dividing it
into 0 and n minus 1 and again 0 and n
minus 2 and again 0 and n minus 3 and at
every level the work done is nearly
order of M right so work done is nearly
order of n right and how many such
levels are there n levels therefore
total work done is order of n square
that was a time complexity although we
got order of n square if it is ascending
or descending order of same sequence
right what if what if the partitioning
algorithm is going to split the input in
such a way that the size of two lists or
the size of two sub-problems we get or
in the ratio of 1 is to 9 which means if
you are giving me a size n elements as
the input then it is going to divide
into n by 10 and 9 and by 10 right so
ratio is 1 is to 9 then it is doing it
constantly which means every time it is
going to give me the split one is to 9
so previous examples where 0 and n minus
1 but now it is n by 10 and 9 9 by 10
then what happens is n by 109 and by 100
9m by hundred right
81 n by 100 right so so on so on this
will reach one element right and then
this will be next time it will be 81 n
by 1000 79 by 1000 n right and so on it
will reach one element right but then if
you see the depth the depth of the this
know this left side child is going to be
less compared to the depth of right side
child but at every level the total work
done will be order of M right either you
run it on complete and elements or n by
10 elements and 9m by elements the
partition algorithm has to actually run
the J that J loop over all the elements
so here all the N elements here n by 10
elements first and 9 n by 10 so however
the total work done is going to be order
of n only right so let me call it as
some constant C into n so C into n C
into n and this is also going to be C
into n as long as all the levels are
full so till this 11 it is going to be C
into n and then after that the elements
are going to stop here right so some of
the elements are going to stop here and
is going to continue which means here I
will not have for the next level and the
demands that will be less than n
elements which means less than C into n
less than C into n and finally it is
less than C into n element no work so
the work done is going to be decreasing
so it is going to be C into until some
level and after that it is going to be
less than C into n right then if the
work done at every level is like this
then how many levels are you going to
have at max right at max you can find
out that the number of levels in this
tree see this
the levels are decreasing like this at
first of all the size is n and at the
second level size is M by 10 by 9 and at
the next level the size is n by 10 by 9
whole square
right so on it is going to reach one
which means it is not decreasing by half
it is decreasing by 10 by 9 therefore
how many levels will be there here it
will be log n to the base 10 by 9 and
you can think of it as it is nearly
equal to log and base 2 or you can say
that this is equal to theta of log in
base 2 they know there will be some
difference definitely but then you can
by putting some constant here by
multiplying with 0.1 or 10 you can say
that these two are like this related by
this therefore number of levels in this
are roughly equal to log in and at every
level we are doing a work of CN
therefore what is the total work done so
total work done is nothing but theta
into theta of and log n right so from
this we have seen that even if the split
is one is to mine at every level we are
going to get the best best case time
complexity which is order of n log n so
it can even be proved that even if this
split is one is 299 or even if the split
is one is to 999 at every level then
also the you know we might get the best
case time complexity theta off and log
in keep this in mind so if the split is
not as bad as 0 n minus 1 then we are
going to get no in the on average n log
n as the time complexity right so one
more interesting one more interesting
thing is let us say at one level we are
getting the best time complexity and the
second level we are getting the worst I
mean at one level we are getting getting
the best case and at next level we are
getting the worst case if the cases are
alternating which means it fit every
level this proportionality is not being
followed let us consider one more
example let us say we are given n
elements to sort we are given n elements
to sort then after applying partitioning
algorithm which will take see
and time I got the worst case inputs
which means one side I got zero and
other side I got n minus one elements
worst case right and again on this n
minus one elements I have done is C into
M nearly two C into n minus one constant
time work then again now I got best case
split what is the best case played n
minus two elements by 2 n minus two
elements by two the reason is why am i
writing like this is there is like this
series n minus 1 elements out of which
one element will be placed in its
correct position then how many elements
will be remaining n minus 2 elements now
let us assume that that n minus 2 is
evenly on the right-hand side and the
left side of the pair of the pivot
element then the problem sizes could be
like this right
in this case see what happened initially
I had to sort n elements for which time
taken is T of n for which I did a total
work of C n and C n which means C n plus
C and work I did right plus then the
problem got divided into two subproblems
right and each of size the problem now
got divided into two subproblems each of
size n minus 2x2 and if this keeps on
happening which means next level it is
bad split and next level it is best
split bad and best if they are going to
alternate that is that is you know if
that is the case then this is what I am
getting thread then what is this
this is to C n plus 2 into T into n
minus 2 by 2 now this to C is nothing
but a constant therefore I can write it
as order of n plus now instead of
writing n minus 2 if I put n what
happens
definitely right hand side is going to
increase then I can put less than or
equal to 2t n by 2 instead of this n by
2 I am putting n therefore the right
hand side is it
going to be more therefore I am putting
less than or equal to then if you solve
this equation you get theta of n log n
by master's theorem right so even if the
split is one level it is worse split and
second level best split next level worst
bit next level best best split even if
the input is alternating like this then
also I am getting the best you know time
complexity which is close to equal to
the best case time complexity right so
remember this we are going to say that
the worst case time of insertion sort is
order of n square but that is not always
the case
the reason is even if it is known each
two nines plate or one is 299 split or
even if it is best and worst combination
then also I am getting n log n right so
the only cases where I might get order
of n square is 0 and n minus 1 0 n minus
1 0 and mess and so on which is nothing
but ascending order descending order or
same elements for such elements we are
going to get order of n square otherwise
we are going to get get off and login
right so let's see some problems on this
on this insertion sort look at this
fashion the median of n elements can be
found in order of n time so what is
median is the value which which is
supposed to be the midpoint right so if
I have you know if I have n elements
then I don't I am not sorting them but
then I can find out what is the average
of it or what value of it is going to
fall in the middle if I spot it out ok
median is that so median is nothing but
out of all elements if I sort them what
element is going to fall in the middle
that element is called median ok now
they are saying that we can find out
median of n elements in order of n time
then which one of the following is
correct about complexity of quicksort
they are talking about if I use this
method in order to find out the median
and then what will be the complexity of
the quicksort
okay so quicksort they are saying that
they are going to use the median as VP
element right so how can I use the
median as a pivot element so take that
partition algorithm okay not that
partition algorithm was selecting always
the last element as the pivot element
right then what you could do is first
step is given an element right when you
run the partition you are going to find
out that some element is the median so
before the first given an elements or we
can find out in order of n time what is
the median right and then you replace
that median at the end you put it at the
end and you take the last element it is
Farid for which time taken is constant
time right and now we apply the
partition on these n elements for which
time taken is order of M right so after
applying the partition algorithm on this
then what do you get finally we are
going to partition the entire list so
since this element is supposed to be in
the middle we are going to get two lives
exactly of size n by 2 and n by 2
not exactly roughly of size right
therefore first find out the partition
first find out the median for which time
taken is order of M and then put the
median at the end of the list whatever
you wanted to sort and then you call the
partition algorithm right and now we get
two problems which are roughly of size n
by 2 and n by 2 all right
therefore you know if you write the time
complexity if I have to sort n elements
then apply the find the median so how
much time is it going to take order of n
time right and then you replace the
median with the lost element and then
you call the partitioning previous
partitioning algorithm see I am
replacing the median with the last
element because our partition algorithm
was choosing the last element as the
pivot element right but if your
partition algorithm is choosing the
first element as the pivot element then
you replace the median with the first
element that depends on what your
algorithm is ok so my algorithm is
choosing the last element as the pivot
element my partition algorithm that is
why I am placing it at the end then you
run the partition algorithm
for which time taken is order of M huh
now after running this now the problem
the entire problem is going to become
almost two problems of equal sizes right
why because the element is median then
what I am going to put here we are going
to put two t n by two roughly right then
what about this n type thing
this another thing is going to add up to
order of M order of M plus two T n by
two now you apply master's theorem then
we are going to get the time complexity
is as n log n that is what is given okay
see this problem they are saying that in
a quicksort for sorting n elements so
now we have to sort n elements the N by
fourth smallest element which means out
of all elements whatever is the n by
fourth smallest element is selected as
pivot right so now for the partitioning
we are going to you n by fourth element
as the pivot element using order of n
time algorithm so using water of n time
algorithm we are going to find out what
is the N by fourth smallest element and
now we are going to give it as you know
devote then what is the worst case time
complexity of quicksort so what you do
is you better pause the video and you
read the question once and you
understand it in the question they are
saying that I have an array of size n
okay then if I run a order of n time
algorithm then I can find out some
element that element of the sorting the
list is will fall in the place of n by 4
which means that element will be here 3
n by 4 elements will be here after
sorting it right I can find out such an
element in order of n now if I am going
to use such an element as a pivot
element then what will be the worst case
time complexity of quicksort that is
what they asked right
so how to analyze this let us say I want
to sort n elements right then first
thing is you run this order of n time
algorithm okay I am run
therefore time complexity is order of n
to run this algorithm then I found out
the element which is supposed to be n by
fourth smallest then what I do is I will
exchange that element with the last
element and then run my partitioning
algorithm right now partitioning
algorithm is going to take for
exchanging know that element with the
last element constant time is taken and
then my constant you know partitioning
algorithm is going to write so which is
going to run for this after my
partitioning algorithm what happens is
pivot is going to sit exactly at its
position and to the left of it there
will be nearly an by four elements and
to the right of it there will be nearly
three and by four elements right
therefore now the problem with ten
elements has is resolved into two
problems one of size n by 4 and other of
size 3 n by 4 which means T of n by 4
and other is T of 3 n by 4 all right
then
it is nothing but T of n equal to order
of n this entire thing I can write it as
order of n plus T of n by 4 plus T of 3
n by 4 right so this is nothing but
using an order of n n time algorithm
I am partitioning the input in a ratio
of 1 is to 3 and I have already shown
you that even if the problem has been
broken into the ratio of 1 is to 9 then
r1 is to 99 or one is to 9 9 9 even if
the problem has been broken like this
still the time complexity is n log n
right therefore definitely for this 1 is
to 3 we get theta of n log n because it
is better than 1 is 2 9 right
and what about 1 is to 1 for 1 is to 1
we have seen that it is going to be n
log N and for 1 is to 3 definitely it is
going to be n log n all right fine
and one question is this they are saying
that we are using quicksort to sort all
the elements and using quicksort using
quicksort if I run fixer on some
algorithm they are saying that if the
input is 1 2 3 4 5 then the time
complexity required is t1 and if the
input is like this they are saying that
if the input is 1 2 3 4 5 so on M which
means all the elements are in ascending
order then the time taken is t1 and they
are saying that if the input is n n
minus 1 n minus 2 so on 1 then the time
taken is t1 then they are asking you
what is the relationship between t1 and
t2 we have already seen that either if
the time no if the elements are sorted I
mean ascending order or descending order
or if the elements are all equal then
also we are going to get t1 equal to t2
equal to Big O of n square so in this
case t1 is equal to t2 right and in
other problem they are saying that so
using a using a partitioning algorithm
which takes order of n time we are
splitting the problem into two parts one
part contains 1 by 5 elements and the
other part contains 4 by 5 elements
right then what do you say about the
time complexity right then how can you
write the time complexity T of n is
equal to order of n plus T of n by 5
plus T of 4 n by 5 okay then then how
can you again simplify it is so it is
less than or equal to Big O of n plus h
1 is bigger I cannot write 2 into T of n
by 5 I can write 2 into T of 4
by five-o you why because this factor is
less than this factor and I am replacing
both the factors with for my five
therefore I can write like this okay so
these are some of the questions which
have been asked in the exam about a
quicksort okay