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.

View Poll Results: Do you think I'm kind of annoying?

Voters
1. You may not vote on this poll
  • Yes

    0 0%
  • No

    0 0%
  • Maybe/Not sure

    1 100.00%
Results 1 to 6 of 6

Thread: Update on "Sorting and Merging"

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

    Question 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.

    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.


  2. #2
    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: 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]



  3. #3
    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: Update on "Sorting and Merging"

    Also, why is it going in decreasing order?

  4. #4
    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: 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?
    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));
    }
     
     
    }

  5. #5
    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: Update on "Sorting and Merging"

    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]





  6. #6
    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: Update on "Sorting and Merging"

    Anybody there?

Similar Threads

  1. Replies: 6
    Last Post: November 12th, 2010, 04:40 AM
  2. Java says:"Hello World". I say:"It works!"
    By Davidovic in forum Member Introductions
    Replies: 4
    Last Post: June 29th, 2010, 08:13 AM
  3. Replies: 1
    Last Post: March 31st, 2010, 10:42 PM
  4. "java.lang.NoSuchMethodError: main" and "fatal exception occured."
    By joachim89 in forum What's Wrong With My Code?
    Replies: 2
    Last Post: January 10th, 2010, 08:35 AM
  5. Replies: 4
    Last Post: August 13th, 2009, 06:54 AM