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

Started by
4 comments, last by Promit 14 years, 1 month ago
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!
__________________________________[ Website ] [ Résumé ] [ [email=contact[at]matthughson[dot]com]Contact[/email] ][ Have I been Helpful? Hook me up! ]
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 = list<span style="font-weight:bold;">;<br>                i–;<br>            }<br><br>            list = key;<br>        }<br>    }<br>}<br><br></pre></div><!–ENDSCRIPT–><br><br>In use:<br><tt>mGameObjects.InsertionSort(CompareByRenderPriority);</tt>
Mike Popoloski | Journal | SlimDX
Thanks, Mike.
__________________________________[ Website ] [ Résumé ] [ [email=contact[at]matthughson[dot]com]Contact[/email] ][ Have I been Helpful? Hook me up! ]
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.
You might also consider using the LINQ OrderBy method. MSDN says that it is stable sort.
For a stable alternative to Quick Sort, what you really want is Merge sort. In fact, merge sort has a bunch of neat properties.
SlimDX | Ventspace Blog | Twitter | Diverse teams make better games. I am currently hiring capable C++ engine developers in Baltimore, MD.

This topic is closed to new replies.

Advertisement