Median of n numbers
Algorithm
Randmized select(a,p,r,i)
1. If(p=r) then
Return a[p];
2. q=randomized partition(a,p,r)
k=q-p+1;
3. if (i=k)then
return a[q];
4. else if (i<k)then
return randmized select(a,p q-1,i);
5. else
return randomized select (a,q+1,r,i-k)
randomized partition(a,p,r)
1 x=a[r];
2 i=p-1;
3 for j=p to r-1
4 do
if (a[j]<=x) then
i=i+1;
exchange a[i+1] and a[j];
5 end of for loop.
6 Exchange a[i+1] and a[r];
7 Return i+1;
Algorithm Description
Randomized select() function takes 4 parameter a:an array, p:starting point of array,r:end point of array, I:gives ith smallest no. from the array 1. if(p=r) means only one element in the array then median is that no. itself. 2. Described below 3-5 K is the position of the pivot element .pivot :element in the array From which all left side elements are small and all right side elements are large; If ith? element is pivot element itself then it return the a[q]; If ith element less then pivot element then same search will perform on the left part of the array. Else (i-k)th element will be search on the right part of the array. Randomized partition() This function takes 3 parameter a:name of the array, p:starting position of the array, r: last position of the array. This function divide array in two parts and gives the position of the pivot element; 1. Take last element as a pivot element. 3-5. These steps shift all elements less then the pivot element one side. 6 this step place the pivot element on the right place.
C Code
/* Find median */
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
# define MAX 100
int n,coord[MAX],beg=0,end=0;
/* this function is partition function which finds location of pivot*/
int partition(int coord[], int beg,int end)
{
int low,pivot,ra,temp,j;
pivot=coord[end];
low=beg-1;
for(j=beg;j<end;j++)
{
if(coord[j]<=pivot)
{
low=low+1;
temp=coord[low];
coord[low]=coord[j];
}
}
temp=coord[low+1];
coord[low+1]=coord[end];
coord[end]=temp;
return low+1;
}
/* function that check whether desired location elemnt is found or not*/
int select(int coord[],int beg, int end, int i)
{
int q,k;
if(beg==end)
return coord[beg];
q=partition(coord,beg,end);
k=q-beg+1;
if(i==k)
return coord[q];
else if (i<k)
return select(coord,beg,q-1,i);
else
return select(coord,q+1,end,i-k);
}
int main()
{
int cordx[MAX],actual_med,i,result=0,n,result1=0;
float cal;
printf("Total numbers: ");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("enter the number %d ",i);
scanf("%d",&coord[i]);
}
if (n%2==0)
{
actual_med=n/2;
result=select(coord,1,n,actual_med);
result1=select(coord,1,n,actual_med+1);
cal=(result+result1)*0.5;
printf("median is %0.2f ",cal);
}
else
{
actual_med=(n+1)/2;
result=select(coord,1,n,actual_med);
printf("median is %d ",result);
}
return 0;
}
