View more

View more

View more

### Image of the Day Submit

IOTD | Top Screenshots

### The latest, straight to your Inbox.

Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.

# Algorithm for certain permutaion of array elements (parallel sorting by regular sampling)

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

4 replies to this topic

### #1Misery  Members

Posted 11 July 2013 - 01:07 AM

I am implementing a parallel sorting by regular sampling algorithm which is described here. I am stuck in a point at which I need to migrate sorted sublists to proper places of the sorted array. The problem can be stated in that way: There is one global array. The array has been divided into p subarrays.Each of those subarrays was sorted. p-1 global pivot elements were determined and each sub-array was divided into p sub-sub arrays (yellow, red, green). Now I need to move those sub-sub-arrays so that sub-sub-arrays with local index i are in the thread i (so they are ordered in such manner at which colors are neighbouring and the order from left to right remains).

Actually serial algorithm will do, but I just have no clever idea how to obtain a proper permutation. The following figure shows a case for p=3 threads. Yellow color denotes a sub-sub-array 0, red - 1, green - 2.

The sub-sub arrays may have different sizes.

Edited by Misery, 11 July 2013 - 01:07 AM.

### #2Norman Barrows  Members

Posted 11 July 2013 - 12:13 PM

perhaps something like:

for CurrentSubSubArray = 0 to 2

for CurrentThread = 0 to 2

if Element[CurrentGlobalIndex].SubSubArray == CurrentSubSubArray

CopyToNewArray()

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

### #3Álvaro  Members

Posted 11 July 2013 - 12:28 PM

This seems straight forward enough:

#include <iostream>

int color[27] = {0, 0, 0, 1, 1, 2, 2, 2, 2, 0, 0, 1, 1, 1, 1, 1, 2, 2, 0, 1, 1, 2, 2, 2, 2, 2, 2};

int main() {
int counters[3] = {0};
for (int i=0; i<27; ++i)
counters[color[i]]++;

int indices[3];
int accumulator = 0;
for (int i=0; i<3; ++i) {
indices[i] = accumulator;
accumulator += counters[i];
}

int permutation[27];
for (int i=0; i<27; ++i)
permutation[indices[color[i]]++] = i;

for (int i=0; i<27; ++i)
std::cout << permutation[i] << ' ';
std::cout << '\n';
}

### #4Misery  Members

Posted 13 July 2013 - 05:32 AM

Well, the problem is that processed amounts of data are huge so I need not to copy whole data. If i'll think of something clever i'll post it here.

### #5Álvaro  Members

Posted 13 July 2013 - 11:49 AM

My code doesn't copy any data... Perhaps you can describe your requirements better, but my code does just about the minimal amount of work required, given what I understood you are trying to do.

Old topic!

Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.