Sign in to follow this  
matthughson

[.net] [C#] List.Sort is Non-Deterministic?

Recommended Posts

Hi, I am trying to use a custom sort delegate with my List in C#. It seems that the result is not deterministic, in that I have a list of items, all with equal values, but the order of the list is different every time I call the Sort method. I call the sort function like so:
mGameObjects.Sort(CompareByRenderPriority);
Here is my implementation of the sort:
// Used to sort the game objects based on render priority.  We want the higher
// priority (which is a smaller number) to appear later on the list.
//
private static int CompareByRenderPriority(GameObject x, GameObject y)
{
    // For testing I just return 0 every time, indicating that the
    // 2 items are equal.
    return 0;
}
Is there a way to tell the list not to change the order of items have the same value? Thanks!

Share this post


Link to post
Share on other sites
From the documentation:

Quote:
This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.


It's easy enough to whip up your own sorting method though. It's a well-researched field:


static class ListExtensions
{
public static void InsertionSort<T>(this IList<T> list, Comparison<T> comparison)
{
if (list == null)
throw new ArgumentNullException("list");
if (comparison == null)
throw new ArgumentNullException("comparison");

for (int j = 1; j < list.Count; j++)
{
T key = list[j];
int i = j - 1;

while (i >= 0 && comparison(list[i], key) > 0)
{
list[i + 1] = list[i];
i--;
}

list[i + 1] = key;
}
}
}



In use:
mGameObjects.InsertionSort(CompareByRenderPriority);

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this