0

I have a list of strings that are already in alphabetical order. Here we are just going to assume the user enters the items in alphabetical order.

I have a list of string items in a class and a method where someone can pass in another string object to be inserted into the array.

String[] strings = new Strings[0];

public void add(String a){
//here the current list is resized and we need to add the new item
Strings[] newSizedList = new String[strings.length+1];
//for loop here to copy items over into the new resized array.
}

The issue is, the list is assumed to be in alphabetical order already. What I need to do is insert the passed in string into its correct position in the array while still keeping the other items in alphabetical order.

The restriction is that I do not want to use any sort of "sorting algorith". In other words, I do not want to sort the entire list at once and put it in order.

I would like to keep the item in order that it is in since it is already in order but insert the current item into its respective position in the list.

I cannot use any Collection static methods or Java collection classes static methods

Does anyone know how this can be done?

user1664285
  • 23
  • 1
  • 5
  • you could insert your String in any position then use Arrays.sort() or take a look at this post if you want to implement you method to sort the array http://stackoverflow.com/questions/12986386/sorting-an-array-of-strings-with-java – JHDev Apr 16 '16 at 19:13

3 Answers3

1

Since you are going to clone the array using for-loop anyways, there is no need to do any kind of sorting here (which should be good news as you said that's not an option). Just insert the new item in its right place when going thorugh the items.

//for loop here to copy items over into the new resized array.
//We use two counters here, ii for the old list and i for the new
int ii = 0, nn = strings.length;
for(int i = 0, n = newSizedList.length; i < n; i++) {

    if(ii != nn && (ii != i || strings[ii].compareTo(a) < 0)){
        //The item in newSizedList[i] will be taken from the original list if
        //we have not already taken all the items from there (ii != nn) and
        //a) we have already inserted the new item (ii != i)
        //or b) a is alphabetically "greater" than the corresponding item in original array
        newSizedList[i] = strings[ii];
        ii++;//Keep the other counter in sync
    } else  {
        //Otherwise, this is the place for the new item
        newSizedList[i] = a;
    }

}
noppa
  • 3,947
  • 21
  • 22
  • What if I had a list of items passed in and I would like to enter these items in the passed in list in alphabetical order using the same algorithm above? – user1664285 Apr 18 '16 at 17:39
  • Unfortunately that would add quite a bit of complexity to the problem and thus this snippet would also need some changes. For example, the `i != ii` test wouldn't work and you'd need to do comparisons with all the items in that array, now we are just comparing to `a`. With some changes it should still be possible, but you'll save a lot of trouble if you just sort the array or use a SortedSet like the others have suggested. This approach works here because the task of inserting just one item is quite simple. – noppa Apr 18 '16 at 17:57
  • I see what you mean. So what I will do is have a method that takes a list of strings as the param and then loop through the list adding each string to its correct position in the array by calling the method above for each string in the list. Does this sound like a good solution? – user1664285 Apr 18 '16 at 17:59
  • @user1664285 Hmm... well I gave it a try anyways and it didn't turn out to be that difficult after all, at least not if the new list would also be sorted already. Take a look at https://repl.it/CGsy/0 – noppa Apr 18 '16 at 18:15
0

Arrays.binarySearch can be used to find the correct insertion point efficiently.

Alex Hall
  • 34,833
  • 5
  • 57
  • 89
0

Simply call the right method in the Arrays class.

Arrays.sort(newSizedList);
Dinsdale
  • 184
  • 3
  • 12