Sorting by Random.Next()

Question

In this question 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, which would obviously be safe

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?

Answer 1

this is basically a good way to randomize your list. it works, but is kinda haxor.

Answer 2

Just use a random shuffle.

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

Answer 3

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.

Answer 4

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.

Answer 5

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.)