Error while sorting with IComparer

[awiklund]

Hi,

I am sorting an arrayList using a custom comparer, but it sort the
element in a uncommon fashion.

Take a look at this code.

using System;

namespace ConsoleApplication8
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class Class1
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
try
{
System.Collections.ArrayList list = new
System.Collections.ArrayList();
list.Add(new Test(1, 10));
list.Add(new Test(1, 12));
foreach(Test item in list)
{
System.Console.Write("Before: " + item.index + " -
" + item.value);
System.Console.Write("\n");
}
list.Sort(new MyComparer());
foreach(Test item in list)
{
System.Console.Write("After: " + item.index + " -
" + item.value);
System.Console.Write("\n");
}
foreach(Test item in list)
{
System.Console.Write("Before: " + item.index + " -
" + item.value);
System.Console.Write("\n");
}
list.Sort(new MyComparer());
foreach(Test item in list)
{
System.Console.Write("After: " + item.index + " -
" + item.value);
System.Console.Write("\n");
}

}
catch(Exception ex)
{
Console.WriteLine(ex.ToString());
}
Console.ReadLine();

}
}

public class Test
{
public int index = 0;
public int @value = 0;
public Test(int i, int j)
{
index = i;
@value = j;
}
}

public class MyComparer: System.Collections.IComparer
{
#region IComparer Members

public int Compare(object x, object y)
{
int result = 0;
Test dataX = x as Test;
Test dataY = y as Test;


if(dataX.index < dataY.index)
{
result = -1;
}
else if(dataX.index > dataY.index)
{
result = 1;
}

return result;
}

#endregion
}

This should noramlly give the output:
Before: 1 - 10
Before: 1 - 12
After: 1 - 10
After: 1 - 12
Before: 1 - 10
Before: 1 - 12
After: 1 - 10
After: 1 - 12

But the output is this:

Before: 1 - 10
Before: 1 - 12
After: 1 - 12
After: 1 - 10
Before: 1 - 12
Before: 1 - 10
After: 1 - 10
After: 1 - 12

WHen to items have the same index it switches these items in each sort
sequence. Am I doing somthing wrong? I cant find any documentation on
the action taken when 0 (zero) is returned by the IComparer.

I cannot alter the code to return -1 each time two values are equals
since a check is done (x and y is the same object, and this must
return 0 (zero)). One way to fix this is to do like this; but I see
this as a hack and a time consuming workaround. Any thoughts?

if(dataX == dataY)
{

}
else if(dataX.index <= dataY.index)
{
result = -1;
}
else if(dataX.index > dataY.index)
{
result = 1;
}


Regards
awiklund

 

[Chris R. Timmons]

(e-mail address removed) (awiklund) wrote in

WHen to items have the same index it switches these items in
each sort sequence. Am I doing somthing wrong? I cant find any
documentation on the action taken when 0 (zero) is returned by
the IComparer.

awiklund,

When ArrayList.Sort() sees two equal indexes, it does not know that
it is "wrong" to switch them. Internally, ArrayList.Sort() uses a
recursive QuickSort implementation, which often swaps equal values.
I don't know of any way to tell ArrayList.Sort() to not perform this
swapping.

To prevent this behavior, you can:

1. Add extra logic in MyComparer.Compare() check the objects' @value
member when an equal index is found.

or

2. Write a custom sort method that does not swap equal values to use
instead of ArrayList.Sort().

 

[Ignacio Machin \( .NET/ C# MVP \)]

Hi,

I just posted a class for doing this, take a look at a thread named
"Sorting DataGrid bound to collection"

cheers,

--
Ignacio Machin,
ignacio.machin AT dot.state.fl.us
Florida Department Of Transportation

Hi,

I am sorting an arrayList using a custom comparer, but it sort the
element in a uncommon fashion.

Take a look at this code.

using System;

namespace ConsoleApplication8
{
/// <summary>
/// Summary description for Class1.
/// </summary>
class Class1
{
/// <summary>
/// The main entry point for the application.
/// </summary>
[STAThread]
static void Main(string[] args)
{
try
{
System.Collections.ArrayList list = new
System.Collections.ArrayList();
list.Add(new Test(1, 10));
list.Add(new Test(1, 12));
foreach(Test item in list)
{
System.Console.Write("Before: " + item.index + " -
" + item.value);
System.Console.Write("\n");
}
list.Sort(new MyComparer());
foreach(Test item in list)
{
System.Console.Write("After: " + item.index + " -
" + item.value);
System.Console.Write("\n");
}
foreach(Test item in list)
{
System.Console.Write("Before: " + item.index + " -
" + item.value);
System.Console.Write("\n");
}
list.Sort(new MyComparer());
foreach(Test item in list)
{
System.Console.Write("After: " + item.index + " -
" + item.value);
System.Console.Write("\n");
}

}
catch(Exception ex)
{
Console.WriteLine(ex.ToString());
}
Console.ReadLine();

}
}

public class Test
{
public int index = 0;
public int @value = 0;
public Test(int i, int j)
{
index = i;
@value = j;
}
}

public class MyComparer: System.Collections.IComparer
{
#region IComparer Members

public int Compare(object x, object y)
{
int result = 0;
Test dataX = x as Test;
Test dataY = y as Test;


if(dataX.index < dataY.index)
{
result = -1;
}
else if(dataX.index > dataY.index)
{
result = 1;
}

return result;
}

#endregion
}

This should noramlly give the output:
Before: 1 - 10
Before: 1 - 12
After: 1 - 10
After: 1 - 12
Before: 1 - 10
Before: 1 - 12
After: 1 - 10
After: 1 - 12

But the output is this:

Before: 1 - 10
Before: 1 - 12
After: 1 - 12
After: 1 - 10
Before: 1 - 12
Before: 1 - 10
After: 1 - 10
After: 1 - 12

WHen to items have the same index it switches these items in each sort
sequence. Am I doing somthing wrong? I cant find any documentation on
the action taken when 0 (zero) is returned by the IComparer.

I cannot alter the code to return -1 each time two values are equals
since a check is done (x and y is the same object, and this must
return 0 (zero)). One way to fix this is to do like this; but I see
this as a hack and a time consuming workaround. Any thoughts?

if(dataX == dataY)
{

}
else if(dataX.index <= dataY.index)
{
result = -1;
}
else if(dataX.index > dataY.index)
{
result = 1;
}


Regards
awiklund