CODEWITHSUNDEEP
carraysalgorithmcuda
Ciel
Ciel

Reputation: 6281

Move items to the front of an array

I have items in the centre of an array and I want to move them to the front of this array. For example:

array[8] = {10, 38, 38, 0, 8, 39, 10, 22}

and I have an index array

index[6] = {0, 3, 4, 6, 7, 1}

and I want to move these 6 items to the front of the array

result[8] = {10, 0, 8, 10, 22, 38, 38, 39}

Actually the order doesn't matter, just make sure the item whose index is in the index array should always before the item whose index is not in the index array.

Can anyone give me a fast algorithm? Actually this is one step in an KNN problem, the data array could be very large. The algorithm should run as fast as possible and the extra space needed should be as small as possible. It is better if you can give me CUDA implementation.

Update: Compare to the data array, the size of the index array is very small. In my case, it is only about 200.

Update: Please note that the size of the data array could be very very very large! It goes to 1M, 10M even higher(The data array is loaded to GPU memory which is quite limited). Any algorithm needs a temp array which has the same size with data array is not acceptable.

Upvotes: 1

Views: 1598

Answers (3)

rkp
rkp

Reputation: 13

Approach 1

You can modify insertion sort to solve your problem which will eventually give you O(n^2) time complexity. But if you want to keep run time in order of N then you can use following approach.

Approach 2

Here we can use index array as auxiliary space as follows :

step 1

store all actual values instead of indexes in index table(array) and replace the value array with negative/non accepting value.

Value Array

[ -1, -1, 38, -1, -1, 39, -1, -1 ]

Index Array

[ 10, 0, 8, 10, 22, 38 ]

complexity in this operation is O(n)

step 2

shift all the remaining at last which will take O(n) time complexity.

Value Array ###

[ -1, -1, -1, -1, -1, -1, 38, 39 ]

Index Array

[ 10, 0, 8, 10, 22, 38 ]

step 3

not put the element from index array to value array.

Value Array

[ 10, 0, 8, 10, 22, 38, 38, 39 ]

Index Array

[ 10, 0, 8, 10, 22, 38 ]

time complexity for this operation is O(n)

Total run time complexity for this approach : O(n)

Improvement

Here in this approach you are not able to preserve your index array. While you can preserve it using O(index array size) space complexity OR with the condition that value array does not contain any non negative values then while keeping -1/non accepting value in it you can use storing index with -ve and in third step you can recover your index array as it is.

Upvotes: 0

Pham Trung
Pham Trung

Reputation: 11284

Sort the index array in increasing order, this step will make sure that we will not make any unnecessary swap.

Starting from 0 to n - 1 (n is the length of array index), swap the ith element in the array with index[i]th element.

Pseudo Code

sort(index);

 for(int i = 0; i < index.length; i++){
     swap(array, i , index[i]);
 }

If you don't want to sort index, we can always find the smallest element in the index array which is not at the beginning of the array. (as the size of index is small)

Use an boolean used to mark which position in the array index is already put at the correct position.

Pseudocode:

bool []used = //

 for(int i = 0; i < index.length; i++){
     int nxt = -1;
     for(int j = 0; j < index.length; j++){
        if(!used[j]){
           if(nxt == -1 || index[j] < index[nxt]){
              nxt = j;
           }
        }
     }
     used[nxt] = true;
     swap(array, i, nxt);
 }

Upvotes: 1

michael-tkach
michael-tkach

Reputation: 259

const int ARRAY_SIZE = sizeof(array) / sizeof(array[0]);
const int INDEX_SIZE = sizeof(index) / sizeof(index[0]);

bool used[ARRAY_SIZE] = {};

for (int i = 0; i < INDEX_SIZE; ++i)
{
    int id = index[i];
    result[i] = array[id];
    used[id] = 1;
}

for (int i = 0, id = INDEX_SIZE; i < ARRAY_SIZE; ++i)
{
    if (!used[i])
    {
        result[id] = array[i];
        ++id;
    }
}

Upvotes: 0

Related Questions