CODEWITHSUNDEEP
javaarraysstringvector
GuestUser140561
GuestUser140561

Reputation: 67

Sorted String Array - Insert value in order

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 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!

Upvotes: 0

Views: 1396

Answers (4)

Codo
Codo

Reputation: 78905

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.

Upvotes: 2

xiaofeng.li
xiaofeng.li

Reputation: 8587

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

Upvotes: 0

Vasu
Vasu

Reputation: 22442

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

Upvotes: 0

Rotem
Rotem

Reputation: 1379

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.

Upvotes: 0

Related Questions