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


Members have full access to the forums. Advertisements are removed for registered users.

Page 2 of 2 FirstFirst 12
Results 26 to 37 of 37

Thread: Sorting and Merging

  1. #26
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Sorting and Merging

    Here's the new code:
    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
     
    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])
    		{
     
    			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;
    /*
    while ((curr < A.length) && (curr2 < B.length))
    {
    if ( A[curr] > B[curr2] )
    {
    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)
    {
     
    	if (left ==right)
    		return;
     
    int[] sub = new int[middle-left];
     
    for (int x = 0; x < sub.length; ++x)
    {
    sub[x] = A[x + left];
    }
     
    int[] sub2 = new int[right - (middle+1)];
     
    for (int y = 0; y < sub2.length; ++y)
    {
    sub2[y] = A[y + middle + 1];
    }
     
    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);
    System.out.println(Arrays.toString(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("New array: " + Arrays.toString(merge(array, array2)));
     
    inplace_merge(array, array[0], array[(int) (array[(array.length -1)] - array[0])/2], array[array.length -1]);
    System.out.println(Arrays.toString(array));
    }
     
     
    }

     

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 1
    at sorting.Merge.inplace_merge(Merge.java:128)
    at sorting.Merge.main(Merge.java:184)




    [error]
    A[z] = result[index];
    [/error]

  2. #27
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Unhappy Re: Sorting and Merging

    Ok, I've noticed something, but I've no clue why.

    It seems that my two sub arrays are empty.

    How come?

    ^:^:-((

  3. #28
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default Re: Sorting and Merging

    Quote Originally Posted by javapenguin View Post
    Ok, am stuck with how to do the last step of inplace_merge

    Also, why is it always

    ++variable

    instead of variable++

    ?
    As I'm using it, there's no difference. The reasons are mostly historical (in some other languages there were performance advantages to doing ++variable, though in Java I don't believe there is any difference performance wise).

    for (int z = left; z <= right; ++z)
    You're checking 1 too many to the right. Use z < right.

    Ok, I've noticed something, but I've no clue why.

    It seems that my two sub arrays are empty.

    How come?
    Merge sort is a recursive algorithm, and as such it reduces the problem until it becomes elementary. There are 2 such cases: arrays of length 0 and arrays of length 1. Both cases are by default "sorted".

    edit:

    Oh, and last note, you're algorithm is sorting your array in descending order (try running through merge by hand with the following arrays: {1}, {2})
    Last edited by helloworld922; December 6th, 2010 at 10:55 AM.

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

    javapenguin (December 6th, 2010)

  5. #29
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Sorting and Merging

    I want it to sort in ascending order.

    That's part of the reason why I asked if the ++variable instead of variable++ would make a difference.

  6. #30
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Red face Re: Sorting and Merging

    Also
    inplace_merge(array, array[0], array[(int) (array[(array.length -1)] - array[0])/2], array[array.length -1]);

    It doesn't like this line, found in main method.

    Wait.....



    I'm not supposed to be subtracting the values at those indexes, just the indexes for the middle one!

    Let's see what happens when I fix that.

  7. #31
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Sorting and Merging

    I seem to be losing at least half of my array.

    Plus, I don't think it's doing it in ascending order.

    Maybe the mergesort will do that.

    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 ==right)
            return;
     
    int[] sub = new int[middle-left];
     
    for (int x = 0; x < sub.length; ++x)
    {
    sub[x] = A[x + left];
    }
     
    int[] sub2 = new int[right - (middle+1)];
     
    for (int y = 0; y < sub2.length; ++y)
    {
    sub2[y] = A[y + middle + 1];
    }
     
    int[] result = merge(sub, sub2);
    for (int value =0; value < result.length; value++)
    {
    	System.out.println("Value is: " + result[value]);
    }
     
    System.out.println(Arrays.toString(result));
    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);
    System.out.println(Arrays.toString(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);
    System.out.println(Arrays.toString(array3));
    }
     
     
    }

     

    Enter the number of elements in the first array.
    2
    Enter the value at index 0
    1
    Enter the value at index 1
    2
    Enter the number of elements in the second array.
    2
    Enter the value at index 0
    3
    Enter the value at index 1
    4
    Array 1: [1, 2] Array 2: [3, 4]
    Merging 2 arrays
    i: 0
    i: 1
    i: 2
    i: 3
    New array: [3, 4, 1, 2]
    i: 0
    i: 1
    i: 2
    i: 3
    Using in place merge on array 3
    i: 0
    i: 1
    Value is: 3
    Value is: 1
    [3, 1]



     

    Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2
    at sorting.Merge.inplace_merge(Merge.java:100)
    at sorting.Merge.main(Merge.java:158)


    Last edited by javapenguin; December 6th, 2010 at 03:25 PM. Reason: ArrayIndexOutOfBoundsException

  8. #32
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Sorting and Merging

    Ok, why is right always 1 and left and middle always 0?

  9. #33
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Unhappy Re: Sorting and Merging

    What's going wrong?

    ^

  10. #34
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Sorting and Merging

    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; 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 (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));
    }
     
     
    }

    What's wrong with my code?

    Stupid index out of bounds exception for that for loop at the end of inplace_merge.
    Last edited by javapenguin; December 7th, 2010 at 12:38 PM.

  11. #35
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Talking Re: Sorting and Merging



    Fine, I'll come back in the morning, and hope that somebody has responded to me.

    >

  12. #36
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Default Re: Sorting and Merging

    Hey, I got it to stop throwing that error, but the output isn't quite what I'd hoped it to be. It seems to lose some values.
    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 (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));
    }
     
     
    }

     

    Enter the number of elements in the first array.
    2
    Enter the value at index 0
    1
    Enter the value at index 1
    3
    Enter the number of elements in the second array.
    2
    Enter the value at index 0
    5
    Enter the value at index 1
    7
    Array 1: [1, 3] Array 2: [5, 7]
    Merging 2 arrays
    i: 0
    i: 1
    i: 2
    i: 3
    New array: [5, 7, 1, 3]
    i: 0
    i: 1
    i: 2
    i: 3
    Using in place merge on array 3
    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: []
    [5, 7, 1, 3]
    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: []
    [5, 7, 1, 3]
    A.length =4
    Left is:0
    Middle is:1
    Right is:3
    middle-left =1
    First sub array is: [5]
    Right is: 3
    Middle is: 1
    Left is: 0
    right - (middle+1) =1
    sub2.length =1
    The value at A is: 1
    Second sub array is: [1]
    i: 0
    i: 1
    Result array is: [5, 1]
    Value is: 5
    Value is: 1
    Result Array is: [5, 1]
    Index: 0
    Index: 1
    [5, 5, 1, 3]
    [5, 5, 1, 3]



  13. #37
    Banned
    Join Date
    May 2010
    Location
    North Central Illinois
    Posts
    1,631
    My Mood
    Sleepy
    Thanks
    390
    Thanked 112 Times in 110 Posts

    Exclamation Re: Sorting and Merging

    Anybody 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.
    1
    Enter the value at index 0
    1
    Enter the number of elements in the second array.
    3
    Enter the value at index 0
    1
    Enter the value at index 1
    2
    Enter the value at index 2
    3
    Array 1: [1] Array 2: [1, 2, 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: []
    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
    [1]
    [1, 1, 3]
    i: 0
    i: 1
    i: 2
    i: 3
    [1, 1, 1, 3]




    PLEASE! PLEASE! PLEASE! PLEASE! PLEASE! PLEASE! PLEASE HELP ME! I've been waiting all day!!!


    :-^

Page 2 of 2 FirstFirst 12

Similar Threads

  1. Merging of Trees..
    By Kumarrrr in forum What's Wrong With My Code?
    Replies: 1
    Last Post: March 24th, 2010, 12:39 AM
  2. Merging Arrays Vs. Linked List.
    By Kumarrrr in forum Collections and Generics
    Replies: 1
    Last Post: March 1st, 2010, 03:20 AM
  3. merging two tables from two diffrent htmls files using java
    By sukant_at in forum File I/O & Other I/O Streams
    Replies: 3
    Last Post: September 1st, 2009, 06:13 AM
  4. merging two tables from two diffrent htmls files using java
    By sukant_at in forum File I/O & Other I/O Streams
    Replies: 2
    Last Post: August 7th, 2009, 01:48 PM
  5. Problem in merging two java classes
    By madkris in forum Object Oriented Programming
    Replies: 11
    Last Post: March 16th, 2009, 10:02 AM