write a subroutine named \"median\" which will sort an array of integers so that
ID: 3674523 • Letter: W
Question
write a subroutine named "median" which will sort an array of integers so that the resulting values will appear from smallest to largest then find the statistical median, which is the center item in the list. If the list has an even number of items, then the median is the average of the two items closest to the center of the list. the subroutine will expect to be passed the address of an array of type "int" and one integer representing the number of items in the array to sort. You may use any sort algorithm you want.
Explanation / Answer
Hi below i have written the algorithm and implementation for better understanding for your problem,
This method works by first getting medians of the two sorted arrays and then comparing them.
Let ar1 and ar2 be the input arrays.
Algorithm:
Example:
For above two arrays m1 = 15 and m2 = 17
For the above ar1[] and ar2[], m1 is smaller than m2. So median is present in one of the following two subarrays.
Let us repeat the process for above two subarrays:
m1 is greater than m2. So the subarrays become
Implementation:
#include<stdio.h>
int max(int, int); /* to get maximum of two integers */
int min(int, int); /* to get minimum of two integeres */
int median(int [], int); /* to get median of a sorted array */
/* This function returns median of ar1[] and ar2[].
Assumptions in this function:
Both ar1[] and ar2[] are sorted arrays
Both have n elements */
int getMedian(int ar1[], int ar2[], int n)
{
int m1; /* For median of ar1 */
int m2; /* For median of ar2 */
/* return -1 for invalid input */
if (n <= 0)
return -1;
if (n == 1)
return (ar1[0] + ar2[0])/2;
if (n == 2)
return (max(ar1[0], ar2[0]) + min(ar1[1], ar2[1])) / 2;
m1 = median(ar1, n); /* get the median of the first array */
m2 = median(ar2, n); /* get the median of the second array */
/* If medians are equal then return either m1 or m2 */
if (m1 == m2)
return m1;
/* if m1 < m2 then median must exist in ar1[m1....] and ar2[....m2] */
if (m1 < m2)
{
if (n % 2 == 0)
return getMedian(ar1 + n/2 - 1, ar2, n - n/2 +1);
else
return getMedian(ar1 + n/2, ar2, n - n/2);
}
/* if m1 > m2 then median must exist in ar1[....m1] and ar2[m2...] */
else
{
if (n % 2 == 0)
return getMedian(ar2 + n/2 - 1, ar1, n - n/2 + 1);
else
return getMedian(ar2 + n/2, ar1, n - n/2);
}
}
/* Function to get median of a sorted array */
int median(int arr[], int n)
{
if (n%2 == 0)
return (arr[n/2] + arr[n/2-1])/2;
else
return arr[n/2];
}
/* Driver program to test above function */
int main()
{
int ar1[] = {1, 2, 3, 6};
int ar2[] = {4, 6, 8, 10};
int n1 = sizeof(ar1)/sizeof(ar1[0]);
int n2 = sizeof(ar2)/sizeof(ar2[0]);
if (n1 == n2)
printf("Median is %d", getMedian(ar1, ar2, n1));
else
printf("Doesn't work for arrays of unequal size");
getchar();
return 0;
}
/* Utility functions */
int max(int x, int y)
{
return x > y? x : y;
}
int min(int x, int y)
{
return x > y? y : x;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.