| 62 | namespace math |
| 63 | { |
| 64 | double averages::median(std::span<const double> data) |
| 65 | { |
| 66 | // The median of an odd number of elements is the value |
| 67 | // that appears in the middle position of these elements when they are sorted. |
| 68 | // The median of an even number of elements is typically |
| 69 | // defined as the mean of the two middle elements in a sorted range. |
| 70 | |
| 71 | // We cannot sort the data span itself, because it's elements are const. |
| 72 | // Therefore, we first copy the const input data to be able to sort it |
| 73 | std::vector<double> sorted; |
| 74 | |
| 75 | // Use range-based for loop to copy the input data. |
| 76 | // See Chapter 20 for built-in means of copying a data range. |
| 77 | for (auto value : data) |
| 78 | sorted.push_back(value); |
| 79 | |
| 80 | // See Chapter 20 for built-in means of (partially) sorting data |
| 81 | quicksort(sorted); |
| 82 | |
| 83 | const size_t mid = data.size() / 2; |
| 84 | return data.empty() ? std::numeric_limits<double>::quiet_NaN() // Or std::nan |
| 85 | : data.size() % 2 == 1 ? sorted[mid] |
| 86 | : (sorted[mid - 1] + sorted[mid]) / 2; |
| 87 | } |
| 88 | } |
| 89 | |
| 90 | void quicksort(std::vector<double>& data, size_t start, size_t end); |