Data Structures and Algorithms - Old Questions
3. What are external and internal sorting? Explain partition strategies of Merge sort and Quick sort. Trace these sort algorithms for following data:
11 45 61 33 55 9 83 25
Sorting is the technique to arranging the items of list in any specific order which may be ascending or descending order.
Sort can be classified in two types:
1. Internal sort: This method uses only the primary memory during sorting process. All data items are held in main memory and no secondary memory is required in this sorting process. If all the data that is to be sorted can be accommodated at a time in memory is called internal sorting. For e.g. selection sort, insertion sort etc.
Limitation: They can only process relatively small lists due to memory constrains.
2. External sort: Sorting large amount of data requires external or secondary memory. This process uses external memory such as HDD, to store the data which is not fit into the main memory. So primary memory holds the currently being sorted data only. All external sorts are based on process of merging. Different parts of data are sorted separately and merging together. For e.g. merge 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++;
}