Program that finds the median of list of numbers whose size is taken to be 10000000. It also prints out the total number of swaps(fundamental operation involved) to prove linear time complexity.

Median.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 1000000

int getMedian();
int count=0;

void swap();
void main(int argc,char *argv[])
{
int i=0;
int a[SIZE];
int n=SIZE;
int k;

srand(time(NULL));




for(i=0;i<n;i++)
 a[i] = rand()%SIZE;

if(n%2==0)
printf("The median is %f\n",((float)getMedian(a,0,n-1,n/2-1)+ (float)getMedian(a,0,n-1,n/2))/2 );
else
printf("%d",getMedian(a,0,n-1,n/2));


printf("Number of swaps made is %d\n",count);
}


int getMedian(int a[], int low,int high,int k)
{

int i;
int part = low;

if(low >= high)
return a[low];

for(i=low+1;i<=high;i++)
{
if(a[i]<a[low])
swap(a,i,++part);
}
swap(a,part,low);

if(part>k)
return getMedian(a,low,part-1,k);
else if(part<k)
return getMedian(a,part+1,high,k);
else if(part==k)
return a[part];
}

void swap(int a[],int i,int j)
{
count++;
int temp=a[i];
a[i] = a[j];
a[j] = temp;
}