*675*

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}elementHere 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.