What is wrong with my sorting?

Question

First of all I have to specify that I'm working in Unity 5.3 and the new MonoDevelop doesn't allow me to debug. Unity just crashes :(

So I have a list of "goals" that I need to sort based on 3 criterias:

1. first should be listed the "active" goals
2. then ordered by difficulty level
3. finally randomly for goals of the same level

here is a my code:

public class Goal {
    public int ID;
    public int Level;
    public bool Active;
}

...

List<Goal> goals;

goals.Sort((a, b) => {
    // first chooses the Active ones (if any)
    var sort = b.Active.CompareTo(a.Active);
    if (sort == 0) {
        // then sort by level
        sort = (a.Level).CompareTo(b.Level);
        // if same level, randomize. Returns -1, 0 or 1
        return sort == 0 ? UnityEngine.Random.Range(-1, 2) : sort;
    } else {
        return sort;
    }
});

When I run this code sometimes I get one or more active goals after inactive ones, but I don't understand why.

Answer 1

To work correctly a sorting algorithm should not depend on mutating state. Explanation of why using a random generator while comparing values is not a good idea is given here.

The problem can be solved in two ways:

Option 1: Pre-compute random numbers

    var tmp = goals.Select( g=> new {goal = g, weight = rnd.NextDouble()})
        .OrderByDescending(t=>t.goal.Active) // Active first
        .ThenBy(t=>t.goal.Level)
        .ThenBy(t=>t.weight)
        .Select(t=>t.goal)
        .ToList();



    goals.Clear();
    goals.AddRange(tmp);

Working sample

Option 2: Sort then shuffle ties

Random rnd = new Random();

Comparison<Goal> comparison =  (a, b) => {
// first chooses the Active ones (if any)
var sort = b.Active.CompareTo(a.Active);

if (sort == 0) {
// then sort by level
    return sort = (a.Level).CompareTo(b.Level);
  } else 
{
   return sort;
}
};



int startIndex = 0;
int endIndex = 0;

goals.Sort(comparison);

while (startIndex < goals.Count)
{
    for (endIndex = startIndex + 1; endIndex < goals.Count; ++endIndex)
    {
       if (comparison(goals[startIndex], goals[endIndex]) != 0)
       {
          //End of tie
          break;
       }
    }

    if (endIndex - startIndex > 1)
    {
       // Shuffle goals of the same level
       ShuffleRange(goals, startIndex, endIndex - startIndex, rnd);
    }

    startIndex = endIndex;
}   

static void ShuffleRange<T>(List<T> list, int startIndex, int count, Random rnd)
{
     int n = startIndex + count;  
     while (n > startIndex + 1) 
     {  
        int k = rnd.Next(startIndex, n--);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}           

Working sample

Shuffle algorithm is borrowed from here

Answer 2

Try this lambda:

(a, b) => ((b.Active ? 1000 : 0) + b.Level) - ((a.Active ? 1000 : 0) + a.Level)

Active is 1000 times more important than a level difference of 1. This works for up to 1000 levels. When Active is the same, the level becomes relevant. Finally, if it still is the same it will be ordered in a deterministic but irrelevant manner, which is the same as random.

There's no need to use a true random number. The order will always be the same during one run, but it may differ between runs. If you really need a random order you can use this:

(a, b) =>
    ((b.Active ? 10000 : 0) + b.Level * 10) -
    ((a.Active ? 10000 : 0) + a.Level * 10) + UnityEngine.Random.Range(-1, 2)

Answer 3

I can't reproduce your issue of getting "one or more active goals after inactive ones". It sounds like your Goal instances are being mutated after the sort. I would suggest trying to make read-only objects where possible.

My other suggestion is to simplify you sort code to make it clearer and easier to reason about - although that's probably not going to directly help in this case.

Just do this sort:

var sorted =
(
    from g in goals
    orderby g.Active descending, g.Level, UnityEngine.Random.Range(-1, 2)
    select g
.ToList();

...or alternatively and equivalently like this:

var sorted =
    goals
        .OrderByDescending(g => g.Active)
        .ThenBy(g => g.Level)
        .ThenBy(g => rnd.Next())
        .ToList();

LINQ sorts work fine with a random source. I've done the distribution analysis on it and it works just as well as fisher-yates.