QUICK SORT WITH EXAMPLE

[Music] hello friends welcome back to our channel so in the in the previous session we have covered the applications of a stack and then we have seen a few sorting techniques so in that we have covered the bubble sort insertion sort selection sort merge sort and heap sort and today's session will go with the another sorting mechanism that is called a quick sort so this sorting mechanism will follow the divide and conquer method divided conquer so the name itself indicates so divide and conquer means first the complex problem is divided into subproblems and EH is a problem will be implemented so like like that here also the complete large elements will be divided into different partitions and each partition will be applied for sorting so each partition will be implemented by using the recursive methods okay next so let us see the procedure first and then we'll go with the example then first step here we have to first we have to select the pivot and we have to find the position of the pivot element so here we will go with the pivot element right so first we have to find the position of AP would position of the free P would such that all the elements would share a left towards this pivot are less than the pivot element and whatever the elements which are on the right side to this position are greater than appear would right so this position first we have to find this position then consider this as a word partition consider this as another partition so see this is less than P Walter this is a greater than you know guitar okay this is a less than symbol and a greater than symbol okay so less than P what is more partition greater than P what is an angle partition so recursively call the same procedure for this partition again consider the pivot and find the position of the pivot for this partition and again divide that into two positions right so like like this we have to find this quicksort first this pivot can be considered as the element the pivot element can be considered as first statement middle element the last n right so we can consider any element as the pivot element and based upon the pivot element we have to find the position of that particle pivot element for example if if the numbers are 50 40 10 30 and 40 this element can be considered as a P word or this element can be considered as a people or this element can be considered as a people so after considering the element a zippy would we have to find the position of that particular pivot point such that all the elements which are less than P word should be all the right dancing and all the elements which are greater than the P word should be arranged on right hand side so in such a way we have to find the position of the people first we have to consider the pivot element what is the pivot element right so in our example we will consider this one first one so let us consider the first element has a P word and find the pivot position see faster considered first element as if he would consider the first element as a people next initialize I to low index J to high index that was the starting element J is a last element next we have to repeat the power procedure repeat the following steps and the I less than J so until I becomes until I less than J until the condition is true we have to repeat the following procedure so first keep on incrementing I keep on incrementing I why yep I is less than or equal to people unless unless this condition becomes false we have to keep on incrementing the high value okay next similarly keep on decrement in the J why yeah J is greater than people so similarly from the starting we have to incrementing the I towards the right and we have to decrement in the J towards the left okay so while incrementing and decrementing I and J values we have to check these conditions whether I of delay of AI is less than or equal to P work and whether the a of J is greater than devote right next so if this two condition fails if these two at some condition this condition I mean at some point this condition will be failed so we have to stop incrementing the I at some statement element this condition will be false so we have to stopped incrementing the team now check the condition if I is less than J I is less than J yes then if it is true then swap the elements yeah of I come on yeah of J yeah I come on I object so we have to swap the elements of a I value the elements which are available in I think X and J index next next if this becomes false if this becomes false I less than J so if I is greater than J the index value of I is greater than J then there also we have to swear swear yeah J element with the people you have J element with the P word so that so this is nothing but I mean okay this is nothing but the airflow you have flow because here I the pivot is the first element right free wood is the first element P what is the first element so we have to change this where' between the jet element and paper value so here J is the position of people this is right J is the position of a people so then all the elements which are less than P would are on the right hand side L for left hand side and all the elements which are greater than the pivot will be on right hand side so here after completion of this one the pivot value will be fixed the pivot position is fixed right now that people value P what position will be fixed right so we have supposed to find that position effective or now divide the two partitions so what is something after getting the P word after getting the people value right so this is one partition and this is another partition so this is 0 to P minus 1 and here P to high P plus 1 Rho I plus 1 low to P minus 1 so this is one partition this is another partition so consider this partition and here also consider repeat the same process so recursively the cubed same process cuz at this partition and same area filaments now consider the Peapod first element as a keyboard and starting high to low index and J to high index so I will be no J will be P minus 1 and then repeat the following steps until I is the is than J so keep on incrementing I while I a of I is less than or equal to few would and then keep on decrementing the J where my a FJ is greater than pure right then if I is less than J the index values of I is less than J then simply swap the positions of a int the elements which are read positions of by the engine then if I is greater than J the index value of y is greater than the input value of J then simply strap the a low value with the a of J that means of the value present at the position J so here you have low means nothing but at Peapod value because in the first system we are considering the first element as a keyword so here again the pivot where the P the position J is a position of MU or some position when the pivot position is fixed so that all the elements of which are less than P what will be on the left hand side and all the elements which are then promote are available in the right hand side and again do the partitions and again right we do the same process right so this is how we will implement we are going to implement this quick set right so based upon this algorithm let us solve an example so that your doubts will be clarified so our aim is to find the position of eight people and we will implement the same thing recursively for all the partitions so once the pivot is fixed then we have to divide it into partitions and considering each partition and B how to repeat the same okay example example let us take some elements trusted resentments okay see so these are the elements of an ally so this is arrangements these are the in exists this is the Y value this is the T value I value T value okay right then consider this as it people to consider this element I think people know now I repeat the process so first two first step I said the pivot as a first element so we have considered this one and next one is image laser to do and J is initially is too high so I less than J I less than J that is here 0 less then funny the condition is to so this condition is true we have to repeat the process so what we have to repeat we have to keep on incrementing int I is less than or equal to t mode so yeah I less than or equal to P would see this condition I request must we have to repeat the same process okay so here see faster 30 less than or equal to 30 so I plus 2 s so that means that it that means 1 it will be next 20 as them are equal to 30 I plus plus 2 right next 10 less than or equal to 30 I plus plus 3 index value 3 so 50 less than or equal to 30 so things okay Phil here the condition fields now here edward condition it is free i is equal to three so i is equal to 3ei by condition I is equal to three phase so after completion of this one is pointing and here now keep on decrement in the J value so yeah of J is greater than people would if I J - - so repeat this process so if j j is nothing but a high value look hey when you fight so for T for T greater than or equal to greater than 30 J - - so it will be for next 60 greater than 30 J - - the second 4 so 3 after decrementing it will be 3 next 50 greater than 30 again J - - - next M greater than 30 phase so at where it fails J is equal to 2 right so at some condition if some element both the condition will be things now we have to check whether I is less than J so what is the C if I less than J then swear yeah fil Madrid yeah German right yes we have to change swear yeah of J limit with people right now let us take the condition here so I less than J so 3 D less than 2 I less than J 3 less than 2 which is false right so we have to swear yes Jay yep Germans today is to be able to come on pivot where the people 30 are AOL flow yeah 0 because up here the P what is he up to go right so sappy J position is he would so what is the deposition to second position is that P rooted second position is the pivot element for the first thing so after getting this world see just swap the positions you have to comma F 0 we have to move 10 so 10 will be here 23 then 50 60 and 40 you know 1 2 3 and 5 so second position is a pivot second position is that pin would right so here if you observe all the elements which are on the left-hand side of the pivot are less than these people 10 and 20 so it may be in a sorted order it may it may not be in a sorted order right so what are the elements which are on the right hand side of the keyboard are greater than the fuel elements right so this is may be in a sorted order and these may not be in a sorted order so this is the partition one this is the partition to right so now we have to consider so this position is fixed right the word position is fixed so we have to take it about the partition 100 partition 2 excluding this pure position so that is why we are writing from 0 to 200 to p minus 1 and here P plus 1 2 so we have not considering them favored position because it is already fixed so hope you understood this one so after the first iteration first recursion this is the element now let us write these elements okay I will write down here so 10 20 30 50 60 and 40 right so I will erase all these things so first vacation this is about the first paper so this is the pivot element okay fixed so this will be the partition one and this will be the partition right so let us consider these partitions so 10 and 2008 in its first index so obviously this will be a this will be J and also TiVoed we know that we are considering the pivot as a first element so this one so mark you have to check with how to repeat until I is less than G here it is 0 less than 1 condition true then keep on incrementing so a of I is less than or equal to P volt I plus plus so for this we have to go with this so 10 less than or equal to 10 I press press that means that will be 1 and a 20 less than or equal to 10 okay so false so I is equal to 1 or third alright is equal to 1 so I value is changing from here to here ok next yes J greater than P mode we have to keep on documenting the gene value we have you would have to keep on determining the different so 20 is greater than or equal to the point is greater than 10 J - - right J - - and the value will be 0 because initial J is equal to 1 and M is greater than 20 which is a false so J is equal to 0 C and I is equal to 1 condition fails and J is equal to 0 prediction fix here if you observe I is less than J then what you have to do slab a of I comma J of J yes sorry we can write the condition okay I greater than J then swear here of J comma P both people right so here we can observe here at which crew headway at what positions the condition phase I is equal to 1 and J is equal to 0 so 1 less than 0 the condition is false so this will be happened so swear yeah of Janus 0 come on people here pivot means again here so that implies that implies so both the J position both the J value and a purity are in the same position so we we need not swap right so already those are in sorted order that means these are in a sorted order because we need not swap an ailment okay will two elements are dead we need not swap any remain so this will be the preferred position okay so here see jail position is a pre-war position is it it right what is the deposition zero so zero disappeared position see if zero is a pure position see ya left hand say we are not having any element so right answer we are having only one element which is also greater than 10 so the eating place this partition is already in sorted order right next hope you understood next we will go you the partition to you go with the partition do so this is already in sorted order no we're every the same process with the partition to so 50 60 and 40 so 0 1 & 2 so this is the I value this is the Jaylin okay this is the I value this is a J value and this is the future right so continue the process so I less than J that is 0 less than 2 so this condition true then ya of I less than or equal to P would I plus place so keep on doing all these things so yeah I that means are 50 less than or equal to 50 I plus plus that means I becomes one initial is you next 16 less than or equal to 50 faith and I is equal to 1 and I is equal to 1 it fails so now I becomes here then similarly a of J is a greater than P walk j- - so repeat this process so general is a for T for T greater than 50 for T greater than 50 condition false so J is equal to zero pollution and J is equal to 2 and J is equal to 2 the condition fails okay then see if you observe here check the condition I greater the energy here is 1 greater than 2 I greater than G it is a punch so swear so sorry sorry I less than J so if I is less than J we have to slap the University f ing of J if I is greater than J then we have to swap the elements of J and pivot so here the first condition is less than J I value is 1 J value is 2 so I is less than J so swear yeah of I come on here G so what are the elements we have to sell swear the 60 and 40 so the elements will be after the iteration the elements will be 50 40 60 50 40 60 the positions of fire then J are same okay so the index values 0 1 and 2 and this is the people we are considering right so after swapping 6 J according we will get this one okay now again you repeat the same process so yeah I is less than or equal to P vote so I plus plus answer this one here Phi that means R for T less than or equal to 50 I plus plus which becomes 2 similarly 6 has ever reported 50 fail and is equal to rank and I is equal to Tony face now I and J are positioning at the same point I am jab positioning at the same point similarly a of J is greater than P board then simply determine the J repeat the process so 60 greater than or equal to 50 not equal greater than 50 J - - which becomes 1 similarly for T greater than 50 which fails at position J is equal to 1 now J is positional one right now check the condition so if I is less than J then swear here of I come on any of j-just a minute yes swear EF j come on P good right now here I list - James 1:2 less than 1 false so we have to slap false condition slap here of jade come on P wood which is the template yeah Sam yep J means you have 140 come on you have P would 50 and we know that J is P word J is people that means 1 1 is P would here ok so here 1 is pure so after completion of this okay after completion of this so I will erase this one right so here that Jay is a people Jay is peeled here what is the value of jail one-for-one is a pivot position one his pivot position so we have to serve after slapping after swapping for a comma 50 the elements are 40 50 and 60 the positions 0 1 2 the position this is the favored position so left hand side of the pivot is having the values of less than people and the right side of the pivot position are having the elements greater than people so here again this is the one partition this is the another partition so here the partition is having only one value so need not apply the sorting damage and here also the partition is having only one value here also we need not apply the sorting techniques so finally after completion of all these things we can simply have 40 50 and 60 okay so this is a procedure we are supposed to apply so hope you understood this one right after the first iteration too easy we would so that two partitions are there first partition again 0 is the P word second partition 1 is a pyramid 1 means the position 1 index 1 ok index 0 and index 1 right so hope you understood this one the quicksort algorithm how it applied for this how we are dividing the complete elements into different part and the hope we are applying the recursive functions right so simple thing so faster we have to consider the pivot element and first to find out the position of that particular pivot element and then based upon that particular pivot element we have to divide it to the partitions and recursively apply the same procedure so let us stop here so if you are having any doubts regarding this a quicksort feel free to post your doubts in the comment section so that I will definitely try to clarify all your notes and if you really understood my sessions like my sessions share my sessions with your friends and don't forget to subscribe to our channel thanks for watching thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 75,590

Keywords: sundeep, saradhi, kanthety, c language, c programming, cp, computer, computer programming, loops, c programming trainee, c language training, sort, bubble sort, swaping, interchange of elements, nested loops, iterative statements., array applications, single dimensional array, array example, ascending order, descending order, pivot, partition, recursive sort, quick sort, divide and conquer, swapping

Id: 4uJHGIFQ72M

Length: 33min 40sec (2020 seconds)

Published: Tue Jul 02 2019