2.8.1 QuickSort Algorithm

hi the topic is quicksort first of all let us understand what is the idea behind quicksort 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 asks them to arrange themself 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 quicksort 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 quietly come and stand in the beginning of a list nobody has to help him he can check himself for URL or I am there in the class who is shortest in the class then I can know that my places in the beginning I can simply go and stand in the beginning now if you are the tallest person in the class where a student is tall as he knows that I am the tallest of all he will simply go and stand in 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 tour shorter person should come in front and they will find me place that is the idea of quicksort now I'll write few numbers 10 80 90 60 30 20 which element is obviously sorted in the list this one six three five four two eight nine one nine which are immense seems to be sorted in one glance if you see this element is sorted how we can say that that is largest and it's at the back rest of the numbers don't know whether they are sorted or not but that is sorted sure in the same way if I have the numbers 4 6 7 10 16 12 m 33 sorted and it's a 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 so that is it's sorted position so quicksort works on the idea that an element is in the sorted position if all the elements on the left hand side should be smaller than that element all the elements after that element that is on the right hand side should be greater than that element then that element is in solid position rest of the elements may or may not be sorted so this is the idea of quicksort quicksort works on this one and that's how the name comes quick so like the students can quickly arrange themselves so that's all this is the quick method for sorting but this is not the fastest method of sorting the name is quit now let us look at the procedure of quicksort quicksort is a divide and conquer algorithm it follows divide and conquer strategy so it means it will split the problem into subproblems and solve those subproblems so let us see how it works so I will make initial setup first of all then I will show you the working so the initial setup is this is el lo that is the beginning of a list and this is 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 strengths we have slash 0 null character the string terminator here we have taken infinity to show the end of a list otherwise we should know that there are 9 elements or 10 elements or 20 elements we should work order according to length instead of that we prefer taking end of list marker then first element I will select a spy would so PI mu destined by what is 10 so it means I want to find the sorted position of the certain 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 at this side so for doing so I will take I starting from 5 volt and J starting from infinity I will search for the elements which are greater than 10 that's 5 odd and J will search for the element which are smaller than private so that they can exchange the numbers all right so I at most it will stop at infinity J it will at most stop back by volt maximum if it is not getting anything it will Utley it at most it will stop at by vote now let us see the the procedure what we will do now is called as partitioning procedure first I will perform the procedure diamond line then I will write on the algorithm for partitioning let us start C 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 elements smaller than or equal to pi volt that step is a smaller exchange them 5 comes here 16 goes there one swap continue increment I until you find a pivotal element greater than pootle element 8 is it greater than pi no 12 is it greater than 5 o TS now decrement J until you get an element smaller than pi vote this is smaller interchange them 9 comes here - it goes there continue I this is greater stop decrement J this is smaller stop three this side 15 that side continue is that greater than 10 is it greater than 10 yes I comes here degree Mint J is it smaller than 10 is 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 Pi board what is the position J wherever J is pointing that is the position of Pi board 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 greater than 10 and these are not sorted these are not sorted and even those are not sorted merely have to sort them then who is sorted 10 is sorted by what is sorted this is the partitioning position this is the partitioning position 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 pirate element now break this perform quicksort recursively perform quicksort recursively on either side so that's it this is the partitioning method this is followed by quicksort let me write on the piece of code on this one partition it takes low and high as parameter then what it does select first element as pi would so P would is a of low then I was studying 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 pi mode so it was incrementing if the element is smaller than or equal to the pi what do I plus plus y a of I is less than or equal to PI boat and similarly decrement J until you get an element smaller than or equal to PI would while a of J is greater than PI would 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 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 increment I and continue decrementing J and compare them and swap so this process has to be repeated so I will write on 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 Pi what elements should be done with a chain and a return j that is partitioning position that's all this is a partitioning algorithm ah quicksort works so this is just partitioning let us see how big sort works quicksort 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 lower and high and that questioning algorithm will return J the position where the partitioning is done then it will perform quicksort on left-hand side that is low to J and it will perform quicksort on right hand side from J plus 1 to hi that's it so it will perform this part perform from low to J and this perform from J +1 from here to this one perform quicksort on 2 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 first first list so this is a small piece of recursive quicksort which is using this partitioning partitioning was finding the position of Pi word by taking I and J that's all watch next video for an analysis of quicksort

Channel: Abdul Bari

Views: 2,369,491

Keywords: algorithms, algorithm, Quicksort, qucik sort, quicksort algorithm, abdul bari, bari, gate

Id: 7h1s2SojIRw

Length: 13min 42sec (822 seconds)

Published: Thu Feb 01 2018