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

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 2

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

Answer 3

std::random_shuffle(thelist.begin(), thelist.end());

Answer 4

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.

Answer 5

But a key question would be whether the runtime required to randomize the list might not be more than the runtime to traverse it sequentially.

Perhaps what you really need to do is not actually randomize it, but rather read it in some order other than front to back. For example, if the list has n members, perhaps you should process 1, n, 2, n-1, 3, n-2, etc. or 1, n/2, 2, n/2 + 1, 3, n/2 +2, etc.

If you always have the same number of points or if the number of points falls into a small finite set, you could produce an order of point evaluation for each possible number of points once in advance, either truly random or perhaps carefully calculated in some way.

Answer 6

int array[N];

for(int i = N - 1; i > 0; i--) {
  int j = rand() % i;
  int tmp = array[i]; array[i] = array[j]; array[j] = i;
}