Quick Sort
Quick Sort
Quick Sort is another algorithm which uses the strategy of divide and conquer paradigm, it uses a similar strategy as that of merge sort, which includes division of the list into sub-lists and applying quick sort on them. Additionally Quick Sort is an important algorithm, and in basic sense it selects an element and places it at a place where the elements to the left are less than the selected element and the element to the right are greater than the selected elements.
The worst case time complexity of Quick Sort is O(n^2) while its Average case is Θ(nlogn).
Worst case in Quick Sort occurs when the elements which we are selecting , appears in sorted order dividing the list comparable to insertion sort.
Average case assumes that , the element selected will on an average divide the list in 2 almost equal parts thereby acting comparative to merge sort, thus the complexity nlogn.
fig.1
Fig.1 depicts the basic working of Quick Sort,( Selected Element == Blue ) i.e. The selected element should have all the smaller elements to its right whereas bigger elements should reside to the left of it. Then further Quick sort is applied to the left part of selected element and right part of selected element.
Selected element is also known as pivot element, and we will use the same.
Algorithm For QuickSort
QuickSort(p,q)
{
if(p<q) then
{
j = partition(a,p,q+1);
Quicksort(p,j-1);
Quicksort(j+1,q)
}
}
Partition(a,m,p)
{
v = a[m]; i=m; j=p;
repeat
{
repeat
{
i++;
}until(a[i] >= v);
repeat
{
j++;
}until(a[j] <= v);
if(i<j) then Interchange(a,i,j);
}until(i>=j)
a[m] = a[j];
a[j] = v;
return j;
}
Interchange(a,i,j)
{
p = a[i];
a[i] = a[j]
a[j] = p;
}
Written By
Sarvesh Bhatnagar
