Trying to adjust a findlargest algorithm to a find median in a unique set of num
ID: 3637656 • Letter: T
Question
Trying to adjust a findlargest algorithm to a find median in a unique set of numbers. Use the FindLargest algorithm (below) to develop an algorithm to find the median value in a list of n unique numbers. Median is defined as the value in the list in which approximately half the values are larger than it and half the values are smaller.2. Find the Median Algorithm
Get the value for n, the size of the list
Get values for A1, A2, ….., An, the list to be searched
Set the value of largest so far to A1
Set A1 as complete, move to last location
Set the value of i to 2
While (i<=n) do
If Ai > largest so far, not marked as complete
Set largest so far to Ai
Set Ai as complete, move to last location
Add 1 to the value of i
End of Loop
print out the valuesof the largest so far and location
stop
How can I revise this into one for finding a median in unique set?
Explanation / Answer
By the de?nition, the median of a list is largest than approximately half the
numbers. When N is odd, this median has to be smaller than N-1/2 numbers; otherwise, it has to be smaller than N/2 numbers. Thus, the idea is to apply the FindLargest algorithm enough
times to ?nd all the numbers greater than the median, according to either N is even or odd;
then apply the FindLargest one more time to ?nd the next largest one, which is the median.
Then the algorithm should look like the following:
1. Get the values for N and a list of N numbers
2. If N is odd Set m to (N/2)
3. Else Set m to N/2-1
4. Set i to 1
5. While i <= m Repeat Steps 6 and 7
6. Call FindLargest
7. Increment i by 1
8. Call FindLarest one more time
9. Set Median to the current value of Largest
10. Print out the value of Median
11. Stop