How to randomize a sorted list?

Question

Here's a strange question for you guys,

I have a nice sorted list that I wish to randomize. How would i go about doing that?

In my application, i have a function that returns a list of points that describe the outline of a discretized object. Due to the way the problem is solved, the function returns a nice ordered list. i have a second boundary described in math and want to determine if the two objects intersect each other. I simply itterate over the points and determine if any one point is inside the mathematical boundary.

The method works well but i want to increase speed by randomizing the point data. Since it is likely that that my mathematical boundary will be overlapped by a series of points that are right beside each other, i think it would make sense to check a randomized list rather than iterating over a nice sorted one (as it only takes a single hit to declare an intersection).

So, any ideas on how i would go about randomizing an ordered list?

Answer 1

Use std::random_shuffle. If you want to implement the method yourself you should look at the Fisher-Yates shuffle.

Answer 2

You can try the random_shuffle algorithm, but note that it won't work on list since it requires random access iterators. You can use it on a vector or deque, though.

Answer 3

Assuming your "list" doesn't mean a linked list, but instead means something that supports random access (e.g., an array, std::vector, or std::deque), std::random_shuffle might be useful.