Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sorting an Array in Java

  1. Jun 24, 2007 #1
    Hello,

    I need to write a method that adds an interger to a sorted array of integers. I'm using the following code to search for an interger in the array

    private static int binarySearch(int[] list, int key,
    int low, int high) {
    while (low <= high) {
    int mid = (low + high) / 2;
    int midVal = list[mid];

    if (midVal < key) {
    low = mid + 1;
    } else if (midVal > key) {
    high = mid - 1;
    } else {
    return mid; // key found
    }
    }
    return -(low + 1); // key not found.
    }

    I have not done programming in a long time, so I'm very confused on how to write the code to insert a number and preserved the sorted order.
    I would appreciate any help

    Thanks :smile:
     
  2. jcsd
  3. Jun 24, 2007 #2
    You could search for the next largest number, store it in a temporary variable and:

    1. Replace the number you just stored in the temp variable with the one you want to insert.
    2. Use the temporary variable to shift the array down by one.

    Eg:
    for(i=maxval;i>x;i--) /*x is the position of the next largest number maxval is the largest index number of the array*/

    {
    arr[x-1]=arr[x];
    }
    arr=j; //j is the number you want to insert and i=x now

    This is good enough for a static array, but for a dynamic one i guess you'd need to create a new array with one more element. I cant help you in the actual coding cause I only know c++. The logic, however, should be the same.
     
  4. Jun 24, 2007 #3

    rcgldr

    User Avatar
    Homework Helper

    He wants to add an item to a list, not delete it, so shouldn't that be:

    arr[x+1]=arr[x];

    ?
     
    Last edited: Jun 25, 2007
  5. Jun 24, 2007 #4
    Thanks for your help
     
  6. Jul 1, 2007 #5
    Since the array is static, one item will be deleted. If the array is dynamic, and you want to add an item in the middle, then you use the linked list approach, which is totally different.
     
  7. Jul 1, 2007 #6

    -Job-

    User Avatar
    Science Advisor

    If you're not required to use an array as your data structure then you should use a Vector instead, which is basically an array that automatically grows when necessary.

    Also, if this is a school assignment then you might get extra points if you code your binary search as a recursive function.
     
    Last edited: Jul 1, 2007
  8. Jul 2, 2007 #7
    How would you do that (the vector part)?
     
  9. Jul 3, 2007 #8

    -Job-

    User Avatar
    Science Advisor

  10. Jul 3, 2007 #9
    Vector<int> MyVector is not a valid code

    Vector<Integer> is valid, since you cannot pass primitives into the <> tags.

    It is generally recommended to use ArrayList instead of Vector class.

    That is one can do

    ArrayList<Integer> integerList = new ArrayList<Integer>();
    integerList.add(5);
    integerList.add(6);
    ...add as many as you like the list will grow as needed.
     
  11. Jul 3, 2007 #10

    -Job-

    User Avatar
    Science Advisor

    Sorry, i've been doing C# exclusively for the past 6 months and i use primitives in generic collections all the time.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Sorting an Array in Java
  1. [Java] Selection Sort (Replies: 4)

Loading...