I need help fixing this sorting method

Unity Engine
1

Hello guys,

I have a problem with this sorting function, lets say I have an inventory and it sorts a list of Creatures based on the stars of a creature and this method works perfectly.

private static int SortByAverageStarRating(Creature o1, Creature o2) {
        return o2.averageStarRating - o1.averageStarRating;
    }

But let’s say I have creatures with 2 star rating side to side ( same value which is a 2 ), every time I call this method they would swap themselves, and I don’t want this to happen. I want it sort when its higher or greater, but when they are compared against the same value you do nothing. I tried to make these changes but was unable to get it to work properly.

Too be honest I don’t even know how this code snippet even works on the list using the return and comparison, otherwise I would be able to solve it myself.

Any help would be greatly appreciated!

2

It sounds like you want to use a “stable” sorting algorithm.

You can find more info on it by looking at this:

Or over here:

A salient point is found on that page:

“Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.”

I would guess you are using Quick Sort, which is why you are seeing instability - because Quick Sort is not stable.

Can you show us your call to “sort”? Maybe there is an easy way to tell it to be stable?

3

Thanks for the insight!

I sort it by:

creatureList.Sort(SortByAverageStarRating);

Currently I just set bool flags in my game logic where I determine if i need to sort or not, but that is mostly just fixing the bug and not the real problem. My flag method doesn’t solve the problem where when I need to sort, it will still just swap anything equal.

4

Is there another property in the Creature class you could use to break ties?

Then, maybe you could change it to something like:

private static int SortByAverageStarRating(Creature o1, Creature o2) {

   if (o2.averageStarRating == o1.averageStarRating)
   {
      // break the tie using other property
      return o2.otherProperty - o1.otherProperty;
   }
   else
      return o2.averageStarRating - o1.averageStarRating;
}
5

No there isn’t another property to break ties sadly.

6

Try using the linq OrderBy() method instead of sort. OrderBy is a stable sort.

7

You could always add a field called something like “index”.

Then, before a sort:

int creatureCtr = 0;
foreach (Creature creature in creatureList) {
    creature.index = creatureCtr++;
}

Then, the sort function would be like this:

private static int SortByAverageStarRating(Creature o1, Creature o2) {

   if (o2.averageStarRating == o1.averageStarRating)
   {
      // break the tie using index property
      return o2.index - o1.index;
   }
   else
      return o2.averageStarRating - o1.averageStarRating;
}

Also, there are probably ways to avoid all that initializing right before a sort. For instance, you may be able to number the creatures as they are created or maybe even use timestamps.

Also, if you don’t want to do all that, you might be able to do an insertion sort as described here:

http://www.csharp411.com/c-stable-sort/

Also, I suspect the linq approach is viable also, but I have never used LINQ.

8

Thanks I will do this :slight_smile: