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

Find the median of a sequence of n integers.

by nikoo28
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.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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