Data Structures and Algorithms - Old Questions
6. Compare partition strategies of Merge sort and Quick sort.
Quick Sort
In quick sort one of the array element is chosen as a pivot element. Then large array is partitioned into two sub arrays one on left side of pivot which holds values smaller than the pivot element and another array on right side of pivot which holds values greater than pivot the pivot value. This procedure of choosing pivot and partition the list is applied recursively until sub-arrays consisting of only one element.
Algorithm:
QuickSort(A, l, r)
{
if(l<r)
{
p = Partition(A,l,r);
QuickSort(A,l,p-1);
QuickSort(A,p+1,r);
}
}
Partition(A, l, r)
{
x =l; y =r ; p = A[l];
while(x<y)
{
do {
x++;
}while(A[x] <= p);
do {
y--;
} while(A[y] >=p);
if(x<y)
swap(A[x],A[y]);
}
A[l] = A[y];
A[y] = p;
return y; //return position of pivot
}
Merge Sort
The basic concept of merge sort is divides the list into two smaller sub-lists of approximately equal size. Recursively repeat this procedure till only one element is left in the sub-list. After this, various sorted sub-lists are merged to form sorted parent list. This process goes on recursively till the original sorted list arrived.
Algorithm:
MergeSort(A, l, r)
{
If ( l < r)
{
m = (l + r)/2
MergeSort(A, l, m)
MergeSort(A, m + 1, r)
Merge(A, l, m+1, r)
}
}
Merge(A, B, l, m, r)
{
x=l, y=m;
k=l;
while(x<m && y<r)
{
if(A[x] < A[y])
{
B[k]= A[x];
k++;
x++;
}
else
{
B[k] = A[y];
k++;
y++;
}