unsigned long partitionArray(int arr[], unsigned long left, unsigned long right)
{
unsigned long pivot = (rand() % (right - left + 1)) + left;
SWAP(arr[left], arr[pivot]);
unsigned long i = left + 1;
for(unsigned long j = left + 1; j <= right; ++j)
{
if(arr[j] < arr[left])
{
swap(arr[j], arr[i]);
++i;
}
}
swap(arr[i-1], arr[left]);
return i-1;
}
int RSelect(int arr[], int left, int right, int n)
{
if(left == right && left == n)
return arr[left];
int pivotIndex = partitionArray(arr, left ,right);
if(pivotIndex + 1 == n)
return arr[pivotIndex];
else if(pivotIndex + 1 > n)
return RSelect(arr, left, pivotIndex - 1, n);
else
return RSelect(arr, pivotIndex + 1, right, n);
}
{
unsigned long pivot = (rand() % (right - left + 1)) + left;
SWAP(arr[left], arr[pivot]);
unsigned long i = left + 1;
for(unsigned long j = left + 1; j <= right; ++j)
{
if(arr[j] < arr[left])
{
swap(arr[j], arr[i]);
++i;
}
}
swap(arr[i-1], arr[left]);
return i-1;
}
int RSelect(int arr[], int left, int right, int n)
{
if(left == right && left == n)
return arr[left];
int pivotIndex = partitionArray(arr, left ,right);
if(pivotIndex + 1 == n)
return arr[pivotIndex];
else if(pivotIndex + 1 > n)
return RSelect(arr, left, pivotIndex - 1, n);
else
return RSelect(arr, pivotIndex + 1, right, n);
}