Almost there
package sorting;
import java.util.Arrays;
import java.util.Scanner;
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
if (A.length ==0 && B.length !=0)
{
return(B);
}
if (A.length != 0 && B.length ==0)
{
return(A);
}
int x = A.length + B.length;
int[] C = new int[x];
for (int i =0; (curr < A.length || curr2 < B.length) && i < C.length; ++i)
{
System.out.println("i: " +i);
if (curr < A.length && curr2 < B.length)
{
if (A[curr] >= B[curr2])
{
C[i] = B[curr2];
curr2++;
}
else
{
C[i] = A[curr];
curr++;
}
}
else if (curr < A.length)
{
C[i] = A[curr];
curr++;
}
else
{
C[i] = B[curr2];
curr2++;
}
}
return C;
}
public static void inplace_merge(int[] A, int left, int middle, int right)
{
if (left < 0 || left > middle || left >= A.length)
return;
if (middle < left || middle > right || middle >=A.length || middle < 0)
return;
if (right < middle || right < 0 || right >=A.length)
return;
// if the array is empty
if (A.length ==0)
return;
// if the array has only one element
if (right == left)
return;
// if the array has only two elements
/* if (A.length ==2)
{
int[] specialsub = new int[1];
specialsub[0] = A[left];
int[] specialsub2 = new int[1];
specialsub2[0] = A[right];
int[] merged = merge(specialsub, specialsub2);
A[0] = merged[0];
A[1] = merged[1];
} */
System.out.println("A.length =" + A.length);
System.out.println("Left is:" + left);
System.out.println("Middle is:" + middle);
System.out.println("Right is:" + right);
System.out.println("middle-left =" + (middle-left));
int[] sub = new int[middle-left];
for (int x = 0; x < sub.length; ++x)
{
sub[x] = A[x + left];
}
System.out.println("First sub array is: " + Arrays.toString(sub));
System.out.println("Right is: " +right);
System.out.println("Middle is: " + middle);
System.out.println("Left is: " + left);
System.out.println("right - (middle+1) ="+ (right-(middle+1)));
int[] sub2 = new int[right - (middle+1)];
System.out.println("sub2.length =" + sub2.length);
for (int y = 0; y < sub2.length; ++y)
{
sub2[y] = A[y + middle + 1];
System.out.println("The value at A is: " +A[y+middle+1]);
}
System.out.println("Second sub array is: " + Arrays.toString(sub2));
int[] result = merge(sub, sub2);
System.out.println("Result array is: " + Arrays.toString(result));
for (int value =0; value < result.length; value++)
{
System.out.println("Value is: " + result[value]);
}
System.out.println("Result Array is: " +Arrays.toString(result));
int index = 0;
for (int z = left + 1; z < right; ++z)
{
System.out.println("Index: " + index);
A[z] = result[index];
index++;
}
}
public static void mergesort(int[] A, int left, int right)
{
// don't bother with empty arrays
if (left >=right)
return;
int middle = (left + right) /2;
mergesort(A, left, middle);
mergesort(A, middle+1, right);
inplace_merge(A, left, middle, right);
// System.out.println(Arrays.toString(A));
}
public void sort(int[] A)
{
// mergesort(A, ?, ?);
}
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.length; 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));
/*
System.out.println("Merging 2 arrays");
System.out.println("New array: " + Arrays.toString(merge(array, array2)));
int[] array3 = merge(array, array2);
System.out.println("Using in place merge on array 3");
//inplace_merge(array3, 0, (int) ((array3.length -1) - 0)/2, array3.length -1);
*
*/
mergesort(array, 0, array.length -1);
mergesort(array2, 0, array2.length-1);
System.out.println(Arrays.toString(array));
System.out.println(Arrays.toString(array2));
int[] array3 = merge(array, array2);
System.out.println(Arrays.toString(array3));
}
}
Enter the number of elements in the first array.
3
Enter the value at index 0
-1
Enter the value at index 1
0
Enter the value at index 2
1
Enter the number of elements in the second array.
4
Enter the value at index 0
3
Enter the value at index 1
5
Enter the value at index 2
7
Enter the value at index 3
9
Array 1: [-1, 0, 1] Array 2: [3, 5, 7, 9]
A.length =3
Left is:0
Middle is:0
Right is:1
middle-left =0
First sub array is: []
Right is: 1
Middle is: 0
Left is: 0
right - (middle+1) =0
sub2.length =0
Second sub array is: []
Result array is: []
Result Array is: []
A.length =3
Left is:0
Middle is:1
Right is:2
middle-left =1
First sub array is: [-1]
Right is: 2
Middle is: 1
Left is: 0
right - (middle+1) =0
sub2.length =0
Second sub array is: []
Result array is: [-1]
Value is: -1
Result Array is: [-1]
Index: 0
A.length =4
Left is:0
Middle is:0
Right is:1
middle-left =0
First sub array is: []
Right is: 1
Middle is: 0
Left is: 0
right - (middle+1) =0
sub2.length =0
Second sub array is: []
Result array is: []
Result Array is: []
A.length =4
Left is:2
Middle is:2
Right is:3
middle-left =0
First sub array is: []
Right is: 3
Middle is: 2
Left is: 2
right - (middle+1) =0
sub2.length =0
Second sub array is: []
Result array is: []
Result Array is: []
A.length =4
Left is:0
Middle is:1
Right is:3
middle-left =1
First sub array is: [3]
Right is: 3
Middle is: 1
Left is: 0
right - (middle+1) =1
sub2.length =1
The value at A is: 7
Second sub array is: [7]
i: 0
i: 1
Result array is: [3, 7]
Value is: 3
Value is: 7
Result Array is: [3, 7]
Index: 0
Index: 1
[-1, -1, 1]
[3, 3, 7, 9]
i: 0
i: 1
i: 2
i: 3
i: 4
i: 5
i: 6
[-1, -1, 1, 3, 3, 7, 9]
LinkBack URL
About LinkBacks
Update on "Sorting and Merging"
Reply With Quote
Related threads:
Re: Update on "Sorting and Merging"
Re: Update on "Sorting and Merging"