Comparison method for sorting that shuffles equal elements randomly

Question

Here's a puzzle for you.

I want to change the following comparison method, so that when two items are considered equal, they will be shuffled randomly.

myList.Sort( (x, y) => x.Score.CompareTo(y.Score) );

I could imagine that this scenario would be useful when ordering search results if you didn't want to give preference to one result over another when their scores are the same.

Anyone want to give it a go?

Here was my first attempt at a solution, but it doesn't work. I'll let you figure out why.

class RandomizeWhenEqualComparer<T> : IComparer<T>
{
 private readonly Func<T, T, int> _comparer;

 public int Compare(T x, T y)
 {
            if (x.Equals(y)) return 0;

     int result = _comparer(x, y);

     if (result != 0) return result;

     double random = StaticRandom.NextDouble();
     return (random < .5) ? -1 : 1;
 }

 public RandomizeWhenEqualComparer(Func<T, T, int> comparer)
 {
  _comparer = comparer;
 }
}

Answer 1

The problem is that the result of comparison is not reproduceable along the sort. The sort algorithm can invoke the comparison method many times for a given pair of elements and the comparison method should return the same value each time.

You could store the result of each comparison involving the random shuffle and look them up when the comparison method is invoked again for the corresponding pair.

Answer 2

First shuffle it randomly, then use a stable sort.

Answer 3

If you only control the sorting method then you are severely limited since you do not know which sorting algorithm it will be used in. You'd have to keep the randomized results of any comparison between equal key values and look any new comparison between equal values up in the table to ensure the same, stable result in any single sorting run, like Sharptooth said.

Not strictly a comparison method, but what about a quicksort algorithm where you randomize into which subdivision any value with key equal to the pivot value goes? The recursive subdivision would randomly place some equal values on the left and some on the right.

Answer 4

You could, as sharptooth said, store the result for each comparison and look them up again.

But that's no fun, and it increases the time complexity and space complexity since you have to store the previous comparisons and search them every time you make a comparison.

So here's what I'd do: At the beginning of the search, get a random seed. Then write a function that creates a hash based on both a T and the seed.

public int Hash(T a, int s)
{
    // e.g.
    return Random( a.Name().ToInt() + s ).NextDouble();
}

public int Compare(T x, T y, int s)
{
    if (x.Equals(y)) return 0;

    int result = _comparer(x, y);

    if (result != 0) return result;

    return (Hash(x, s) < Hash(y, s) ) ? -1 : 1;
}

This will be stable within a given sort, but doesn't require a lookup table.