Problems sorting arraylist Compareto

Unity Engine
1

I’m trying to sort some objects in a list based on an int value, but when two objects have the same values, they sometimes switch place in the list. I need them to stay in the same place. I make a new sort every time something is added to the list, because the values might have changed.

private List<QueUnit> Que = new List<QueUnit>();
//Code to fill the list
Que.Sort((a,b) => a.getWait().CompareTo(b.getWait()));

Potential output of idNumbers when no values are changed:
1
1,2
2,1,3
1,2,3,4
2,1,3,4,5
1,2,3,4,5,6

2

Not sure why they would switch places… but basically the sorting works like this:

A comparer is used (in this case, it’s comparing probably two integers) and it returns a value.

1 means “object a” is greater than “object b”
-1 means "object a is less than “object b”
and 0 means they are the same. The Sort method might be transposing them for some reason if they are the same. You can create your own comparer like so:

public class QueUnitComparer: IComparer<QueUnit>
{
    public int Compare(QueUnit a, QueUnit b)
    {
        var waitA = a.getWait();
        var waitB = b.getWait();
 
        if(waitA > waitB)
        {
             return 1;
        }

        return -1;
         
     }
}

What this will do is return that A is greater than B when it is… otherwise it ALWAYS assumes that A is less than B (even when they are equal) and it won’t affect sorting.

Now you can change your code to this:

private List<QueUnit> Que = new List<QueUnit>();

//Code to fill the list
Que.Sort(new QueUnitComparer());

This will use your comparer to do the comparison for you. It’s actually an IComparer with your custom compare method.

Also, you’re using a “Generic List”, not an “ArrayList”.

3

error CS0308: The non-generic type `System.Collections.IComparer’ cannot be used with the type arguments

I know, I thought I used an ArrayList, and forgot to change the title.

4

I should have coded it up instead of just mocking it up in the post… let me replicate your objects and rewrite this for you.

5

Ok… can you post your code? I think what you’re doing is this:

QueUnitComparer : IComparer

but it needs to be:

QueUnitComparer : IComparer

What is the DataType being returned by getWait? Also, you may be better avoiding the method call if all getWait is doing is returning the value of a property and do something like:

private int _wait;

public int Wait
{
    public get { return _wait; }
    private set { _wait = value; }
}

This will allow you to expose the property getter without exposing the setter and you’ll avoid the overhead of throwing another methodcall onto the stack. Then you can change everywhere you use “unit.getWait()” to just “unit.Wait”

Now for the code, here is the QueUnit I mocked up to test with:

namespace UnityTests
{
    public class QueUnit
	{
		public int Wait;
		public int getWait()
	    {
		    return Wait;
	    }
    }
}

And I implemented the IComparer with the following… you should be able to copy this code (everything inside the Namespace brackets) and it will work:

using System.Collections.Generic;

namespace UnityTests
{
	public class QueUnitComparer : IComparer<QueUnit>
	{
		public int Compare(QueUnit a, QueUnit b)
		{
			var waitA = a.getWait();
			var waitB = b.getWait();

			if (waitA > waitB)
				return 1;

			return -1;
		}
	}
}

Now here is the test that I used. It is the “Progam.cs” if a Console app, but you could copy everything inside the Main method and use it (except for the Console.WriteLine stuff):

using System;
using System.Collections.Generic;
using UnityTests;

namespace TestConsole
{
	class Program
	{
		static void Main(string[] args)
		{
			var list = new List<QueUnit>();
			var rnd = new Random();

			for (var i = 0; i < 100; i++)
			{
				list.Add(new QueUnit { Wait = rnd.Next(0, 9999)});
			}

			list.Sort(new QueUnitComparer());

			foreach (var q in list)
			{
				Console.WriteLine(q.getWait());
			}

			Console.ReadKey();
		}
	}
}

How here’s something to keep in mind… I’m not sure how often or where all you’re doing the sorting. This method of sorting will actually physically re-order your list. You could also use LINQ like this:

foreach(var unit  in unitList.OrderBy(q => q.getWait())
{
   //Output your stuff
}

This will actually just get an enumerator over your collection and allow you to access it in order without physically re-ordering the list. There are pros and cons to each approach. One is physically reordering the lists which will cause fluctuations in memory allocation as it creates a new list comprised of the values from the old one, but then again you’re only sorting it when you absolutely need to. The second method (using LINQ) only creates an enumerator, but you could potentially be doing that sorting over and over and over. You could also add .ToList() to the end of your OrderBy and it will give the physically reordered list:

   unitList = unitList.OrderBy(q => q.getWait()).ToList();

This does essentially the same as Sort but may still reorder equal values (I’m not sure if this behavior should actually be happening).

6

As an answer to why items get reordered, .Sort uses an implementation of Quicksort. Quicksort is a fast, general sorting algorithm…but it is generally not a stable sorting algorithm. The implementation used by .Sort is documented as being an unstable implementation.

Edit: .OrderBy uses a stable sorting algorithm, so objects will remain in place if two sort to the same value.

7

That’s what I was wondering but wasn’t 100% sure. So .Sort is using a non-deterministic algorithm to do the shorting (this is the Quicksort) but LINQ does not use Quicksort. In this case the best thing to do would be to just use LINQ to do the sorting and make a call to ToList() afterwards to persist it (see my very last code sample). Then you don’t have to worry about the IComparer.

8

Thinking about it further, it’s also probably important to note that different sorting algorithms yield different performance depending on the makeup of your data. The sort algorithms baked into .NET are pretty general purpose sorts. If your list is already sorted though, you might want to look at something like a bubble sort or insertion sort which both work considerable well on mostly sorted data. You could create extension methods for List that allow you to do these sorts.

Another thing though, if your list is already sorted, you might just want to insert at the appropriate index. Let’s say you have a list of 1000 QueUnit objects. You create a new QueUnit object. You’ll want to find the index of the first QueUnit whose getWait() value is larger than your new one, and that is where you’ll want to insert it. If none are found, then you just add it to the end of the list. At most, you’ll compare the value to all 1000 existing QueUnit objects, but you may only ever do one comparison (to the first one). So you would do the following:

var qu = new QueUnit {Wait = rnd.Next(0, 9999)};
var nextBiggest = list.FirstOrDefault(q => q.getWait() > qu.getWait());

if (nextBiggest != null)
{
	list.Insert(list.IndexOf(nextBiggest), qu);
}
else
{
	list.Add(qu);
}

In this case, “list” is our List from above and it’s already been sorted once. If you are using this insert method, you can make sure that the item is always ordered. In fact, here is the code you would need to create the extension method to do this for you:

using System.Collections.Generic;
using System.Linq;

namespace UnityTests
{
	public static class ListQueUnitExtensions
	{
		public static void InsertOrdered(this List<QueUnit> list, QueUnit newUnit)
		{
			var nextBiggest = list.FirstOrDefault(q => q.Wait > newUnit.Wait);

			if (nextBiggest != null)
			{
				list.Insert(list.IndexOf(nextBiggest), newUnit);
			}
			else
			{
				list.Add(newUnit);
			}
		}
	}
}

Now in the original code you just do this:

for (var i = 0; i < 100; i++)
{
	var qu = new QueUnit {Wait = rnd.Next(0, 9999)};
	list.InsertOrdered(qu);
}

This will use your extension method to make sure that the QueUnit objects are ALWAYS inserted in order. So you would never have to do a sort if you always used this method for adding to your List

9

Wikipedia has a good comparison table, including memory use (which can be of concern with allocations that the GC has to clean up).

10

Thanks for the help, I got it to work now. It works exactly like it should.
The getWait() function does more things then just return a variable, there’s some calculations and some other functions it has. And I have to sort every time, because the wait might change for the items between every insert, so 2 items might have to swap places.

It’s hard to explain everything, but I believe this is the best way to do it, and I only sort maybe once a minute or something like that.