We help IT Professionals succeed at work.

We've partnered with Certified Experts, Carl Webster and Richard Faulkner, to bring you two Citrix podcasts. Learn about 2020 trends and get answers to your biggest Citrix questions!Listen Now

x

How to sort Arraylist that contains objects?

on
Medium Priority
612 Views
Hi all.
I have an ArrayList that contains objects which then contain strings as names.
I want to sort the ArrayList by the names of the obejcts. Any clever fast method?

Example code:
ArrayList thisList = new ArrayList();
MyOwnClass myClass = new MyOwnClass("myName", 1,2,3,4);
...

Now I want to get a thisList that is sorted by myClass.getName().
Comment
Watch Question

View Solutions Only

Commented:
You should implement the IComparable interface on your MyOwnClass. It would look something like this:

public int CompareTo(object obj)
{
if (obj is MyOwnClass)
{
MyOwnClass other = (MyOwnClass)obj;
return this.getName().CompareTo(other.getName());
}
else
{
throw new ArgumentException();
}
}

Now you can simply call the Sort() method on the ArrayList theList.

Commented:
Its also good, if you are using a sorted arraylist, to maintain your arraylist as sorted so that you don't have to call Sort. This is much, much faster so you should do it if you are worried about performance. You do this by implementing IComparable as Divinity says, and then using BinarySearch to do the insert:

int intBinary = this.myArrayList.BinarySearch(myObject);
if (intBinary >= 0)
// already exists in list according to IComparable
else
{   // otherwise insert into the list at the complement of the integer returned, which maintains the sort
int intInsertAt = ~intBinary;
this.myArrayList.Insert(intInsertAt, myObject);
}

As BinarySearch is O(log2 n), and Contains is O(n), if you maintain a sorted list it can help a lot with performance when you are doing a lot of object location in your list.

Andy

Commented:
There are two methods to tackle this.  Both use the ArrayList's Sort() method.

Method 1:
Make my class implement the IComparable interface:

public class MyOwnClass : System.Collections.IComparable
{
...My Class Stuff...
#region IComparable Implementation
int CompareTo(object obj)
{
MyOwnObject otherObj=obj as MyOwnObject;
If (obj==null)
throw new UnsupportedException("object is null or not an instance of MyOwnObject");
//..Implement code to compare 'this' against 'otherObj', returning :
//             Less than zero            This instance is less than obj.
//             Zero                       This instance is equal to obj.
//             Greater than zero      This instance is greater than obj.
}
#end region
}

Then you can call thisList.sort();  to sort the array

Method 2

Implement another class that implements IComparer
public class MyOwnClassComparer : System.Collections.IComparer
{
int Compare(object x, object y)
{
MyOwnClass obj1=x as MyOwnClass;
MyOwnClass obj2=y as MyOwnClass;
If (obj1==null || obj2==null)
throw new UnsupportedException("object is null or not an instance of MyOwnObject");
//..Implement code to compare 'obj1' against 'obj2', returning :
//             Less than zero            This instance is less than obj.
//             Zero                       This instance is equal to obj.
//             Greater than zero      This instance is greater than obj.
}
}

You would use method 2 if you did not want(or could not) to modify the class being sorted, or you want to vary the sort based on context(e.g. change sort columns and/or sort direction).  Method 1 would probably sort the class only by one specific way.

Commented:
Ok, thanks guys. The concept of iComparer is new to me. Will look into it and try to get it working. Expect an answer in a few hours :)

Commented:
Wow, AGBrown, I never thought of it that way. Thanks for sharing that information.

Commented:
Stupid question now:
If I use this ArrayList I can't access the objects directly. To do this I need to use a Hashtable. Any way to combine the get-element-by-id-feature of a Hashtable with the sorted functinallity from an ArrayList?

Commented:
A hashtable, by definition, isn't sorted. But could you tell us, what you are trying to achieve ? As things are right now, I think you want to do theList[name] to get the object, but theList has to be sorted as well ? Why does it need to be sorted, if you are fetching the items from it by their name ?

Or maybe I'm missing something ?

Commented:
By the way, I assume you know you can get an item from an ArrayList with theList[0]. This will get the object in the first position directly.

Commented:
I just keep on spamming, don't I.

If you really want to access the object by it's name, while still keeping it sorted, you should take a look at System.Collections.SortedList. This object works like a Hashtable if you look at the get-element-by-id part, but it also sorts all items by the keys of the objects. It should work for you.

Commented:
That sounds good. Will look into it too.

The reason for my question is about caching. I have a large list of objects I want to keep in the RAM of the server and access them fast. That's why I wanted to use Hashtables.

But in some cases I need to list all of them (or some) sorted by their name (or any other property they also have). That's why I was looking for this sort thing. Sure I could access all thos things sorted from the DB, but as mentioned I want to do all from the cache that I build.
Software Architect
CERTIFIED EXPERT
Commented:
Hi!

You can create your own collection object.
Inehriting from the CollectionBase will let you manage the way the collection behaves and most important it will let you sepcify the Item[index] return value type.
You can then apply the IComparer implementation as stated above.

Note 1:
myObject is a sample object I created for this demo...
it can be whatever you need... custom classes, strings, ints... whatever.

Note 2:
As you have your own collection object, you can create an overload of the default property to receive the string you're looking for instead of the index.

Sample code:

public class myObject
{
public string Name;
}

public class myCollection : System.Collections.CollectionBase
{

public void Remove(myObject item) { base.List.Remove(item); }
public myObject this[int index]
{
get { return ((myObject)base.List[index]); }
set { base.List[index] = value; }
}
public myObject this[string name]
{
get
{
return GetObjectByName(name);
}
set
{
// In this case the Set doesn't make much sence to me but you may
//  need to do something with it...
myObject obj = this.GetObjectByName(name);
obj = value;
}
}

private myObject GetObjectByName(string name)
{
if (name == null) return null;

myObject retval = null;
for (int i = 0; i < base.List.Count; i++)
{
if (this[i].Name == name) { retval = this[i]; break; }
}
return retval;
}

}

Alex :p

Not the solution you were looking for? Getting a personalized solution is easy.

Commented:
Cool. Sorry for a stupid question again... what is the better approach for my issue then? Using SortedList or creating an own collection object?

(Damn, I should be able to give away more than 500 pts!)

Commented:
Well, from an OO standpoint, you just gotta love AlexCode's method. Making your own collections is just cool ;)

But since you are using this stuff to get items fast, I wouldn't recommend his function, simply because it loops through each item and checks its Name property for the given name. I don't know how SortedList works internally, but I hope they came up with something better/faster than that.
Commented:
Alex's solution is a good one, so is the sorted list, or you could maintain an ArrayList of sorted names strings, and compliment it with a HashTable using the name as the key.

Use what you think is the simplest for you to maintain, as long as you can see ways to alter it in future without breaking your code. The sorted list works slower for inserts than a hashtable or unsorted ArrayList as it has to maintain the sort, but the same would be true of maintaining a sort on an ArrayList using BinarySearch. However, although the typed collection has the same effect as the sorted list, SortedList.Item/SortedList["name"] is fast O(log_2 n), and the typed collection search will be linear and slower i.e. O(n).

Are you going to be maintaing large lists (1000s of items) where performance is a problem? If not then just go for the SortedList, you can always go to your own object (typed collection) to implement fancy operations later on, once you have performance tested your code.

Andy

PS Divinity - its just another way of looking at it, and whether you use it or not depends on the predominant use of your ArrayList and so where your performance is going to be a problem. I think I picked the method up out of the OReilly C# cookbook.

Commented:
Divinity: I'm guessing that sorted list takes advantage of a binary search to return an item by index - that would make performance sense.
Software Architect
CERTIFIED EXPERT

Commented:

You have to choose...
SortedList isn't that fast either since it has to reorder the items on Add... but you also have to do that on this custom collection if you want an automated sortedlist... maybe a BubbleSort approach.

This depends on how many object you need to deal with.
With about 100 obejct it works fine... maybe more... you can teste it simply creating a loop to add items to a collection and then quering it.

You can also create a TypedDataSet and deal with a typed Table object.
The name of the objects will also be available thru intellisense and you can manage it, sort it and whatever as if it really was a DataBase object...

Alex :p

Commented:
For performance, I think a typed Dataset will be worse than all of the other options.
Software Architect
CERTIFIED EXPERT

Commented:

I never user Datasets... either kind...
They are slow and do too much work behind the scenes and are slow... slower than any other approach...

But I must admit that it makes certain things easier to accomplish (in-memory queries, sorts, links between objects, (de)serialization)...

The important thing is to have a good knowledge about either the tools the prog language provides and the need we have.

Alex :p

Commented:
True. Maybe a summary?

-IComparable and IComparer can be used to sort any object of a given type with respect to another object of the same type (or even a different type if you so wish to dig that hole).
-Sorted object - if they are .NET objects, such as ArrayList or SortedList, it's likely they will use the same mechanism behind the scenes to maintain the sort as you add objects. Therefore maintaining a sorted arraylist with your own BinarySearch is the same as adding an object to SortedList.
-Therfore, adding an item to a sorted object has an overhead, as underneath everything in the array frmo that point on needs to be shifted on one. Getting an item out is fast due to the BinarySearch that can be used to find an object.
-Unsorted objects (Hashtable) are fast to add objects to, but slower to get objects out of by name/non-numeric index than sorted objects.
-A sorted ArrayList + Hashtable is a poor man's solution, as you are maintaining a lot of objects by the time you get to the bottom of it all.
-SortedList will be slow to insert, fast to retrieve by name, therefore might be your best solution.
-Hashtable will be fast to insert, slower to retrieve by name. You can't sort it without extra objects (such as a sorted arraylist).
-Typed Collection based on CollectionBase will behave the same as a Hashtable, but it will be typed, and you can present a "sorted" facade to it, therefore is the best in terms of design patterns, but only necessary once you need extra performance or functionality you couldn't get out of a .NET object.
-Datasets are a RAD-based solution to typed collections, but are very heavyweight objects

And none of that really matters if you only have O(100) objects, so you decide.

I would say SortedList for you. Anyone else want to weigh in? One vote each only lol :-)

Andy
Software Architect
CERTIFIED EXPERT

Commented:

Facts & Problems regarding SortedList:

Facts 1:
SortedLists are based on HashTables... it's just a sortable HashTable.
HashTables items have 2 things: one key and one velue.

Fact 2:
The key is unique...
So you can't enter 2 keys with the same value.

Fact 3:
SortedList sorts based on the keys.

Problem 1:
On adding a new item to the SortedList collection we must specify 2 values (key & object) instead of simply giving 1 object.

Problem 2:
We can't have 2 objects that have the same value on the same property we want to sort by.

Problem 3:
The return value is always of type object... we always need to cast it.

-- // --

This is why I like the custom collection inherited from CollectionBase...
It's easier to maintain and behaves just like we want to.

If you're using the .net Framework 2.0 use the Generic Collections :))

Once again, if none of the problems I mentioned apply to you then use the SortedList, otherwise create a custom collection.

Alex :p

Commented:
Smoerble,

Did you have any luck with any of the ideas we posted? I know I would be interested to know how you got on, I'm sure the others would. :-)

Andy
Thanks for using Experts Exchange.

• View three pieces of content (articles, solutions, posts, and videos)
• Ask the experts questions (counted toward content limit)
• Customize your dashboard and profile