CareerCup

I think divide and conquer will work for this problem.

My Approach would be

#1
for(1 to N)
{
random=generate a random no b/w 1 and N ;
swap element 1 and element random ;
}
Complexity O(n)

for(i=0;i<=N,i++)
{
replaceIndex=i+random()*(N-1);
//.... replace element with (N-i)th index with replaceIndex
}

This is Kenneth algorithm which is most of the time used for shuffling.

#include<stdio.h>
void swap(int *a,int x)
{
int temp=a[x];
a[x]=a[x-1];
a[x-1]=temp;
}
void suffle(int *a,int n)
{
int i,j,mid,k;
mid=n/2;
for(i=0;i<mid-1;i++)
{
j=i;
k=0;
while(k<=i)
{
swap(a,mid+j);
j=j-2;
k++;
}
}
}
main()
{
int a[]={1,2,3,4,5,6,7,8,9,10},i;
printf("before \n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
suffle(a,10);
printf("\nafter \n");
for(i=0;i<10;i++)
printf("%d ",a[i]);
return 0;
}

int myRandomNumber()
{
int temp_id=0;
unsigned int myseed;
myseed = (unsigned)time(NULL);
srand(myseed); // Initialize the random number generator
temp_id = rand(); // Random number
return temp_id;
}
by seeding u will get a truly random number..

- generate this numer twice per swap..

random1 = myRandomNumber();
random2 = myRandomNumber();

swap(a[random1], a[random2]);

for(i=list.size()-1;i>=0;i--)
{
int r=rand()%i;
swap(list[r],list[i]);
}