How to resolve the algorithm Averages/Median step by step in the EMal programming language
How to resolve the algorithm Averages/Median step by step in the EMal programming language
Table of Contents
Problem Statement
Write a program to find the median value of a vector of floating-point numbers. The program need not handle the case where the vector is empty, but must handle the case where there are an even number of elements. In that case, return the average of the two middle values. There are several approaches to this. One is to sort the elements, and then pick the element(s) in the middle. Sorting would take at least O(n logn). Another approach would be to build a priority queue from the elements, and then extract half of the elements to get to the middle element(s). This would also take O(n logn). The best solution is to use the selection algorithm to find the median in O(n) time. Quickselect_algorithm
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Averages/Median step by step in the EMal programming language
Source code in the emal programming language
fun median = real by some real values
values = values.sort()
int mid = values.length / 2
return when(values.length % 2 == 0, (values[mid] + values[mid - 1]) / 2.0, values[mid])
end
writeLine(median(4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2, 5.0))
fun median = real by some real values
fun swap = void by int a, int b
real t = values[a]
values[a] = values[b]
values[b] = t
end
fun select = real by int k
int left = 0
int right = values.length - 1
while left < right
real pivot = values[k]
swap(k, right)
int pos = left
for int i = left; i < right; i++
if values[i] < pivot
swap(i, pos)
++pos
end
end
swap(right, pos)
if pos == k do break
else if pos < k do left = pos + 1
else do right = pos - 1 end
end
return values[k]
end
int halfLength = values.length / 2
return when(values.length % 2 == 0,
(select(halfLength) + select(halfLength - 1)) / 2.0,
select(halfLength))
end
writeLine(median(4.1, 5.6, 7.2, 1.7, 9.3, 4.4, 3.2, 5.0))
You may also check:How to resolve the algorithm Knuth shuffle step by step in the SparForte programming language
You may also check:How to resolve the algorithm Command-line arguments step by step in the NetRexx programming language
You may also check:How to resolve the algorithm Linear congruential generator step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Vector products step by step in the Swift programming language
You may also check:How to resolve the algorithm Loops/While step by step in the Fortress programming language