What is wrong with my sorting?

Question

First of all, I have to indicate that I am working in Unity 5.3, and the new MonoDevelop does not allow me to debug. Unity just crashes :(

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

• “Active” goals should be indicated first.
• then sorted by difficulty level
• randomly for one level goals

here is 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, the sorting algorithm should not depend on the state of the mutation. An explanation of why using a random generator when comparing values ​​is not a good idea is given here .

The problem can be solved in two ways:

Option 1: Precomputing 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 example

Option 2: Sort and then shuffle links

 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 example

Shuffle algorithm borrowed from here

Answer 2

Try this lambda:

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

Active 1000 times more important than the difference of levels 1. It works up to 1000 levels. When the same is active, the level becomes relevant. Finally, if it is the same anyway, it will be ordered in a deterministic but inappropriate way, which is the same as random.

There is no need to use a true random number. Within one run, the order will always be the same, but it may differ in different 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 cannot reproduce your problem of getting "one or more active goals after inactive". It appears that your Goal instances mutate after sorting. I would suggest trying to make read-only objects where possible.

My other suggestion is to simplify the sort code to make it more understandable and understandable - although this probably won't help in this case.

Just do this type:

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

... or alternatively and equivalently:

 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 did a distribution analysis on it, and it works as well as fishermen-yates.