rselect Algorithm
The rselect Algorithm, also known as the Randomized Selection Algorithm, is an efficient algorithm for finding the ith smallest element in an unsorted array or list. This algorithm is based on the concept of divide and conquer and is an extension of the QuickSelect algorithm, which was developed by C.A.R Hoare. It uses random sampling to select a pivot element, which significantly reduces the average-case complexity compared to deterministic selection algorithms. The main advantage of the rselect Algorithm is its ability to find the desired element in linear time, with an average-case time complexity of O(n).
The working of the rselect Algorithm involves choosing a random pivot element from the unsorted array and partitioning the remaining elements into two groups - one with elements smaller than the pivot and the other with elements larger than the pivot. The pivot element's position in the sorted array is then determined, and based on this position, the algorithm either continues searching in the left partition, right partition, or returns the pivot element when it matches the desired position. The process is recursively repeated on the relevant partition until the ith smallest element is found. Due to the random selection of the pivot, the rselect Algorithm performs well on average, even though the worst-case scenario can still have a time complexity of O(n^2). However, the chances of encountering the worst-case scenario are significantly low, making the rselect Algorithm a popular choice for various applications.
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
void swap(int *a ,int *b)
{int t;t =*a;*a=*b;*b=t;}
int part(int a[],int l,int r,int n,int pivot,int pindex)
{int p1=l,p2=r;
while(p2>p1)
{
if (a[p1] > pivot && a[p2]<pivot)
{swap(&a[p1],&a[p2]);}
else
{
if (a[p1] <=pivot)
{p1++;}
if (a[p2]>=pivot)
{p2--;}
}
}
swap(&a[pindex],&a[p2]);
return p2;
}
int rselect(int a[],int l,int r,int n,int o)
{
int pivot,pindex,pactual;
if (r>l)
{
pindex = rand()%(r-l+1);
pivot = a[pindex];
pactual = part(a,l,r,n,pivot,pindex);
if (pactual == o)
{return a[pactual];}
if (o < pactual)
{rselect(a,l,pactual-1,n,o);}
if (o>pactual)
{rselect(a,pactual+1,r,n,o-pactual);}
}
if (r==l)
{return a[l];}
}
int main()
{srand(time(NULL));
int n,o,i,*a;
scanf("%d %d",&n,&o);
a = (int*)malloc(n*sizeof(int));
for (i=0;i<n;i++)
{scanf("%d",a+i);}
printf("\n\n%d",rselect(a,0,n-1,n,o));
return 0;
}
