aspose file tools*
The moose likes Java in General and the fly likes adding Strings to a list using Insertion sort Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "adding Strings to a list using Insertion sort" Watch "adding Strings to a list using Insertion sort" New topic
Author

adding Strings to a list using Insertion sort

Cj Powell
Greenhorn

Joined: Nov 25, 2011
Posts: 5
For some reason i am having a lot of problems with this.
I have a list of names i am adding to an array one at a time. i have to create my add method and use insertion sort to alphabatize the names as they come along and add them in the proper place.

I have tried a couple of ways, but i couldnt get it to work. The way i thought i could do it, with a for loop, said my add method doesnt work. In trying a variety of different methods to do this, i am now lost, and feel like i am really messing up all my code, and that it should be really simple.

I have to use compareTo and a two parameter add method to do this...here is my add method. Any help with this is greatly appreciated, even just guidance.

Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3739
    
  16
I'm not quite sure I understand your question, but what is the point of passing a parameter (comp) to a method which you immediately set to zero ?


Joanne
Cj Powell
Greenhorn

Joined: Nov 25, 2011
Posts: 5
I dont know I was thinking about using it as a place holder so it would represent the location in the list. But then again I know that arrays automatically move items up and down as you add items. So I know what I wrote doesn't work...but like I said this is the end product of me overthinking this.
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3739
    
  16
You're going to have to clarify what exactly you are trying to do.
You say you need to add some names to an array but you don't have any arrays in your sample code.
You have two collections of some sort (dwarves and holder), but you are using the same test (assuming the = on line 9 was meant to be ==) to decide whether to add the string to both of these.
The compareTo will always equal zero because w1 and w2 refer to the same object.

So you need to tell us
1. what are dwarves and holder ?
2. what decides which of these the string should be added to ?
3. why do you think you need two parameters for your add method ? The first parameter is obviously the string to be added but what is the second parameter ?
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3739
    
  16
Cj Powell wrote:I know that arrays automatically move items up and down as you add items

No they don't. Are you sure you mean arrays ? It seems more likely you are talking about an ArrayList which is not the same thing.
Jimmy Clark
Ranch Hand

Joined: Apr 16, 2008
Posts: 2187
It is easy and efficient to sort items in an array with java.util.Collections.sort().
Cj Powell
Greenhorn

Joined: Nov 25, 2011
Posts: 5
Ok, i was hoping for an easy answer that i was just missing something....Sorry about that...let me start over...here is what i have for my full code. including the add function. The one thing i havent accomplished with this, is that i need to change the add function so that it will add to the list in alphabetical order. In doing this i have to use Insertion Sort, and i need to use 2 parameter add method. Yes it is an Array list as you see, sorry i have been plugging at this all day, and i just fealt i was missing something with that method. This is different from what i had earlier, because as i said i am still trying to get it to work. I know as i add i need to look at the list i already have, and as i add to it, add to it accordingly. So the first add is simply just to the list, but the second add needs to look at the list and figure out where it needs to go. And i know that needs to be a loop. I guess do i create a holder ArrayList to put items into and take them out of, as i add them to the list. Or do i just need to assign the current list to a variable and then the current name to a variable and compare the two..but i assume you would need to iterate through the list to check it against each word. So check against position 0, then 1, then 2..so a for loop would work right? I feel like i am on the right path, just missing something small. Sorry for not posting up all the info.

Martin Vajsar
Sheriff

Joined: Aug 22, 2010
Posts: 3611
    
  60

Assuming this is not some kind of interface or assignment, I'd suggest to try to use standard collection classes as much as possible. Depending on your needs, two approaches seem to be most appropriate:

1) Do you need to access the collection using an index, as if it were an array? Store the entries in an ArrayList and use Collections.sort when all entries have been added.

2) Do you need the collection to be kept sorted while it is being built, or need to root out duplicate entries? Use a SortedSet implementation, ie. a TreeSet. You won't be able to efficiently access items using a numerical index, only iteration will be possible.

If your requirements are a mix of both, it can get tricky. You might be really needing a kind of structure that is not implemented in the JDK. I'd suggest to look around for a library that would suit your needs, like Google's guava library or Apache Commons. If all of this fails, the best way might be implementing a special collection that would encapsulate all of the functionality you need - much better than having the code responsible for it scattered all around your project.

If you're just practicing, you might be best off not using the libraries at all and implement your functionality over simple plain arrays. Even though an ArrayList is similar to an array, it is not identical and implementing the "classical" sorting algorithms effectively might be tricky when using collections and will surely differ from the textbook versions. This kind of practice is great to get better grasp of these algorithms (which is always a good thing), but may be of limited practical use, as you'll probably won't want to reinvent the wheels of the Collection Frameworks (and other libraries) in your programming career.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8244
    
  23

Cj Powell wrote:In doing this i have to use Insertion Sort, and i need to use 2 parameter add method.

So assuming this is a class assignment and you're not overly worried about efficiency; one way to do it would be to use Collections.binarySearch() to find the insertion point. Providing you do this for every element after the first, the List will always be in sorted order.
The nice thing about that method is that it returns the index at which a non-existent element should be inserted as a negative number.
If you do use the above approach, you should also decide what you want to do in the case of trying to add a duplicate (ie, existing) element.

However, Martin is quite right: adding them all and then sorting will be a lot quicker.

Winston


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39865
    
  28
If you want to add things in the middle of a List you should consider a LinkedList.
Cj Powell
Greenhorn

Joined: Nov 25, 2011
Posts: 5
Sorry for the late reply i was out with family for the weekend. So the challenge with this, is that i can not sort them after, i have to sort them as i place them in the list. I am going to try out both of your suggestions. Because i have not used either of those methods. I have been reading about using a TreeSet, and that seems like a good way to go, but i am a little confused about its implimentation. I willl try and get this working today, and post up with feedback and questions. Thank you so much for your guidance.
Cj Powell
Greenhorn

Joined: Nov 25, 2011
Posts: 5
Still working on this, i am going to try the TreeMap part next. but here is what i have with compareTo, although with this, i am getting a neverending loop with this, and no dwarves are actually added , this i feel is as close to what the problem is asking to do, but i am still missing something.

Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3739
    
  16
Cj Powell wrote:i am getting a neverending loop with this

To iterate over a list you need either a foreach loop or an iterator - you've got both.
Get rid of lines 18 and 19 and you should be fine.

The reason you have an infinite loop is that if you use an iterator, the call to hasNext() only checks if there is another item in the list. You have to read it from the list using something like this. Because you don't, hasNext is always returning true.
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8244
    
  23

Cj Powell wrote:So the challenge with this, is that i can not sort them after, i have to sort them as i place them in the list.

Did you read my post? Because what it says will allow you to perform an insertion sort on a List.
Don't let me stop you from learning about new structures, because it's all good stuff but, strictly speaking, a TreeSet does NOT perform an insertion sort; it uses a specialized structure (a tree) to allow a new element to be inserted at the correct point quickly. Whether that violates the rules of your challenge only you will know.

Winston
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: adding Strings to a list using Insertion sort