[0:00]Hi, the topic is quick sort. First of all, let us understand what is the idea behind quick sort, on what basis it works, what is the base idea about it? So let us take an example. So the idea is if suppose there are group of students in a class and a teacher asked them to arrange themselves in the increasing order of their height. There are two options: a teacher can show their places like you go there and stand at the back, you come here and stand in the middle or front, whatever it is. So the teacher can show places to the students, this is one option. Second option is teacher can ask the student to arrange themselves, so every student will find his place in the sorted order. So the faster method or quick method will be the one if the students are finding their place. So yes, this is the idea of quick sort. So let us see, I have taken some icons here, some picture here to show you. Now if I ask the students to arrange themselves in the increasing order of height, the shortest person in the class, he knows what is his place. He will quickly come and stand in the beginning of a list. Nobody has to help him, he can check himself or you are there or I am there in the class, who is shortest in the class, then I can know that my place is in the beginning. I can simply go and stand in the beginning. Now, if you are the tallest person in the class or a student is tallest, he knows that I am the tallest of all, he will simply go and stand at the back. Nobody has to help him and nobody has to show his place. Then the rest, they will arrange themselves. How they will arrange themselves? Like let us take this guy, what he will do? He will ask these guys that you are taller than me, you better go at the back and he will ask that person that you are shorter than me, you come in front. So others will find their places by arranging each other. Like suppose I have to stand in the line, I have to stand in the queue, so then I will see that where I should come. I will see that the person who is taller, he should be at the back of me, so let him go at the back and short person should come in front and they will find my place. That is the idea of quick sort. Now I will write few numbers: 10, 80, 90, 60, 30, 20. Which element is obviously sorted in the list? This one. 6, 3, 5, 4, 2, 8, 9.
[3:07]Which element seems to be sorted in its sorted position? This element is in sorted position. Because all the elements before that element are smaller than this one, and all the elements after that element are greater than that element, then that element is in sorted position, rest of the elements may or may not be sorted.
[3:45]So this is the idea of quick sort, quick sort works on this one. And that's how the name comes quick. So like a student can quickly arrange themselves, so that's how this is the quick method for sorting, but this is not the fastest method of sorting. The name is quick. Now let us look at the procedure of quick sort. Quick sort is a divide and conquer algorithm, it follows divide and conquer strategy. So it means it will split the problem into sub problems and solve those sub problems. So let us see how it works. So I'll make initial setup first of all, then I'll show you the working. So the initial setup is this is L low, that is the beginning of a list, and this is H high, that is end of a list. I have total nine elements, this place is empty, I have taken it. Now I will add here infinity, that is maximum number. Infinity is not defined in computer, so we take some maximum integer. That will act as end of the list. Like in strings we have slash zero, null character, that is string terminator, here we have taken infinity to show the end of a list. Otherwise we should know that there are nine elements or 10 elements or 20 elements, we should work according to length. Instead of that we prefer taking end of list marker. Then first element I will select as pivot. So pivot is 10. Pivot is 10. So it means I want to find the sorted position of this 10. Where this 10 should come? 10 should come at a place such that all the elements smaller than 10 should be on left side and all greater should be on the right hand side. For that I should check if any greater number this side, I will send it on that side. If any smaller on that side, I will bring it in this side. So for doing so, I will take I starting from pivot and J starting from infinity. I will search for the elements which are greater than 10, that is pivot, and J will search for the element which are smaller than pivot. So that they can exchange the numbers. All right. So I at most it will stop at infinity, J it will at most stop at pivot. Maximum, if it is not getting anything, it will at most it will stop at pivot. Now let us see the procedure. The procedure what we will do now is called as partitioning procedure. First I will perform the procedure, then I will write then I will write down the algorithm for partitioning. Let us start. See, increment I until you find an element greater than 10, so the next element is greater than 10 only. Decrement J until you find the element smaller than or equal to pivot, that is 10. Yes, this is smaller, exchange them. Five comes here, 16 goes there.
[7:07]One swap. Continue, increment I until you find a pivotal element greater than pivotal element. Eight, is it greater than pivot? No, 12 is it greater than pivot? Yes. Now decrement J until you get an element smaller than pivot.
[7:42]This is smaller, stop. Three this side, 15 that side. Continue, is it greater than 10? Is it greater than 10? Yes, I comes here, decrement J, is it smaller than 10? Yes, this is smaller than 10, stop here. That's all, don't interchange I and J element because I became greater than J. I has crossed J. It means we found the position of pivot. What is the position? J, wherever J is pointing, that is the position of pivot. So send that element here and take 10 as this position. Now this is sorted, this list is not yet sorted and this list is not yet sorted. You can see that all the elements on this side are smaller than 10 and all the elements on that side are greater than 10 and these are not sorted. These are not sorted and even those are not sorted, we have to sort them. Then who is sorted? 10 is sorted, pivot is sorted. This is the partitioning position, this is the partitioning position.
[9:05]This is how partitioning position works. I have shown you the partitioning procedure which has worked on one list and found out the position of a pivot element. Now break this, perform quick sort recursively, perform quick sort recursively on either side. So that's it, this is the partitioning method, this is followed by quick sort. Let me write down the piece of code on this one. Partition, it takes low and high as parameter. Then what it does, select first element as pivot. So pivot is A of low. Then I was starting from here, J was starting from here. So I will be at low and J will be at high. Then what we did with I, I was incrementing until it finds an element greater than pivot. So it was incrementing if the element is smaller than or equal to pivot.
[10:17]And similarly decrement J until you get an element smaller than or equal to pivot.
[10:35]So I will stop if it is getting any greater element. And J will stop if it is getting any smaller element. So I have written the termination condition here. Then what to do? If I is on this side and J is on that side only, then interchange the elements. If I is less than J, swap A of I with A of J. This is just one comparison. Then again continue I, incrementing I and continue decrementing J and compare them and swap, so this process has to be repeated. So I will write down this whole thing in a loop. How long I should do this? While I is less than J. This I should continue as long as I is less than J. If I became greater than J, it will stop and here it should interchange swap A of low with A of J. So swapping of pivot element should be done with J and return J, that is partitioning position. That's all, this is a partitioning algorithm, how quick sort works. So this is just partitioning. Let us see how quick sort works. Quick sort it will take low and high. If low is less than high, means at least there are two elements. If so, then it will call partition algorithm by passing low and high, and that partitioning algorithm will return J. The position where the partitioning is done. Then it will perform quick sort on left hand side, that is low to J. And it will perform quick sort on right hand side from J plus one to high. That's it. So it will perform this part, perform from low to J. And this perform from J plus one from here to this one, perform quick sort on two. Now one thing I can show you here, this is already sorted. Why do you include J? See right hand side list is having infinity, then where is the infinity for left hand side list? So this sorted element will help as an infinity, act as an infinity for first list. So this is a small piece of recursive quick sort which is using this partitioning. Partitioning was finding the position of pivot by taking I and J.
[13:38]That's all. Watch next video for an analysis of quick sort.
