QUICK SORT ALGORITHM
QUICK SORT ALGORITHM
1.) It is a Comparison based Sorting Algorithm.
QUICK SORT ALGORITHM
1.) It is a Comparison based Sorting Algorithm.
2.) It is one of the efficient and practical problem solving algorithm.
QUICK SORT ALGORITHM
1.) It is a Comparison based Sorting Algorithm.
2.) It is one of the efficient and practical problem solving algorithm.
3.) It works on Divide and Conquer technique.
QUICK SORT ALGORITHM
1.) It is a Comparison based Sorting Algorithm.
2.) It is one of the efficient and practical problem solving algorithm.
3.) It works on Divide and Conquer technique.
4.) It is not stable. (Unstable)
QUICK SORT ALGORITHM
1.) It is a Comparison based Sorting Algorithm.
2.) It is one of the efficient and practical problem solving algorithm.
3.) It works on Divide and Conquer technique.
4.) It is not stable. (Unstable)
5.) It is Inplace.
PARTITION ALGORITHM
Partition algorithm is the heart of quick sort.
algorithm.
Select an array element as pivot.
put pivot element in the correct order of sorted array, such that the elements smaller than
pivot element will on the LHS of the pivot element (i.e. before the pivot element) and the
elements larger than the pivot element will be on RHS of the pivot element
(i.e. after the pivot element.)
QUICK SORT ALGORITHM
PIVOT SELECTION: There are many ways to select pivot element. According to the selection of pivot
element, the time complexity of the algorithm will vary.
1. Pick first element as pivot.
2. Pick last element as pivot.
3. Pick median element as pivot.
4. Pick any random number as pivot.
5. Pick middle element as pivot.
6. Pick (n/10th) element as pivot.
QUICK SORT ALGORITHM
Take first element as pivot:
5 6 4 2581 3
QUICK SORT ALGORITHM
5 6 4 2581 3
1. take first element as pivot.
2. take i=p=starting index.
3. take second index as j.
4. now compare arr[j] with pivot element, if it is smaller than or equal to pivot element,
increament i and swap arr[i] and arr[j].
5. increament j.
follow step 4 and step 5 untill j reaches the last element.
at the end swap arr[i] and arr[p]
pseudo code:
Partition(arr[], p, q)
{
pivot =arr[p];
i=p;
for(j=p+1; j<=q;j++)
{ if(arr[j]<= pivot)
{
i++;
swap(arr[i],arr[j]);
}
}
swap (arr[i],arr[p])
return(i);
}
2. Take last element as pivot:
5 6 4 2581 3
1. take last element as pivot.
2. take i=j=starting index.
3. now compare arr[j] with pivot element, if it is smaller than or equal to
pivot element,
swap arr[i] and arr[j] and increament i.
4. increament j.
follow step 3 and step 4 untill j reaches the second last element.
at the end swap arr[i] and arr[p]
Partition(arr[], p, q)
{
i=j=p;
pivot =arr[q];
for(j=0; j<=q-1;j++)
{ if(arr[j]<= pivot)
{
swap(arr[i],arr[j]);
i++;
}
}
swap (arr[i],arr[q])
return(i);
}
Quicksort(arr[],p,q)
{ if(p==q)
return(arr[p])
else
{
K=partition(arr[],p,q);
Quicksort(arr[],p,k-1);
Quicksort(arr[],k+1,q);
return(arr[]);
}
}
RECURENCE RELATION AND TIME COMPLEXITY
T(n) = T(k-p) + T(q-k) + O(n) + Pivot Selection time
Best Case
WORST CASE