Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

1. ## Sorting and Merging

```Out: 30th November 2010 Type: Medium Due: 8th December 2010 at 11:59pm
Note: You can use Eclipse for this assignment if you wish.
In class we discussed different algorithms to sort an array in ascending order. This assignment explores a useful operation that you can perform on sorted arrays: merging them so that the merged array is also sorted.
Given two arrays A and B of different lengths that are already sorted in ascending order, one can merge them into an array C as follows:
1. Maintain current positions for arrays A and B.
2. If number at current position in A is greater than that in B, add As current number to C and advance As position. Otherwise add Bs current number to C and advance Bs position.
3. Continue step 2 until you reach the end of one of the two arrays. When you do, copy the remaining elements of the other array to the end of C.
What to do:
1. Write a class Merge. It will have no variables.
2. Write a static method merge in Merge that takes two arrays as parameters and returns the merged array using the above algorithm. Make sure your method works even if there are common numbers in the two arrays, and if one or both arrays have just one number in them. You will not receive any points if you use any other method, including putting numbers in another array and then sorting it.
3. Write another static method inplace_merge in Merge. This method takes a single array A as a parameter, along with three indices left, middle and right. Assuming all three are valid indices, this method assumes that the array A is sorted between (left, middle) and (middle+1, right), including the ends. It then merges these two sub-arrays and copies the result back to A between left and right. You may use the above method to accomplish this if you wish.
4. You have almost implemented a popular algorithm to sort an array, mergesort. The pseudocode for mergesort is as follows: mergesort(A,left,right) { if (left >=right) return Compute middle  floor((left+right)/2) Call mergesort recursively as mergesort(A,left,middle) Call mergesort recursively as mergesort(A,middle+1,right) Merge the two sorted arrays A(left,middle) and A(middle+1,right) in place using inplace_merge above. // Now the array A is sorted correctly from index left to index right. }
Write the above method in the Merge class. Write another method sort(A) that calls the mergesort method so that the array A is sorted.
5. The main method of your program should ask the user for the following input from the keyboard in the given order:
a. Number of elements in 1st array.
b. Numbers of 1st array.
c. Number of elements in 2nd array.
d. Numbers of 2nd array.
It should then print (1) both arrays as entered by the user (2) sorted arrays using the mergesort algorithm (3) the array obtained by merging the two arrays.
Hint: To verify that your merge works correctly, you can use the code from class that sorts arrays using selection, bubble or insertion sort. But make sure that the program you submit uses mergesort to sort the two arrays entered by the user.```

Am currently starting to code it now.  Reply With Quote

3. ## Re: Sorting and Merging

Oh, I should add that I don't have to worry about the user not entering them in sorted order, as I'm the only user. This whole thing is assuming that the arrays are already sorted and is only intended to work in such a case.  Reply With Quote

4. ## Re: Sorting and Merging

Where is everyone?  Reply With Quote

5. ## Re: Sorting and Merging

You've provided us with your assignment lol, What do you want us to do? We can't help until you give us some code to help on hehe.

Chris  Reply With Quote

6. ## The Following User Says Thank You to Freaky Chris For This Useful Post:

javapenguin (December 2nd, 2010)

7. ## Re: Sorting and Merging

```public class Merge
{

public Merge()
{

}

public static  int[] merge (int[] A, int[] B)
{
int curr = 0; // current position of first array
int curr2 = 0; // current position of second array

int x = A.length + B.length;
int y = 0; // index of C

int[] C = new int[x];

while ((curr < A.length) && (curr2 < B.length))
{
if A[curr].compareTo(B[curr2] > 0)
{
C[y] = A[curr];
y++;
curr++

}

else
{
C[y] = B[curr2];
y++;
curr2++;

}
}
if (curr == A.length)
{
for (int k = curr2; k < B.length; k++)
{
C[k + curr] = B[curr2];
curr2++;
}

}

else
{
for (int v = curr; v < A.length; v++)
{
C[v + curr2] = A[curr];
curr++;
}

}

return C;

}

}```

Will that always work?  Reply With Quote

8. ## Re: Sorting and Merging

Can you tone down that obnoxious signature?  Reply With Quote

9. ## Re: Sorting and Merging

Obnoxious?  Reply With Quote

10. ## Re: Sorting and Merging

Its incredibly long, and includes such gems as

Also, you can create your own javadoc, though I'm not sure how to get that part to work at this point.
Why would that need to be in every post?  Reply With Quote

11. ## The Following User Says Thank You to DavidFongs For This Useful Post:

javapenguin (December 2nd, 2010)

12. ## Re: Sorting and Merging

Also, I'm wondering, is my spam stopping organization getting on people's nerves? I mean, people other than the evil spammers of course.  Reply With Quote

13. ## Re: Sorting and Merging

Found 2 more.

Chimeric and LOThoams  Reply With Quote

14. ## Re: Sorting and Merging

This is not the place to discuss Spammers.

You code seems to be ok, I cannot see any serious floors at a quick glance.

Chrsis  Reply With Quote

15. ## The Following User Says Thank You to Freaky Chris For This Useful Post:

javapenguin (December 3rd, 2010)

16. ## Re: Sorting and Merging

```public class Merge
{

public Merge()
{

}

public int[] merge (int[] A, int[] B)
{
int curr = 0; // current position of first array
int curr2 = 0; // current position of second array

int x = A.length + B.length;
int y = 0; // index of C
String str = "";
int[] C = new int[x];

while ((curr < A.length) && (curr2 < B.length))
{
if A[curr].compareTo(B[curr2] > 0)
{
C[y] = A[curr];
y++;
curr++

}

else
{
C[y] = B[curr2];
y++;
curr2++;

}
}
if (curr == A.length)
{
for (int k = curr2; k < B.length; k++)
{
C[k + curr] = B[curr2];
curr2++;
}

}

else
{
for (int v = curr; v < A.length; v++)
{
C[v + curr2] = A[curr];
curr++;
}

}

return C;

}

public static void implace_merge(int[] A, int left, int middle, int right)
{

int[] sub = new int[(middle-left) + 1];

for (int x = 0; x < sub.length; x++)
{
sub[x] = A[x];
}

int[] sub2 = new int[right - (middle+1)];

for (int y = middle + 1; y < sub2.length; y++)
{
sub2[y] = A[y];
}

int[] result = merge(sub, sub2);

}

}```  Reply With Quote

17. ## Re: Sorting and Merging

Well, we can always try tomorrow.  Reply With Quote

18. ## Re: Sorting and Merging

`if A[curr].compareTo(B[curr2] > 0)`
I think you started getting mixed up a bit here (lack of sleep perhaps?).  Reply With Quote

19. ## The Following User Says Thank You to helloworld922 For This Useful Post:

javapenguin (December 3rd, 2010)

20. ## Re: Sorting and Merging

Yeah. I had not that much yesterday. I'm better now.  Reply With Quote

21. ## Re: Sorting and Merging

```public class Merge
{

public Merge()
{

}

public int[] merge (int[] A, int[] B)
{
int curr = 0; // current position of first array
int curr2 = 0; // current position of second array

int x = A.length + B.length;
int y = 0; // index of C
String str = "";
int[] C = new int[x];

while ((curr < A.length) && (curr2 < B.length))
{
if A[curr].compareTo(B[curr2] )> 0)
{
C[y] = A[curr];
y++;
curr++

}

else
{
C[y] = B[curr2];
y++;
curr2++;

}
}
if (curr == A.length)
{
for (int k = curr2; k < B.length; k++)
{
C[k + curr] = B[curr2];
curr2++;
}

}

else
{
for (int v = curr; v < A.length; v++)
{
C[v + curr2] = A[curr];
curr++;
}

}

return C;

}

public static void inplace_merge(int[] A, int left, int middle, int right)
{

int[] sub = new int[(middle-left) + 1];

for (int x = 0; x < sub.length; x++)
{
sub[x] = A[x];
}

int[] sub2 = new int[right - (middle+1)];

for (int y = middle + 1; y < sub2.length; y++)
{
sub2[y] = A[y];
}

int[] result = merge(sub, sub2);
int index = 0;
for (int z = left; z <=right; z++)
{
A[z] = result[index];
index++;
}

}

public static void mergesort(int[] A, int left, int right)
{
if (left>=right)
return;

int middle = (left + right) /2;

mergesort(A, left, middle);
mergesort(A, middle+1, right);

inplace_merge(A, left, middle, right);

}

public static void main(String[] args)
{
Scanner console = new Scanner(System.in);

System.out.println("Enter the number of elements in the first array.");

int x = console.nextInt();

int[] array = new int[x];

for (int i =0; i < array.size; i++)
{
System.out.println("Enter the value at index " + i);
array[i] = console.nextInt();
}

System.out.println("Enter the number of elements in the second array.");

int y = console.nextInt();

int[] array2 = new int[y];

for (int j =0; j < array2.length; j++)
{
System.out.println("Enter the value at index " + j);
array2[j] = console.nextInt();
}

System.out.println("Array 1: " + Arrays.toString(array) + " Array 2: " + Arrays.toString(array2));

}

}```

Out: 30th November 2010 Type: Medium Due: 8th December 2010 at 11:59pm
Note: You can use Eclipse for this assignment if you wish.
In class we discussed different algorithms to sort an array in ascending order. This assignment explores a useful operation that you can perform on sorted arrays: merging them so that the merged array is also sorted.
Given two arrays A and B of different lengths that are already sorted in ascending order, one can merge them into an array C as follows:
1. Maintain current positions for arrays A and B.
2. If number at current position in A is greater than that in B, add A’s current number to C and advance A’s position. Otherwise add B’s current number to C and advance B’s position.
3. Continue step 2 until you reach the end of one of the two arrays. When you do, copy the remaining elements of the other array to the end of C.
What to do:
1. Write a class Merge. It will have no variables.
2. Write a static method merge in Merge that takes two arrays as parameters and returns the merged array using the above algorithm. Make sure your method works even if there are common numbers in the two arrays, and if one or both arrays have just one number in them. You will not receive any points if you use any other method, including putting numbers in another array and then sorting it.
3. Write another static method inplace_merge in Merge. This method takes a single array A as a parameter, along with three indices left, middle and right. Assuming all three are valid indices, this method assumes that the array A is sorted between (left, middle) and (middle+1, right), including the ends. It then merges these two sub-arrays and copies the result back to A between left and right. You may use the above method to accomplish this if you wish.
4. You have almost implemented a popular algorithm to sort an array, mergesort. The pseudocode for mergesort is as follows: mergesort(A,left,right) { if (left >=right) return Compute middle  floor((left+right)/2) Call mergesort recursively as mergesort(A,left,middle) Call mergesort recursively as mergesort(A,middle+1,right) Merge the two sorted arrays A(left,middle) and A(middle+1,right) in place using inplace_merge above. // Now the array A is sorted correctly from index ‘left’ to index ‘right’. }
Write the above method in the Merge class. Write another method sort(A) that calls the mergesort method so that the array A is sorted.
5. The main method of your program should ask the user for the following input from the keyboard in the given order:
a. Number of elements in 1st array.
b. Numbers of 1st array.
c. Number of elements in 2nd array.
d. Numbers of 2nd array.
It should then print (1) both arrays as entered by the user (2) sorted arrays using the mergesort algorithm (3) the array obtained by merging the two arrays.
Hint: To verify that your merge works correctly, you can use the code from class that sorts arrays using selection, bubble or insertion sort. But make sure that the program you submit uses mergesort to sort the two arrays entered by the user.  Reply With Quote

22. ## Re: Sorting and Merging

I'm baffled as to what to do with my new array in inplace_merge.

Did he say to return it?  Reply With Quote

23. ## Re: Sorting and Merging

Ok, according to the directions, see above, I'm wondering how my mergesort method is supposed to help me get an array in the main method.

I'm kinda close to done, I hope, but am lost. Does it work for all values and for arrays with common elements and with only 1 element in one or both arrays?  Reply With Quote

24. ## Re: Sorting and Merging

Any help here would be hot.  Reply With Quote

25. ## Re: Sorting and Merging

Arrays are passed via reference rather than by value, so any changes you make to the object inside another method will be reflected in the original array. This is why your professor had you declare inplace_merge as void (since it doesn't need to return anything).

As a side note, for a true "in-place merge" you can't use a second list and call the original merge to merge these two together Of course, writing an efficient in-place merge requires linked lists and I can see why he has you write that method as it is.

You're algorithm's a bit off, too. Here's the java code that should get you what you want (there are some spots you'll need to fill in still)

```public static int[] merge(int[] A, int[] B)
{
int aIndex = 0; // current position of first array
int bIndex = 0; // current position of second array
int[] result = new int[A.length + B.length];

for(int i = 0; aIndex < A.length || bIndex < B.length; ++i)
{
if (aIndex < A.length && bIndex < B.length)
{
if (A[aIndex] <= B[bIndex])
{
// TODO: something needs to be added to the result array
// TODO: one of the two indices needs to be increased
}
else
{
// TODO: something needs to be added to the result array
// TODO: one of the two indices needs to be increased
}
}
else if (aIndex < A.length)
{
// TODO: something needs to be added to the result array
// TODO: one of the two indices needs to be increased
}
else
{
// TODO: something needs to be added to the result array
// TODO: one of the two indices needs to be increased
}
}
return result;

}

public static void inplace_merge(int[] A, int left, int middle, int right)
{
int[] leftArray = new int[/*TODO: how long should leftArray be?*/];
int[] rightArray = new int[/*TODO: how long should rightArray be?*/];
for (int i = 0; i < leftArray.length; ++i)
{
leftArray[i] = A[/*TODO: what index in the original array maps to the left array?*/];
}
for (int i = 0; i < rightArray.length; ++i)
{
rightArray[i] = A[/*TODO: what index in the original array maps to the right array?*/];
}
int[] merged = merge(leftArray, rightArray);
for (int i = 0; i < merged.length; ++i)
{
A[/*TODO: what index in the merged array maps to the original array?*/] = merged[i];
}
}```  Reply With Quote

26. ## The Following User Says Thank You to helloworld922 For This Useful Post:

javapenguin (December 5th, 2010)

27. ## Re: Sorting and Merging

```public static int[] merge (int[] A, int[] B)
{
int curr = 0; // current position of first array
int curr2 = 0; // current position of second array

int x = A.length + B.length;
int y = 0; // index of C
String str = "";
int[] C = new int[x];

for (int i =0; (curr < A.length || curr2 < B.length) && i < C.length; i++)
{
System.out.println(i);
if (curr < A.length && curr2 < B.length)
{
if (A[curr] <= B[curr2])
{
int temp = B[curr2];
C[i] = temp;
curr2++;
}
else
{
int temp2 = A[curr];
C[i] = temp2;
curr++;
}
}
else if (curr < A.length)
{
for (int var = curr ; var < A.length; var++)
{
int temp3 = A[var];
C[i] = temp3;
}
}
else
{
for (int var2 = curr2; var2 < B.length; var2++)
{
int temp4 = B[var2];
C[i] = temp4;
}
}
}
return C;
}```

Not quite working.  Reply With Quote

28. ## Re: Sorting and Merging

Hmm, are you sorting in ascending order or descending order? Though I guess that doesn't really matter.

The only thing I can see that's wrong is this section:

```else if (curr < A.length)
{
for (int var = curr ; var < A.length; var++)
{
int temp3 = A[var];
C[i] = temp3;
}
}
else
{
for (int var2 = curr2; var2 < B.length; var2++)
{
int temp4 = B[var2];
C[i] = temp4;
}
}```

The main for loop is designed so that one and only one value is added to the result matrix each time through. Take a look at the comments I had for this section again (there are 2 line comments, 1 line of code/comment, no other control structures needed).

Lastly, it's not necessary to create a temporary variable before setting it to another array (though technically there's nothing wrong with it) You can simply perform the assignment into the result array:

```// Version 1: old code
int temp3 = A[var];
C[i] = temp3;
// version 2: New hotness (bonus points if you can name the movie :D)
C[i] = A[var];```  Reply With Quote

29. ## The Following User Says Thank You to helloworld922 For This Useful Post:

javapenguin (December 5th, 2010)

30. ## Re: Sorting and Merging

Oh, I see why I had to do pre-increment. Doing post increment would sort it already.

Now working on inplace_merge.  Reply With Quote

31. ## Re: Sorting and Merging

Ok, am stuck with how to do the last step of inplace_merge

Also, why is it always

++variable  Reply With Quote
32. ## Re: Sorting and Merging  Reply With Quote