java program Someone proposes an algorithm to find the median of a series of N n
ID: 3585026 • Letter: J
Question
java program
Someone proposes an algorithm to find the median of a series of N numbers (all different and given in a random order) contained in a simple array, where N is an odd number For example, if N-5 and the numbers in the array are 13,2,7,4,3 the median is 4 (the "middle" element) The idea of this programmer is to go over each number and to find how many numbers in the array are smaller than this one. You do this for every number until you find one for which there are exactly (N-1)/2 smaller numbers; at this point you may stop and this number is the median A) (15 pt) Give a pseudo-code description of the algorithm described above B) (15 pt) Give a big-h complexity for the best-case and for the worst-case running time (of course, give the tightest big-Oh you can for each case). Justify your answersExplanation / Answer
public class Median {
static int find_Median(int a[])//method to find median in a given array of integers
{
int n=a.length;
int i=0,c=0,j;
while(i<n)//for each element in a
{
c=0;
j=0;
while(j<n)
{
if(a[j]<a[i])//counting number of elements less than a[i]
c++;
j++;
}
if(c==(n-1)/2)//number of smaller elements equals to (n-1)/2
return a[i];//returning median
i++;
}
return -1;//if number of elements in a are zero..
}
//complexity
//best case : O(n)// means first element is meadian...where inner for loop runs n times for it..
//worst case : O(n^2)//last element is meadian...inner for loop must run for all elements..
public static void main(String argv[])
{
int a[] = {13,2,7,4,3};
System.out.println("Median is : "+find_Median(a));
}
}
OUTPUT:
run:
Median is : 4
BUILD SUCCESSFUL (total time: 0 seconds)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.