Update on "Sorting and Merging"

• December 7th, 2010, 01:38 PM
javapenguin
Update on "Sorting and Merging"
I've gotten the code to slightly work better, though it's not doing what it's supposed to still.

Also, I have no clue how to call the sort(int[] A) method, which appears to just supposed to call
mergesort(int[] A, left, right).

I figured out why it was throwing that error earlier. I was supposed to be going between left and right, but I had been including left. #-o

Code java:

```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 (A.length ==0) return; // it's already sorted if it has only 1 element if (left>=right) return; if ((right + left)/2 < left) return; if ((right + left)/2 > right) return; if (left < 0) return; if (right < 0) return; if (left >=A.length) return; if (right >= A.length) 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(array3, 0, array3.length -1); System.out.println(Arrays.toString(array3)); }     }```

It's changing so values it's not supposed to and losing others. And worst of all, it's not sorting it into ascending order.
• December 7th, 2010, 02:19 PM
javapenguin
Re: Update on "Sorting and Merging"

```
Enter the number of elements in the first array.
1
Enter the value at index 0
-50
Enter the number of elements in the second array.
2
Enter the value at index 0
0
Enter the value at index 1
50
Array 1: [-50] Array 2: [0, 50]
Merging 2 arrays
i: 0
i: 1
i: 2
New array: [0, 50, -50]
i: 0
i: 1
i: 2
Using in place merge on array 3
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: []
[0, 50, -50]
A.length =3
Left is:0
Middle is:1
Right is:2
middle-left =1
First sub array is: [0]
Right is: 2
Middle is: 1
Left is: 0
right - (middle+1) =0
sub2.length =0
Second sub array is: []
Result array is: [0]
Value is: 0
Result Array is: [0]
Index: 0
[0, 0, -50]
[0, 0, -50]
```
• December 7th, 2010, 02:36 PM
javapenguin
Re: Update on "Sorting and Merging"
Also, why is it going in decreasing order?
• December 7th, 2010, 03:25 PM
javapenguin
Re: Update on "Sorting and Merging"
Hey, I found part of the problem.

But why is it copying the value at index 0 of each array into index 1 whenever I use mergesort?
Code java:

```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)); }     }```
• December 7th, 2010, 05:00 PM
javapenguin
Re: Update on "Sorting and Merging"
Almost there
Code java:

```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]
```

^:)^^:)^^:)^^:)^^:)^^:)^^:)^^:)^^:)^^:)^=((:((~X(
• December 7th, 2010, 06:45 PM
javapenguin
Re: Update on "Sorting and Merging"
Anybody there?