Home Arrays Find the median of a sequence of n integers.

# Find the median of a sequence of n integers.

0 comment

Question: Given a sequence of integers, find the median of the integers?

Input: arr [] = {15, 23, 4, 16, 8, 42}. Find median.
Output: 15

Since the question does not specify anything we cannot assume that the given array is a sorted one. The definition of median is the (n/2)th element of a sorted sequence of integers.
This definition makes our approach simpler. All we need to do is sort the integers and then return the (n/2)th element.
Here is the code for above approach. I use quick sort to sort the array.

#include<stdio.h>

void swap(int *i, int *j) {
int temp = *i;
*i = *j;
*j = temp;
}

int partition(int arr[], int start, int end) {
int pivot = arr[end];
int i = start, j = end-1;
while(i<=j) {
while(arr[i]<pivot)    i++;
while(arr[j]>pivot)    j--;
if(i<=j) {
swap(&arr[i],&arr[j]);
i++;
j--;
}
}
swap(&arr[i],&arr[end]);
return i;
}

void performQuickSort(int arr[], int start, int end) {
if(start<end) {
int p = partition(arr, start, end);
performQuickSort(arr, start, p-1);
performQuickSort(arr, p+1, end);
}
}

void quickSort(int arr[], int size) {
performQuickSort(arr, 0, size-1);
}

// driver program to find median
int main(void)
{
int i;
int arr[6] = {15, 23, 4, 16, 8, 42};
int size = 6;

quickSort(arr,size);

printf("Median:- %d",arr[size/2]);

return 0;
}


Time Complexity:- O (n*log (n)) due to quick sort.

#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More