int RANDOMIZED_SELECT(A,p,r,i)
{ int q,k;
if(p==r)return A[p];
q=RANDOMIZED_PARTITION(A,p,r);
k=q-p+1;
if(i==k)return A[q];
else if(i<k)
then return RANDOMIZED_SELECT(A,p,q-1,i);
else return RANDOMIZED_SELECT(A,q+1,r,i-k);
}

int RANDOMIZED_PARTITION(A,p,r)
{int i,t;
i=RANDM(p,r);
t=A[r];A[r]=A[i];A[i]=t;
return PARTITION(A,p,r);
}
int PARTITION(A,p,r)
{int x,i,j;
x=A[r];
i=p-1;
for(j=p;i<=r-1;j++)
{
if(A[j]<=x){ i=i+1;t=A[i];A[i]=A[j];A[j]=t;}
}
t=A[i+1];A[i+1]=A[r];A[r]=t;
return i+1;
}

#include<stdio.h>
#include<stdlib.h>
#define NUM 1000
Void main()
{
int A[NUM],i,s=0;
printf(" the length of array A[]\n");
scanf("%d",&s);
for(i=1; i<=s; i++)
scanf("%d",&A[i]);
r=s;p=1;
RANDOMIZED_SELECT(A,p,r,i);
for(i=1; i<=s; i++)
printf("A[i]=%d\t",A[i]);
}