b) b. Merging two subarrays requires an additional temporary array. Although you

Question

b) b. Merging two subarrays requires an additional temporary array. Although you need to use this extra
space, you can save much of the time that our earlier merge algorithm spends in copying entries
from the temporary array back to the original array. If a is the original array and t is the temporary
array, you first merge subarrays of a into the array t. Instead of copying t back to a and continuing
the merge, you determine subarrays of t and merge them into a. If you can do this an even number
of times, no additional copying is necessary. Make these changes to the iterative merge sort that
you wrote in Part a.

this is the code i have can any one edit this am getting errorss:

code:

public class MergeSortB
{
public static<T> <T extends Comparable super T>> void
mergeSortB(T[]a, int n)
{
int i,j;
int firstSubList, secondSubListEnd;

T[] tempArray = (T[])new Comparable[a.length];
boolean copyToTemp = true;
for(i=1; i<a.length; i*=2)
{
for(j=0;j<a.length-1;j+=2*i)
{
firstSubList = j;
int secondSubList = j+i;
secondSubListEnd=j+2*i-1;
if(secondSubListEnd>=a.length)
secondSubListEnd=a.length-1;
merge(a,firstSubList,secondSubList-1,secondSubListEnd,tempArray,copyToTemp);
}
copyToTemp=!copyToTemp;
}
if(!copyToTemp)
for(i=0;i<a.length;i++)
a[i]=tempArray[i];
}
private static<T> <T extends Comparable super T>> void
merge(T[]a, int first, int mid,int last, T[]tempArray, boolean copy ToTemp )
{
if(copyToTemp)
merge(a, first,mid,last, tempArray);
else
merge(tempArray,first,mid,last,a);
}
private static<T extends Comparable super T>> void
void merge(T[]a, int first, int mid,int last, T[]tempArray)
{
int startingHalf1=first;
int endingHalf1=mid;
int startinghalf2=mid+1;
int endingHalf2=last;
int index=first;
while((startingHalf1<=endingHalf1)&&(startinghalf2<=endingHalf2))

{

if(a[startingHalf1].Comparable To(a[startinghalf2])<0))
{
tempArray[index]=a[startinghalf1];
startingHalf1++;
}
else
{
tempArray[index]=a[startinghalf2];
startingHalf2++;
}
index++;
while(startingHalf1<=endingHalf1)
{
tempArray[index]=a[startinghalf1];
index++;
startingHalf1++;
}
while(startingHalf2<=endingHalf2)
{
tempArray[index]=a[startinghalf2];
index++;
startingHalf2++;
}
}
public static void main(String[] args)
{
Integer[]a={25,55,15,20,40,10,5,35,30,29,88,45,50};
System.out.println("The array before sorting is ");
for(int i = 0; i<a.length;i++)
System.out.print(a[i]+"");
System.out.print(false);
mergeSortB(a,a.length);
System.out.println(" The array after sorting is ");
for(int i=0;i<a.length;i++)
System.out.print(a[i]+"");
System.out.print(false);
}
}

for more details

THe question is :

a. If n is a power of 2, as it is in Figure 9-3, you would merge pairs of individual entries, starting at the
beginning of the array. Then you would return to the beginning of the array and merge pairs of twoentry
subarrays. Finally, you would merge one pair of four-entry subarrays. Notice that the subarrays
in each pair of subarrays contain the same number of entries.
In general, n might not be a power of 2. After merging a certain number of pairs of subarrays, you
might have too few entries left to make up a complete pair of subarrays. In Figure 9-13a, after merging
pairs of single entries, one entry is left over. You then merge one pair of two-entry subarrays, and merge
the leftover two-entry subarray with the leftover single entry. Parts b and c of Figure 9-13 show two
other possibilities.
Implement an iterative merge sort. Use the algorithm merge that was given in Segment 9.3. A private
method that uses merge to merge the pairs of subarrays is useful. After the method completes its task, you
can handle the leftovers that we just described.
b. Merging two subarrays requires an additional temporary array. Although you need to use this extra
space, you can save much of the time that our earlier merge algorithm spends in copying entries
from the temporary array back to the original array. If a is the original array and t is the temporary
array, you first merge subarrays of a into the array t. Instead of copying t back to a and continuing
the merge, you determine subarrays of t and merge them into a. If you can do this an even number
of times, no additional copying is necessary. Make these changes to the iterative merge sort that
you wrote in Part a.

Iterative merge sort

9.8) Once we have the merge algorithm, developing the recursive merge sort is easy. Developing an iterative
merge sort is not as simple. We begin by making some observations about the recursive solution.
The recursive calls simply divide the array into n one-entry subarrays, as you can see in
Figure 9-3. Although we do not need recursion to isolate the entries in an array, the recursion controls
the merging process. To replace the recursion with iteration, we will need to control the
merges. Such an algorithm will be more efficient of both time and space than the recursive algorithm,
since it will eliminate the recursive calls and, therefore, the stack of activation records. But
an iterative merge sort will be trickier to code without error.
Basically, an iterative merge sort starts at the beginning of the array and merges pairs of individual
entries to form two-entry subarrays. Then it returns to the beginning of the array and merges
pairs of the two-entry subarrays to form four-entry subarrays, and so on. However, after merging all
pairs of subarrays of a particular length, we might have entries left over. Merging these requires
some care. Project 2 at the end of this chapter asks you to develop an iterative merge sort. You will
see there that you can save much of the time necessary to copy the temporary array back to the original
array during the merges.

FIGURE 9-3 The effect of the recursive calls and the merges during a merge sort Effect of 12 16 calls to mergeSort 13 18 19 Merge steps 21 Copy to original array Numbers on the arrows in the figure indicate the order in which the recursive calls and the merges occur. Notice that the first merge occurs after four recursive calls to mergeSort and before other recursive calls to mergeSort. Thus, the recursive calls to mergeSort are interwoven with calls to merge. The actual sorting takes place during the merge steps and not during the recursive calls

Explanation / Answer

#include <stdio.h>

void mergeSort(int [], int, int, int);
void parts(int [],int, int);

int main()
{
int first[50];
int uu, size;

printf("Enter the total number of elements:");
scanf("%d", &size);
printf("Enter each elements: ");
for(uu = 0; uu<size; uu++)
{
scanf("%d", &first[uu]);
}
parts(first, 0, size-1);
printf("Elements after merge sort: ");
for(uu=0;uu<size; uu++)
{
printf("%d ",first[uu]);
}
return 0;
}

void parts(int first[],int lower,int high)
{
int mid;
if(lower < high)
{
mid=(lower + high)/2;
parts(first, lower, mid);
parts(first, mid+1, high);
mergeSort(first, lower, mid, high);
}
}

void mergeSort(int first[],int lower,int mid,int high)
{
int uu, io, qu, lo, temp[50];

lo = lo;
uu = lo;
io = mid + 1;
while ((lo <= mid) && (io <= high))
{
if (first[lo] <= first[io])
{
temp[uu] = first[lo];
lo++;
}
else
{
temp[uu] = first[io];
io++;
}
uu++;
}
if (lo > mid)
{
for (qu = io; qu <= high; qu++)
{
temp[uu] = first[qu];
uu++;
}
}
else
{
for (qu = lo; qu <= mid; qu++)
{
temp[uu] = first[qu];
uu++;
}
}

for (qu = lo; qu <= high; qu++)
{
first[qu] = temp[qu];
}
}

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.