2.8.2 QuickSort Analysis

now let us look at analysis of quicksort let us analyze it find out its time complexity see one important thing is as a recursive and it is following divide and conquer strategy it is using partitioning procedure partitioning algorithm and the partitioning algorithm will find out the position of P vote and it will divide the list suppose I have the list of elements let us say 1 through 15 I have a list of 15 elements then if I call quicksort by passing first index as one and last index as 15 suppose it is partitioning at the middle then I am getting elements from 1 to 7 on this side and 9 to 15 on this side so partitioning was done at index 8 that is at the middle of a list so elements 1 to 7 here and 9 to 15 on this side suppose the partitioning is done in the middle assume this then what about this left-hand side this part and this part assume always partitioning is in the middle then here the middle element will be 4 and this side we get a list from 1 to 3 and in this side 5 to 7 similarly if it is happening here then the partitioning will be ad to well middle of a list then we get the elements 9 to 11 here and 13 to 15 suppose partitioning is again in the middle then I get one element on this side that is 1 to 1 and 3 to 3 here the partitioning is on 4 so then 5 to 5 and 7 to 7 parsing is at 10 here 9 to 9 here limit 11 and here 13 to 13 14 partitioning is done 15 to 15 if partitioning is always done in the middle I have given 15 elements and suppose the partitioning was at 8 and that's all for every node I have written partitioning so the working of the quicksort will be like this then if I analyze this one based on the trainee what the partitioning algorithm is doing it is comparing the element and exchanging them so what is the time taken by this algorithm it is n it will go through an entire list so the time taken for this is n and the time taken at this level this left side and right side together is almost M no doubt one element is reduced but let us say it is n then at this level also it is N and that's all that is the end of the level then what is the height of a tree see it was 15 / - is it as the partitioning is always in the middle half half the side divided by 2 by 2 by 2 when something is getting divided by 2 every time how many times it will divide such that it reaches 1 so if you say n by 2 then by 2 then by 2 so how many times such that it becomes 1 1 1 element so this n by 2 power K is equals to 1 and n is equals to 2 power K so k is log n B is 2 so yes how many levels are there login levels are there and in each level what is the time taken I am assuming that partitioning algorithm will compare the elements for n times so it's n so the time complexity of quicksort will be order of n log n assume that always partitioning is done in the middle of a list so that assumption has given as this so this will be best case of an algorithm what is the case if the partitioning is always in the middle and what is the time in best case it's order of n log n so the best case time of quicksort is n log in and this will going to achieve only if the partitioning is done in the middle let us see whether this best case is possible or not for that let us know about median what is median if I have the numbers 1 2 3 4 5 6 7 the numbers are sorted and this is the middle element of the sorted list and this is called as median so median is the middle element of self sorted list then the best case of quicksort is always the partitioning should be in the middle so if partitioning is in the middle means the element that is selected as P word should be a median so how can you know median unless the list is sorted we cannot know the median so is it possible that always the element selected is a median and it is sitting in the middle of a list partition in the middle of a list it's not possible randomly it may happen but we cannot control it so achieving best case is not possible in quicksort you cannot achieve it may randomly happen that always the element is median what is the worst case of quicksort suppose I have a list to food 8 10 16 18 17 suppose I have a list which is already sorted then if I perform quicksort how it works partition algorithm we saw it will select the first element as pie wood and it will start I here and here I will continue until it finds a greater number so here and J will continue until it finds a smaller or equal number so it's not small not small it's not so it will come and stop here then way the partitioning will be done at the same place now this is sorted so rest of the elements we have to sort so you can see that partitioning will be done in the beginning of a list because the list was already sorted now from this list if I select four where it will be partitioned very it will be positioned finally at the same place again so always the partitioning will be happening in the beginning of a list that is the worst case of quicksort if I give the numbers from one to seven then one will be sorted and on this side I get two to seven then two will be sorted and this side will get the number from three to seven then four to seven then five to seven six to seven and seven to seven now you can see that always the partitioning is happening on the beginning of a list or it can happen at the end of the list also it depends here it is all sorted in ascending order if it is in descending order always will be at the end now what is the time taken here first partitioning algorithm takes makes n combinations then n minus 1 comparisons and minus 2 and so on so 2 then 1 so what is this equal to this is equal to n into n plus 1 by 2 that is order of n square that's it the worst case time of quicksort is n square worst case time is order of n square best case time of quicksort is n log n which is not possible for us to achieve it but worst case time is n square and when it will happen if the list is already sorted so this is the problem with quicksort that it's worst case is N squared if you compare this with the mossad more sort was not having any best or worst cases it was just average time and logon but here the average time is in log n but the worst case is n square now we need to solve this one how can we reduce this problem see the probability that if the list is already sorted we are again sorting it the chances are high because we want to keep the list in sorted order we will be sorting it again and again so if it is already sorted and you are sorting it then the time is going to be N squared so this is the problem with quicksort so what we do is we say that don't always select the first element s by vote you can select the middle element as before if you select middle element then what happens if you select this one where it will come it will come here only so the partitioning will be done here if partitioning is happening here then the list gets divided into two equal halves that's it if always we select the middle element as pie wood then the partitioning will be done always in the middle of a list because the list is already sorted and that's how it will convert from n square to and log in the worst case will become best case there are two suggestions for improving the worst case of quicksort removing worst case of quicksort always select middle element as pie wood so if the list is already sorted it will become best case that is n log n but still the maximum time will be n square for some element some arrangement of elements other solution is a randomly selects some element s by wood if you randomly select some element SP wood again it will be possible that it may take a log in time or maximum again in square time so always the worst time taken by quick sawdust and square about this complexity quicksort is a recursive algorithm and it doesn't need any extra space but it will use a stack so what could be the maximum size of the stack in worst case it may be n what is the minimum size of the stack in best case the height may be log n so the quicksort takes stock size that is log in to n so how you can know this just now have shown trees in best case the height of a tree was log n so the size of the stack depends on the height of a tree tracing tree and in worst case it was n so maximum size of the stack may be n so that's all about the quicksort this is the

Channel: Abdul Bari

Views: 608,342

Keywords: quicksort, quick sort, algorithm, algorithms, quicksort algorithm, quick sort analysis, quicksort analysis, abdul bari, bari, gate

Id: -qOVVRIZzao

Length: 11min 37sec (697 seconds)

Published: Thu Feb 01 2018