Reorder an array at a given index

Question

Algoritham reorder array according to given index a[] = [50, 40, 70, 60, 90] index[] = [3, 0, 4, 1, 2] a= [60,50,90,40,70] 

in O (n) and without additional arrays / spaces

Answer 1

You will need a place for a temporary variable and loop / index counters. The usual "order" according to the algorithm will also change the index [] back to {0, 1, 2, 3, 4}.

Hint, noting the order of indexes in the index [].

  {0, 1, 2, 3, 4} index[] = {3, 0, 4, 1, 2} 

Reordering can be performed by following "cycles". Start with index [0] and pay attention to "loops" if you look at index [0], then at index [index [0]], etc ...

 // 1st cycle index[0] == 3 // cycle starts at 0 index[3] == 1 index[1] == 0 // end of cycle since back at 0 // 2nd cycle index[2] == 4 // cycle starts at 2 index[4] == 2 // end of cycle since back at 2 

C code example:

 #include <stdio.h> static int A[] = {50, 40, 70, 60, 90}; static int I[] = {3, 0, 4, 1, 2}; int main() { int i, j, k; int tA; /* reorder A according to I */ /* every move puts an element into place */ /* time complexity is O(n) */ for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){ if(i != I[i]){ tA = A[i]; j = i; while(i != (k = I[j])){ A[j] = A[k]; I[j] = j; j = k; } A[j] = tA; I[j] = j; } } for(i = 0; i < sizeof(A)/sizeof(A[0]); i++) printf("%d\n", A[i]); return 0; } 

The same algorithm, but uses swaps instead of moves (this is a slower method).

 #include <stdio.h> #define swap(a, b) {(a)^=(b); (b)^=(a); (a)^=(b);} static int A[] = {50, 40, 70, 60, 90}; static int I[] = {3, 0, 4, 1, 2}; int main() { int i, j, k; /* reorder A according to I */ /* every swap puts an element into place */ /* last swap of a cycle puts both elements into place */ /* time complexity is O(n) */ for(i = 0; i < sizeof(A)/sizeof(A[0]); i++){ if(i != I[i]){ j = i; while(i != (k = I[j])){ swap(A[j], A[k]); I[j] = j; j = k; } I[j] = j; } } for(i = 0; i < sizeof(A)/sizeof(A[0]); i++) printf("%d\n", A[i]); return 0; }