Program and algorithm for merge sort..
Algorithm.
Algorithm.
The Merge Sort
We now turn our attention to using a divide and conquer strategy as a way to improve the performance of sorting algorithms. The first algorithm we will study is the merge sort. Merge sort is a recursive algorithm that continually splits a list in half. If the list is empty or has one item, it is sorted by definition (the base case). If the list has more than one item, we split the list and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list. Figure 10 shows our familiar example list as it is being split by
mergeSort. Figure 11shows the simple lists, now sorted, as they are merged back together.
Figure 10: Splitting the List in a Merge Sort
Figure 11: Lists as They Are Merged Together
The
mergeSort function shown in ActiveCode 1 begins by asking the base case question. If the length of the list is less than or equal to one, then we already have a sorted list and no more processing is necessary. If, on the other hand, the length is greater than one, then we use the Python slice operation to extract the left and right halves. It is important to note that the list may not have an even number of items. That does not matter, as the lengths will differ by at most one.
Once the
mergeSort function is invoked on the left half and the right half (lines 8–9), it is assumed they are sorted. The rest of the function (lines 11–31) is responsible for merging the two smaller sorted lists into a larger sorted list. Notice that the merge operation places the items back into the original list (alist) one at a time by repeatedly taking the smallest item from the sorted lists.
The
mergeSort function has been augmented with a print statement (line 2) to show the contents of the list being sorted at the start of each invocation. There is also a print statement (line 32) to show the merging process. The transcript shows the result of executing the function on our example list. Note that the list with 44, 55, and 20 will not divide evenly. The first split gives [44] and the second gives [55,20]. It is easy to see how the splitting process eventually yields a list that can be immediately merged with other sorted lists.
Program.
/* MERGE SORT */
# include<stdio.h>
# include<conio.h>
void merge_sort(int *, int , int , int );
void merge_pass(int *, int , int );
void print(int arr[],int size)
{
int i;
for(i=0;i<size;i++)
printf(" %d ",arr[i]);
}
void merge_sort(int l[], int top, int mid, int bottom)
{
int temp[1000],f = top, s = mid +1 ,t = top , upper;
while(( f <= mid)&&(s <=bottom))
{
if(l[f] <= l[s])
{
temp[t] = l[f] ;
f ++;
}
else
{
temp[t] = l[s] ;
s ++;
}
t ++;
}
if(f <=mid)
{
for(f = f ; f<=mid; f++)
{
temp[t] = l[f];
t++;
}
}
else
{ for(s = s ; s<= bottom ; s++)
{
temp[t]=l[s];
t++;
}
}
for(upper = top; upper <= bottom ; upper++)
{
l[upper]=temp[upper];
}
}
void merge_pass( int append[], int m, int n )
{
if( m!= n)
{
int mid = (m+n)/2;
merge_pass( append, m, mid );
merge_pass( append, mid+1, n );
merge_sort( append, m, mid, n );
}
}
void main()
{
int list[20];
int i,size;
clrscr();
printf("how many elements are there in the array");
scanf("%d",&size);
fflush(stdin);
printf("\nenter the elemnts");
for(i=0;i<size;i++)
{
scanf("%d",&list[i]);
fflush(stdin);
}
printf("\nthe elements you entered are");
print(list,size);
i = 0 ;
merge_pass(list, i, size-1);
printf("\n Merge sorted list is as follows:\n");
print(list,size);
getch();
}
0 comments:
Post a Comment