Jump to content
  • Advertisement
Sign in to follow this  
matthughson

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

This topic is 3039 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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, key) > 0)
{
list[i + 1] = list;
i--;
}

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



In use:
mGameObjects.InsertionSort(CompareByRenderPriority);

Share this post


Link to post
Share on other sites
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
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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!