Sign in to follow this  
matthughson

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

Recommended Posts

matthughson    588
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
Mike.Popoloski    3258
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
AEtheReal    100
If you do not mind making the structure a bit bigger, the solution is easy.

Store the original index of each element. In the compare function, in case of a tie, compare the original index.

Share this post


Link to post
Share on other sites
Promit    13246
For a stable alternative to Quick Sort, what you really want is Merge sort. In fact, merge sort has a bunch of neat properties.

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