CODEWITHSUNDEEP
javaarrayssorting
Bg601
Bg601

Reputation: 49

Inserting a string into a sorted array

I'm having some problems figuring out how to do get this program to work in Java. I'm supposed to have a class WordList:

public class WordList{
    private int size; //number of words in array
    private String array1[]; //array of words
    private int capacity; // how big the array is supposed to be

And we're supposed to have two constructors: First one:

public WordList(int capacity){
    this.array1 = new String[capacity]; //makes a new array of specified capacity
    this.capacity = capacity; //sets the capacity
    this.size = 0; //sets the size of array (i.e. # of words) to 0
}

Second one:

public WordList (String[] arrayOfWords){
    this.capacity = 2 * arrayOfWords.length; //makes the capacity of array twice the # of words in input array
    this.array1 = new String[capacity]; //makes a new array
    this.size = arrayOfWords.length; //sets the # of words in array
    for (int i = 0; i < arrayOfWords.length; i++){ //loops through array
        this.insert(arrayOfWords[i]); //inserts the words (sorted into our array)
}
}

and finally an insert method. I think the main problem is here. I don't know if my two constructors are correct, but I'm 110% sure there's something wrong here:

public void insert(String newword){


    for (int i = 0; i < size; i++){
        int l = newword.compareTo(array1[i]);
        if (l > 0)
            continue; // means that the word we're inserting is after
        if (l < 0){
            for (int j = size; j > i; j--){
                array1[j] = array1[j-1]; //shifts all array elements over by one - starting at end of array to avoid over writing anything
            }
            array1[i] = newword;//inserts the word
        }
        if (l == 0)
            return;//doesn't do anything if word is already in list
    }
    }

Essentially it's supposed to insert the word provided into an already sorted array of words and keep the list sorted. The program just crashes. Any ideas on what might be wrong?

Upvotes: 1

Views: 1416

Answers (2)

Yang Yu
Yang Yu

Reputation: 356

In the for loop, try initialize j to size-1 instead of size. Also, please notice that while the program will run if you don't check the capacity in insert, you will lose the last element when inserting to a full array. Hope this helps.

Upvotes: 1

user949300
user949300

Reputation: 15729

Is this homework? I think it is, so I'll just give some ideas, not complete answers.

  1. Since the array is sorted, you could use Arrays.binarySearch() to find its location for insert()

  2. I know you build in some extra space in the constructor, but if you insert enough items, your array will need to grow. Insert will need to compare size and capacity.

  3. Think about your "shift everything right" code. Write down on paper ( or use index cards) an example initial array, do a gedanken insert, and go through your code one loop at a time updating the array. You likely have a bug there. Just saying... :-)

  4. Can you use System.arraycopy()? If so, use that when inserting or enlarging your array.

Upvotes: 0

Related Questions