Problem with custom IComparer for List (sort) - c#

Question

Hi,

can anyone help, i have problem doing a sort, I thought i had it sorted but appears not to be working.

I have a List which stores the following values

8,6,10,11,7

I also have another List (accessories in my class and it has a propert called accessoryId current the classes are in the order of id which is currenty 6,7,8,10,11)

Hence i need to sort them from 6,7,8,10,11 to the order used from the simple list which is 8,6,10,11,7

I have my icomparable (see below) and i am calling like this - it does enter but something is wrong BECAUSE the list still has all my classes but is still in the order of 6,7,8,10,11

   // accesories is the IList<Accessories> (hence why i am use ToList)
   // and sortOrder is the simple int list list<int>
   accesories.ToList().Sort(new ItemTpComparer(sortOrder));  

class ItemTpComparer : IComparer<Accessories>
{
    private IList<int> otherList;

    public ItemTpComparer(IList<int> otherList)
    {
        this.otherList = otherList;
    }

    #region IComparer<Accessories> Members

    public int Compare(Accessories x, Accessories y)
    {

        if (otherList.IndexOf(x.AccessoryId) > otherList.IndexOf(y.AccessoryId))
            return 1;

        else if (otherList.IndexOf(x.AccessoryId) < otherList.IndexOf(y.AccessoryId))
            return -1;
        else
            return 0;

        // tried below also didn't work
        //return otherList.IndexOf(x.AccessoryId) - otherList.IndexOf(y.AccessoryId);

Answer 1

The comparer is correct (even the commented single line version). The problem is ToList() creates a new List containing a copy of elements in the IEnumerable<T> object so basically, you are creating a new list, sorting it and throwing it away.

var sortedList = accesories.ToList();
sortedList.Sort(new ItemTpComparer(sortOrder)); 

for which I'd suggest replacing with:

var sortedList = accessories.OrderBy(sortOrder.IndexOf).ToList();

this way, no comparer implementation would be necessary. You could also sort in the descending order easily:

var sortedList = accessories.OrderByDescending(sortOrder.IndexOf).ToList();

If the object is really List<Accessories>, you could also sort it in place:

((List<Accessories>)accessories).Sort(new ItemTpComparer(sortOrder));

Answer 2

Mehrdad showed you why the list was not sorted. I want to address the performance of the comparer, and also the issue with less sorting items than sorted items.

Using IndexOf on a list to locate the index is quite inefficient. I has to loop through the items in the list to find the right one. Use a dictionary as lookup instead, that way you only loop through the items once:

class ItemTpComparer : IComparer<Accessories> {

   private Dictionary<int, int> index;

   public ItemTpComparer(IList<int> otherList) {
      index = new Dictionary<int, int>();
      for (int i = 0; i < otherList.Count; i++) {
         index.Add(otherList[i], i);
      }
   }

   public int Compare(Accessories x, Accessories y) {
      return index[x.AccessoryId].CompareTo(index[y.AccessoryId]);
   }

}

If you want to allow the list of value to sort by to be shorter than the list of items to sort, you check if the value exists in the dictionary:

   public int Compare(Accessories x, Accessories y) {
      int xIndex, yIndex;
      if (!index.TryGetValue(x.AccessoryId, out xIndex)) xIndex = int.MaxValue;
      if (!index.TryGetValue(y.AccessoryId, out yIndex)) yIndex = int.MaxValue;
      return xIndex.CompareTo(yIndex);
   }