2.8.2 QuickSort Analysis

[0:00]Now let us look at analysis of quick sort, let us analyze it. Find out its time complexity. See, one important thing is it's 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 pivot 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 quick sort 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 at 12, 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. Partitioning is at 10, here 9 to 9, here 11 to 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 how for every node I have written partitioning. So, the working of the quick sort will be like this. Then if I analyze this one based on the tree, 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 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 n. 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, divided by 2. As the partitioning is always in the middle, half, half this side, divided by 2, by 2, by 2. Then 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, one, one element. So, this is n by 2 power k equals to 1, and n equals to 2 power k. So, k is log n base 2. So, yes, how many levels are there? Log n 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 quick sort will be order of n log n. Assume that always partitioning is done in the middle of a list. So, that assumption has given us this time. 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 quick sort is n log n. And this we are 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 sorted list. Then, best case of quick sort is always the partitioning should be in the middle. So, if partitioning is in the middle means the element that is selected as pivot 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 at 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 quick sort. You cannot achieve it. It may randomly happen that always the element is median. What is the worst case of quick sort? Suppose I have a list 2, 4, 8, 10, 16, 18, 17. Suppose I have a list which is already sorted. Then if I perform quick sort, how it works? Partition algorithm we saw, it will select the first element as pivot, and it will start I here and J 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 where 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 4, where it will be partitioned? Where 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 quick sort. If I give the numbers from 1 to 7, then 1 will be sorted. And this side I get 2 to 7. Then 2 will be sorted, and this side I'll get the number from 3 to 7. Then 4 to 7, then 5 to 7, 6 to 7, and 7 to 7. Now you can see that always the partitioning is happening on the beginning of a list or it may happen at the end of the list also. It depends. Here it is 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 comparisons, then n minus 1 comparisons, n 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 squared. That's it. The worst case time of quick sort is n squared. Best case time of quick sort is n log n, which is not possible for us to achieve it, but worst case time is n squared. And when it will happen, if the list is already sorted. So, this is the problem with quick sort, that its worst case is n squared. If you compare this with the merge sort, merge sort was not having any best or worst cases, it was just average time n log n. But here, the average time is n log n, but the worst case is n squared. 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 the sorted order, we may 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 quick sort. So, what we do is, we say that, don't always select the first element as pivot. You can select the middle element as pivot. 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 pivot, 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 squared to n log n. The worst case will become best case. There are two suggestions for improving the worst case of quick sort, removing worst case of quick sort. Always select middle element as pivot. 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 squared for some element, some arrangement of elements. Other suggestion is, randomly select some element as pivot. If you randomly select some element as pivot, again, it may be possible that it may take n log n time or maximum again n squared time. So, always the worst time taken by quick sort is n squared. About the space complexity, quick sort 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 quick sort takes stack size that is log n to n. So, how you can know this? Just now I 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.