Sorting by Random.Next()

In this qu开发者_Python百科estion one of the suggestions is to sort a list by Random.Next().

I assume (maybe incorrectly) he's suggesting this

    public static IEnumerable<T> RandomSort<T>(this IEnumerable<T> items)
    {
        Random r = new Random();
        var a = items.ToArray();
        Array.Sort(a, (t1, t2) => (r.Next()%2==0)?-1 : 1);
        return a;
    }

(Yes, there already is an Array.RandomShuffle function which you would obviously use instead. That's not the question)

EDIT: The poster has clarified the answer. He was suggesting the use of the OrderBy clause

The question is, is the above code (Using Array.Sort()) safe to run?

My issue is that it will be breaking a fundamental law of sorting predicates:

if (a < b) and (b < c) then (a < c)

It's not even guaranteeing that if (a < b) then ( a < b) the next time you ask.

Would this would take you into "undefined behaviour" territory?

For example, it could crash or fall into an infinite loop depending upon the sequence of numbers that Random() returns?

This is a useful device for creating a random permutation of the list. For a given permutation it is absolutely true that if a is before b and b is before c then a is before c.

Another way to think of it is like this: if you seed a random number generator with the same seed each time then it will always produce the same ordering. So you can think of every seed of the random number generator as producing a (possibly) different ordering of the list.

It's not even guaranteeing that if (a < b) then ( a < b) the next time you ask.

That's fine. But as explained above if we seed the random number generator with the same seed and present it to Array.Sort as in your sample code in the same state, it will produce the same ordering.

Just to make a quick observation, as I have just tried to do such a randomized sort using the following code (to get some basic unit tests to run in a random order):

Action<object>[] tests = new Action<object>[] {
    delegate { SearchStringByTree(SOURCE, distinctor.Keys, out treeResults, out treeTicks); },
    delegate { SearchStringByIndexOf(SOURCE, distinctor.Keys, out indexOfResults, out indexOfTicks); },
    delegate { SearchBinaryByTree(Encoding.UTF8.GetBytes(SOURCE), GetBytes(Encoding.UTF8, TERMS), out utf8Results, out utf8Ticks); },
    delegate { SearchBinaryByTree(Encoding.UTF8.GetBytes(SOURCE), GetBytes(Encoding.ASCII, TERMS), out asciiResults, out asciiTicks); }
};
Random r = new Random();
Array.Sort(tests, delegate { return r.Next(-1, 2); });

I randomly got the following ArgumentException:

IComparer (or the IComparable methods it relies upon) did not return zero 
when Array.Sort called x. CompareTo(x). x: ''  x's type: 'Action`1' 
The IComparer: 'System.Array+FunctorComparer`1[System.Action`1[System.Object]]'.

It seems Sort does asserts equality on items that it knows to be the same (assuming by object.ReferenceEquals) and, if the Comparer does not return 0 for those ones that it knows should be equal, it invalidates the entire sort.

Just use a random shuffle.

http://www.techtalkz.com/c-c-sharp/66613-shuffle-collection.html

the way it looks like it works is it's only asked once, then every subsequent query on that value it's the same.

it would be like adding an extra column to a table, filling each field with a random number, then ordering by that column.

You are correct that using a random number function for sorting is an easy way to break the formal requirements typically imposed on sorting functions, including the ones you mentioned.

The current implementation of LINQ seems to compute all of the sort keys up front. The following code demonstrates that the sort keys are obtained sequentially and exactly once. This is likely a wise implementation since it avoids the problematic scenarios you are worried about.

Nonetheless, I would not rely on this behavior (it is not documented in MSDN for Enumerable.OrderBy.

    public void Test()
    {
        int[] nums = Enumerable.Range(1, 100).ToArray();
        var sorted = from i in nums orderby Display(i) select i;
        sorted.ToArray();
    }

    private static int Display(int i)
    {
        Console.WriteLine(i);
        return i;
    }

(The above code prints 1 to 100 sequentially, showing how orderby evaluates the sort keys.)