Textbook Solutions Expert Q&A home / study / engineering / computer science / co

Question

Textbook Solutions

Expert Q&A

home / study / engineering / computer science / computer science questions and answers / B) B. Merging Two Subarrays Requires An Additional ...

Question: B) b. Merging two subarrays requires an additional...

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.

Show transcribed image tex

Explanation / Answer

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)
{

// Java program program to merge two
// sorted arrays with O(1) extra space.

import java.util.Arrays;

class Test
{
static int arr1[] = new int[]{1, 5, 9, 10, 15, 20};
static int arr2[] = new int[]{2, 3, 8, 13};

static void merge(int m, int n)
{
// Iterate through all elements of ar2[] starting from
// the last element
for (int i=n-1; i>=0; i--)
{
/* Find the smallest element greater than ar2[i]. Move all
elements one position ahead till the smallest greater
element is not found */
int j, last = arr1[m-1];
for (j=m-2; j >= 0 && arr1[j] > arr2[i]; j--)
arr1[j+1] = arr1[j];
  
// If there was a greater element
if (j != m-2 || last > arr2[i])
{
arr1[j+1] = arr2[i];
arr2[i] = last;
}
}
}

// Driver method to test the above function
public static void main(String[] args)
{
merge(arr1.length,arr2.length);
System.out.print("After Merging nFirst Array: ");
System.out.println(Arrays.toString(arr1));
System.out.print("Second Array: ");
System.out.println(Arrays.toString(arr2));
}
}
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);
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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