CODEWITHSUNDEEP
c#unity-game-engine
morteza khosravi
morteza khosravi

Reputation: 1619

Sorting List with IComparer returns wrong result

I'm trying to sort a list but it does not sort the list right.

internal class GraphUtils{
    internal static List<Edge_t> kruskal2(List<Edge_t> e)
    {
       e.Sort(new KruskalComparer());
       printEdgeArray(e,e.Count);
       // Do stuff
    }
    static void printEdgeArray(List<Edge_t> e, int cnt)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < cnt; i++)
        {
            sb.Append(e[i].weight).Append(",");
        }
        ConsoleLog.Log(sb.ToString());
    }
}

internal class KruskalComparer : IComparer<Edge_t>
{
    public int Compare(Edge_t a, Edge_t b)
    {
        if (a.weight+TerrConstants.Eps > b.weight) return -1;
        if (a.weight < b.weight+TerrConstants.Eps) return 1;
        return 0;
    }
} 

class Edge_t
{
    internal Vertex_t V1;
    internal Vertex_t V2;
    internal float weight;
}

When kruskal2 is called, The sorted array is printed on console. But the result is wrong. It's not sorted by weight of Edge_t.

75.01,78.01,76.51,75.51,75.51,75.01,75.01,75.01,74.51,73.01,71.01,71.01,71.01,71.01,71.01,72.51,71.01,71.01,71.01,71.51,71.51,71.01,79.01,63.01,63.01,59.01,47.01,59.51,47.01,59.01,42.01,47.01,42.01,47.01,47.01,47.01,47.01,47.01,40.01,40.51,40.51,39.51,40.01,39.01,39.01,24.51,38.51,38.51,38.01,37.51,24.51,24.51,24.51,24.51,24.51,24.51,24.51,24.51,40.51,39.01,2.01,2.01,

I'm using Unity3d and the platform is mono 2.5.6.

Why is the result not sorted?

EDIT: TerrConstants.Eps is 1e-6f and it is added to the numbers to make some equality margin. so if the difference is less than TerrConstants.Eps*2 the two weights are considered as equals.

Upvotes: 1

Views: 77

Answers (1)

Ivan Leonenko
Ivan Leonenko

Reputation: 2383

It's probably something wrong with your eps constant. The following compare function should work.

if (Math.Abs(b.weight - a.weight) <= eps)
     return 0;
return b.weight.CompareTo(a.weight);

Upvotes: 1

Related Questions