?
Solved

Sort ArrayList

Posted on 2005-04-22
21
Medium Priority
?
240 Views
Last Modified: 2010-03-31
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?


 
0
Comment
Question by:conorocallaghan
18 Comments
 
LVL 2

Expert Comment

by:nikkilocke
ID: 13842455
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
 
LVL 35

Expert Comment

by:TimYates
ID: 13842456
Arrays.sort( array, Collections.reverseOrder() ) ;
0
 

Author Comment

by:conorocallaghan
ID: 13842486
nikkilocke :
if you have any more info on a binary chop that would be great
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 35

Expert Comment

by:TimYates
ID: 13842520
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
 

Author Comment

by:conorocallaghan
ID: 13842551
My mistake Its an ArrayList.. and it gets pretty big too so the minimum messing around with it the better...

0
 
LVL 35

Expert Comment

by:TimYates
ID: 13842586
>> 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
 

Author Comment

by:conorocallaghan
ID: 13842667
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
 
LVL 35

Expert Comment

by:TimYates
ID: 13842741
0
 

Author Comment

by:conorocallaghan
ID: 13842787
How will it be sorted?? How can the treeSet determine how to sort it?

Going to read up on it now... thanks
0
 
LVL 35

Expert Comment

by:TimYates
ID: 13842841
>> 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
 

Author Comment

by:conorocallaghan
ID: 13842881
Thats sounds like the business.

one more question, is the TreeSet as efficient as the ArrayList?
I presume it is.
0
 
LVL 35

Expert Comment

by:TimYates
ID: 13842965
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
 

Author Comment

by:conorocallaghan
ID: 13843565
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
 
LVL 35

Expert Comment

by:TimYates
ID: 13843820
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
 
LVL 86

Expert Comment

by:CEHJ
ID: 13845626
>>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
 

Author Comment

by:conorocallaghan
ID: 13856731
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
 
LVL 35

Accepted Solution

by:
TimYates earned 1000 total points
ID: 13856748
0
 
LVL 35

Expert Comment

by:TimYates
ID: 13856756
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

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

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.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java contains several comparison operators (e.g., <, <=, >, >=, ==, !=) that allow you to compare primitive values. However, these operators cannot be used to compare the contents of objects. Interface Comparable is used to allow objects of a cl…
Are you developing a Java application and want to create Excel Spreadsheets? You have come to the right place, this article will describe how you can create Excel Spreadsheets from a Java Application. For the purposes of this article, I will be u…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Suggested Courses
Course of the Month14 days, 9 hours left to enroll

839 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question