CODEWITHSUNDEEP
c++randomtheory
Faken
Faken

Reputation: 11822

How to randomize a sorted list?

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?

Upvotes: 6

Views: 13439

Answers (6)

pmr
pmr

Reputation: 59841

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

Upvotes: 12

olegarch
olegarch

Reputation: 3891

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;
}

Upvotes: 1

Jay
Jay

Reputation: 27512

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.

Upvotes: 1

Jerry Coffin
Jerry Coffin

Reputation: 490728

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.

Upvotes: 1

Viktor Sehr
Viktor Sehr

Reputation: 13119

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

Upvotes: -2

Fred Larson
Fred Larson

Reputation: 62123

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.

Upvotes: 4

Related Questions