RashmiDSA blog

Quick Sort

AKU 2019 DSA Quick Sort

Sort the given values using quicksort and write time complexity of algorithm :

65, 70, 75, 80, 85, 60, 55, 50, 45

Sol:

Quick sort algorithm is sorting Algorithm based on Partition technique. In this algorithm first we select pivot element. This pivot element can be any one.

Now we have to take two pointer one is i at left side to the given list another one is j at right side to the given list.

If pivot item pointed by i is smaller than pivot element then increment i by 1

and if item pointed by j is greater than pivot element then decrement j by 1

If above both condition is not true or can say false then simply swap element pointed by i and j

Second case may happen when j cross i if yes then simply interchange pivot element by element pointed by j

This is the working principal of Quick Sort. Outcome of this process is element to the left will always be smaller than pivot and in right all element will be bigger than pivot element that means now pivot element is in appropriate place in the given list.

Lets suppose we are taking first element as pivot element in given list and it is represented by P.

So P= 65

Here item pointed by i (70) is greater than pivot element (65) so increment of i not allowed here i will stop here. Similarly item pointed by j (45) is smaller than Pivot (65) so decrement of j is not allowed so j will stay at the same position. Now, both element pointed by i(70) and j(45) will be interchanged with each other as below

Now, both element pointed by i(70) and j(45) will be interchanged with each other as below:

After swapping element pointed by i ang j, i will increment by 1 and j will decrement by j as below fig.

Here, again item pointed by i(75) is greater than pivot element(65) and item pointed by j(50) is smaller than pivot element(65).So swap operation performed between element pointed by i(75) and element pointed by j(50) as below:

Now, increment the i by one and decrement j by 1 as below:

Here again item pointed by i (80) is greater than pivot element(65) and item pointed by j(55) is smaller than pivot element(65). So swap operation performed between element pointed by i(80) and element pointed j(55) as below.

At the same time i will increment by one and j will be decrement by 1 as below:

Here again item pointed by i(85) is greater than pivot element(65) and item pointed by j(85) is smaller than pivot element (65). So apply swap operation between element pointed i and element pointed by j as below:

At the same time i incremented by one and j decremented by 1 as below:

Now this is the point where j crossed over i. So, here we will interchange element pointed by j with element pointed by pivot element as below

Here pivot element is placed at appropriate place in this list where all element to the left is smaller than the pivot element and right to pivot all elements are bigger than pivot element.

So finally list is divided into two half's one is left subpart to pivot element and other is right sub part to pivot element. Pass 1 is over now.

Repeat same procedure as pass 1 on left subpart as below:

Since item pointed by i (45) is smaller than pivot item(60). So, simply i incremented by one as below:

Again item pointed by i (50) is smaller than pivot item(60). So, simply i incremented by one as below:

Even now item pointed by i(55) is smaller than pivot item(60). So, simply i incremented by one as below:

At this point i is pointed garbage value and simultaneously j comes before i so performed swap operation between element pointed by j(55) and pivot element (60) as below. Finally pivot element 60 got appropriate place in list.