Sort ArrayList

I have an array full of objects... With in each object there contains an in representing a certain property.

Before I add a new object I wish to place it in the appropriate area within the array..

example  
valuse of each object in the array =  [9,8,7,3,2,1]

I wish to add a new object to the array for example 6
I want it as follows [9,8,7,6,3,2,1]
And so on

A bubble sort algorithm maybe ?? Any one got any ideas?


 
conorocallaghanAsked:
Who is Participating?
 
nikkilockeCommented:
Hi conorocallaghan,

A binary chop might be best. If the array is already sorted, there is no need to sort it again, just insert the new entry in the right place.

Do you want more information about how a binary chop works?

Hope this helps,

Nikki
0
 
TimYatesCommented:
Arrays.sort( array, Collections.reverseOrder() ) ;
0
Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
conorocallaghanAuthor Commented:
nikkilocke :
if you have any more info on a binary chop that would be great
0
 
TimYatesCommented:
just add it to the end, and sort it again using Arrays.sort...

Or collections.sort if it is a List that you have (you say it is an Array, but you could mean ArrayList)

Tim
0
 
conorocallaghanAuthor Commented:
My mistake Its an ArrayList.. and it gets pretty big too so the minimum messing around with it the better...

0
 
TimYatesCommented:
>> so the minimum messing around with it the better...

How big?

How often do you add items to it?

What class is the object inside it?

Basically, dependant on these questions, adding to the end and sorting the whole thing may still be the best solution...

Tim
0
 
conorocallaghanAuthor Commented:
TIM,
 basicaly I'm parsing a log file... Each line in the log file is an event.

For each line in the file, I create an object representing it.

Provided the object is not in the arraylist already, I insert it to the end of the array.

However if the object exists I modify the one in the array by incrementing its count..
The file can contain over 200,000 lines, so obviously checking for duplicates is pretty time intensive.

If I arrange the arraylist having the object with the most occurences at the start and so on, it will speed up the search.

So to answer your question,

How big?   = 80,000+

How often do you add items to it? if the are all unique then 200,000 times, other wise it can varey

What class is the object inside it? the class in side the array is one I created my self.. It contains strings and dates and ints.

0
 
TimYatesCommented:
0
 
conorocallaghanAuthor Commented:
How will it be sorted?? How can the treeSet determine how to sort it?

Going to read up on it now... thanks
0
 
TimYatesCommented:
>> How can the treeSet determine how to sort it?

You implement Comparable in your class, and the TreeSet automatically puts your object in the right location when you add it in :-)

Cool eh?

Basically, you implement Comparable

then write a method:

      public int compareTo( Object obj )
      {
            MyClass other = (MyClass) obj;
            return this.intValue - other.intValue ; // Or any other comparison you want to do other.something.compare for example
      }

and also write a method:

      public boolean equals( Object obj )
      {
            MyClass other = (MyClass) obj;
                return other.param.equals( this.param ) ; // or whatever defines equality in your class :-)
      }

Then it should all be taken care of for you...

Oh yeah, you may want to implement hashCode:

       public int hashCode()
       {
                return this.uniqueObject.hashCode() ;
       }

Woo!

Tim
0
 
conorocallaghanAuthor Commented:
Thats sounds like the business.

one more question, is the TreeSet as efficient as the ArrayList?
I presume it is.
0
 
TimYatesCommented:
obviously, it's slightly slower, as it has to do a "binary chop" when it adds a new item, but it's not so much slower as you'd notice :-)

And it saves you having to write all that code (that it does anyway)

And it's probably more efficient that writing the code to do the same thing ;-)

Tim.
0
 
conorocallaghanAuthor Commented:
I've a problem with the TreeSet!

If  it contains a certain object, I wish to modify that object.. I'm unable to do that with the treeSet

What I want is the ability to extract the duplicate object and modify it accordingly

This is how I was doing it with the ArrayList

if(arrDupEvents.size()!=0){
       int dupIndex =arrDupEvents.indexOf(temp);

      if(dupIndex!=-1)
      {
      String date = temp.getDate(0);
      String threadnum = temp.getThreadNumber(0);
      String msgDate = temp.getMessageDate(0);

      temp = (CEvent)arrDupEvents.get(dupIndex);
      temp.incrementCount();
      temp.addDate(date);
      temp.addThreadNumber(threadnum);
      temp.addMessageDate(msgDate);
      temp.addLineNumber(currentlinenum);
      return;                                                
     }                  
}
0
 
TimYatesCommented:
Actually...  you only need this sorting at the end don't you?

Your current code should work whilst you are processing the data, then you can sort the data once all the lines are read using:

  Collections.sort( arrDupEvents, Collections.reverseOrder() ) ;

Then you can just use your ArrayList method as you were before...

Tim
0
 
CEHJCommented:
>>What I want is the ability to extract the duplicate object

Not sure what 'duplicate' means here, but bear in mind that a Set cannot contains duplicates as defined by your equals method
0
 
conorocallaghanAuthor Commented:
To reply to your question about only needing to sort at the end. the answer is no..
I need to sort the array on the fly...
I.e as more and more elements get found I must increment a count with in my object which is contained in the array.. If the count is greater then I wish to move the object accordingly back up towards '0' in the array.



0
 
TimYatesCommented:
They should help.  Basically, it's back to square 1...

That code shows you how to insert an object in the correct position in a sorted list, and how to find an object in a sorted list...

Tim
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.