One more easy one. I want to “sort” a list into a random, shuffled order. I can do that by simply randomizing whether any two elements are greater than, less than, or equal to each other:
myList.Sort((x, y) => (new Random()).Next(-1, 2));
That generates a random -1, 0 or 1 for every comparison, right? So it will sort the list into random order, right?
There are multiple defects here. First off, clearly this violates all our rules for comparison functions. It does not produce a total ordering, and in fact it can tell you that two particular elements are equal and then later tell you that they have become unequal. The sort algorithm is allowed to go into infinite loops or crash horribly when given such an ill-behaved comparison function. And in fact, some implementations of sorting algorithms attempt to detect this error and will throw an exception if they determine that the comparison is inconsistent over time.
Second, every time this thing is called it creates a new
Random instance seeded to the current time, and therefore it produces the same result over and over again if called multiple times in the same timeslice; hardly random.
Shuffling is not sorting; it is the opposite of sorting, so don’t use a sort algorithm to shuffle. There are lots of efficient shuffle algorithms that are easy to implement. (That said, it is legal to shuffle by sorting a list ordered by a randomly chosen key. But the key must be chosen exactly once for each item in the list and there must be a correct comparison function on that key.)
Pingback: Bad comparisons, part three | Fabulous adventures in coding
Does the following have any unexpected sideeffects?
var rnd = new Random();
var SortedItems = SomeItems.OrderBy(item => rnd.NextDouble());
There is a proper comparison function for doubles, but the implementation might call the selector multiple times for the same item. Is this actually the case in this implementation?
How would you randomize a list of items?