0

I was wondering if somebody could give me some pointers for a piece of work that I'm currently working on.

The concept is that I've got to create a Sorted Vector, using a String Array list, and be able to Add, Delete and Find items from the array.

I'm currently really struggling with the Adding of an Item.

In the constructor we have:

private int maxlength;
private int numberofitems;
private String[] data;
private int growby;

And they've been initalized with the values:

maxlength = 10;
numberofitems = 0;
data=new String[maxlength];
growby=10;

I then have a function that takes a String Value and needs to insert the value into the array:

public void AddItem(String value)
{

  if (maxlength == data.length)
  {
    GrowArray();
  }

  //Need Help here
}

^^ That is the point at which I need help.

GrowArray simply creates a temp Array which increases the maxlength by 10, and copies across all the values from the old array to the new one.

private void GrowArray()
{
    String[] data2=new String[data.length+growby];
    System.arraycopy(data, 0, data2, 0, data.length);
    data=data2;
}

My logic is this:

  • I need to loop through the array and compare the search Value being against each item in the array and see whether it belongs before or after the current array value.

I know this should look something like: data[i].compareTo(value) <0;

Any and all help would be greatly appreciated. I should also mention that I'm not allowed to use collections.

Thanks!

Improve this question

4 Answers 4

Reset to default
2

Just use Arrays.binarySearch(). It searches for an element in a sorted array. If the array is not found, it returns the insertion point (or rather (-(insertion point) - 1) ).

So the missing code could look like this:

// find index for insertion
int insertionIndex = Arrays.binearySearch(data, value);
if (insertionIndex < 0) {
    insertionIndex = -insertionIndex - 1;
}

// move elements
if (insertionIndex < data.length) {
    System.arraycopy(data, insertionIndex, data, insertionIndex + 1, data.length - insertionIndex - 1);
}

// insert element
data[insertionIndex] = value;

Fortunately, Arrays.binarySearch uses compareTo.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Nice, technically not using Collections. I wonder whether Arrays is allowed.
A small issue, when not found, the insertion position should be -insertionIndex - 1.
0

A simple approach is to append the new item to the end of the array, then swap it with the previous item if it's smaller, repeat until it is in the correct position. I also corrected your condition for growing the array. You don't need the maxlength member field, you have data.length.

// Grow array when array is full.
if (numberofitems >= data.length) GrowArray();

// Append to the end, at this point we always have enough space.
data[numberofitems++] = value;

// data[i] holds the new item
// Loop until we reach the head (i==0) or data[i]>=data[i-1]
for (int i = numberofitems - 1;
     i > 0 && data[i].compareTo(data[i-1]) < 0;
     i--) {
    // Swap data[i] (the new item) with its predecessor.
    String t = data[i-1];
    data[i-1] = data[i];
    data[i] = t;
}

To follow the Java naming convention, rename your fields and methods.

numberofitems -> numberOfItems
growby -> growBy
GrowArray -> growArray
Improve this answer

Comments

0

java.lang.String implements Comparable, means you can create any implementation to the compare method.

A custom Comparator can look like that:

public class sortString implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return o1.compareTo(o2);
    }
}

Note: The compare() method must return an int value .

The code which sort the data array can look like the following:

Collections.sort(ArrayList, new sortString());

The edition of the elements can be with no regard to the position of the String and after you added all the Strings you can sort them together and get Sorted ArrayList.

Another option can be to use the compare() method while iterating over the ArrayList of Strings and find the right position to add the new data item.

Improve this answer

2 Comments

I don't think I'm allowed to use Collections unfortunately. It all has to be done 'manually'.
in that case you should use the compare method to find the position where you can add the new String. iterate over the Sorted Array and the int result of the compare method can help you find the position to add the new item
0

You need to sort the String elements inside the addItem(String value) as shown in the below code with inline comments (the below logic uses compareTo() of String objects):

      public void addItem(String value) {

          //add element to array and increment numberofitems
          data[numberofitems] = value;
          numberofitems++;

          //check the array size and call grow
          if (maxlength == data.length) {
             GrowArray();
          }

          //Sort the String elements
          String temp =null;
          for(int i=0;i< data.length;i++) {
              for(int j=0;j<data.length;j++) {
                    if(data[i].compareTo(data[j]) < 0) {
                       temp = data[i];
                       data[i]= data[j];
                       data[j] =temp;
                    }
                }
          }
        }

Also, I suggest you to follow Java naming standards for method/class/variable names (GrowArray() is not accroding to Java naming standards, look here for details).

Improve this answer

3 Comments

Thank you, that's very useful. :) At which point would I add in the new value?
You don't have to loop through the array to find the last element, it's numberOfItems, and you need to increment it after adding another item. Anyway, no complete sort is required. See other answers.
Thank you, I have used numberOfItems. I used bubble sort.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.