Array shuffle algorithm
What are some of the creative ways to do an array shuffle in place ?
Say for eg. , you have an array like arr[] = {3, 7, 9, -1, 0, 2} and jumbled sequence of indices as indices[] = {2, 1, 0, 4, 5, 3}.
Shuffle array in place without using additional memory with index 0 replaced by 2, 1 by 1, 2 by 0, 3 by 4 and so on ?
This question was asked in facebook interview.
goli202084 Answered question
Algorithm in C language:-
#include <stdio.h> int main() { int indices[] = {2, 1, 0, 4, 5, 3}, array[] = {3, 7, 9, -1, 0, 2}, i = 0, length = sizeof(array) / sizeof(int), sum=0, x = 0, y = length - 1; for (i = 0; i < length/2; i++) { if (y == x){ sum += array[x]; } else if(y - x == 1) { sum += array[x++] + array[y--]; break; } sum += array[x++] + array[y--]; } for (i = 0; i < length; i++) { printf("%d ", sum - (sum - array[indices[i]])); } return 0; }
goli202084 Answered question