It is an algorithm of Divide & Conquer type.
Divide: Rearrange the elements and split arrays into two sub-arrays and an element in between search that each element in left sub array is less than or equal to the average element and each element in the right sub- array is larger than the middle element.
Conquer: Recursively, sort two sub arrays.
Combine: Combine the already sorted array.
Partition algorithm rearranges the sub arrays in a place.
Figure: shows the execution trace partition algorithm
Let 44 be the Pivot element and scanning done from right to left
Comparing 44 to the right-side elements, and if right-side elements are smaller than 44, then swap it. As 22 is smaller than 44 so swap them.
22 33 11 55 77 90 40 60 99 44 88
Now comparing 44 to the left side element and the element must be greater than 44 then swap them. As 55 are greater than 44 so swap them.
22 33 11 44 77 90 40 60 99 55 88
Recursively, repeating steps 1 & steps 2 until we get two lists one left from pivot element 44 & one right from pivot element.
22 33 11 40 77 90 44 60 99 55 88
Swap with 77:
22 33 11 40 44 90 77 60 99 55 88
Now, the element on the right side and left side are greater than and smaller than 44 respectively.
Now we get two sorted lists:
And these sublists are sorted under the same process as above done.
These two sorted sublists side by side.
SORTED LISTS
Worst Case Analysis: It is the case when items are already in sorted form and we try to sort them again. This will takes lots of time and space.
T (1) is time taken by pivot element.
T (n-1) is time taken by remaining element except for pivot element.
N: the number of comparisons required to identify the exact position of itself (every element)
If we compare first element pivot with other, then there will be 5 comparisons.
It means there will be n comparisons if there are n items.
T(n)=(n-1) T(1) + T(n-(n-1))+(n-(n-2))+(n-(n-3))+(n-(n-4))+n
T (n) = (n-1) T (1) + T (1) + 2 + 3 + 4+............n
T (n) = (n-1) T (1) +T (1) +2+3+4+...........+n+1-1
[Adding 1 and subtracting 1 for making AP series]
T (n) = (n-1) T (1) +T (1) +1+2+3+4+........ + n-1
T (n) = (n-1) T (1) +T (1) + -1
Stopping Condition: T (1) =0
Because at last there is only one element left and no comparison is required.
T (n) = (n-1) (0) +0+-1
Worst Case Complexity of Quick Sort is T (n) =O (n2)
Generally, we assume the first element of the list as the pivot element. In an average Case, the number of chances to get a pivot element is equal to the number of items.
So in general if we take the Kth element to be the pivot element.
Then,
Pivot element will do n comparison and we are doing average case so,
So Relational Formula for Randomized Quick Sort is:
= n+1 +
(T(0)+T(1)+T(2)+...T(n-1)+T(n-2)+T(n-3)+...T(0))
= n+1 +
x2 (T(0)+T(1)+T(2)+...T(n-2)+T(n-1))
Put n=n-1 in eq 1
From eq1 and eq 2
n T (n) - (n-1) T (n-1)= n(n+1)-n(n-1)+2 (T(0)+T(1)+T(2)+?T(n-2)+T(n-1))-2(T(0)+T(1)+T(2)+...T(n-2))
n T(n)- (n-1) T(n-1)= n[n+1-n+1]+2T(n-1)
n T(n)=[2+(n-1)]T(n-1)+2n
n T(n)= n+1 T(n-1)+2n
Put n=n-1 in eq 3
Put 4 eq in 3 eq
Put n=n-2 in eq 3
Put 6 eq in 5 eq
Put n=n-3 in eq 3
Put 8 eq in 7 eq
From 3eq, 5eq, 7eq, 9 eq we get
From 10 eq
Multiply and divide the last term by 2
Is the average case complexity of quick sort for sorting n elements.
3. Quick Sort [Best Case]: In any sorting, best case is the only case in which we don't make any comparison between elements that is only done when we have only one element to sort.