Validation, stored observations, and the median

A running sum can calculate a mean, but it cannot recover the order needed for a median. This lab stores accepted observations, keeps a truthful active count, sorts the active values when needed, and checks the odd- and even-count cases separately.

Review CS1: active array counts, CS1: sorting, and CS1: a complete statistics program. The important connection is that input validation, storage, sorting, and statistics must all describe the same observations.

Accept a complete observation before storing it #

The observation here is a percentage change calculated from a valid pair of positive indexes. Establish the validity of both inputs first. If one is invalid, do not calculate a rate from a partly accepted pair or increase the stored count.

A calculation function can have the precondition that the old and new indexes are positive. The input stage is responsible for meeting that requirement. If parsing fails, a value retained from an earlier iteration must not silently stand in for the failed new input.

A decline between two positive indexes is a valid negative rate. Unchanged positive indexes produce a valid zero rate. Decide validity from the input contract, not from whether the resulting rate is positive. This matters for both the eventual mean and the order used for the median.

Preserve the meaning of used #

A fixed array has storage capacity. The variable used records how many meaningful rates have been stored. At zero used, there are no observations even if the allocated slots were initialized to zero. Those zero bytes are not accepted zero-percent observations.

When room remains, store one accepted rate at index used, then increase used once. If used equals capacity, another append needs a defined outcome rather than a write beyond the array. Every statistic visits only indexes below used.^[1]

For example, after accepting rates eight, two, and six, used is three and the active values are [8, 2, 6]. A rejected pair afterward must leave both that sequence and used unchanged. The program should not create a blank-looking fourth observation and later average it.

Sort a copy or disclose the change #

The median refers to ordered values. Sorting the active observations gives [2, 6, 8]. The count remains three: sorting changes order, not membership or size.

A function that sorts the original array has a side effect. Its contract should say that the caller's active elements will be rearranged. If the original chronological order is needed later, copy the active values and sort the copy. Passing a built-in array parameter does not itself copy the complete array.

Only the active range should be sorted. Sorting all capacity can mix unused slots into the observations. Even if every unused element currently contains zero, moving those values into the front changes the dataset that later processing would read.

Work out the odd-count position #

For a nonempty odd count n, the zero-based middle position is n / 2 using integer division. With n equal to three, this index is one. The sorted sequence two, six, eight has six at index one, with one observation on each side, so the median is six.

Do not use the human phrase 'second element' as an index of two. The second element has index one. The count, the ordinal position, and the subscript are different ways of talking about the same layout.

A single observation also works: one divided by two using integer division is zero, so the only element supplies the median. An empty collection has no middle position and must be handled separately before indexing.

Work out the even-count pair #

For an even nonzero count, the middle indexes are n / 2 - 1 and n divided by two. For [8, 2, 6, 4], sorting gives [2, 4, 6, 8]. The count is four, so the middle indexes are one and two. Their values are four and six, giving a median of five.

Use floating-point division when averaging the two middle observations. A fractional median is legitimate; integer division would discard it. For general large values, the arithmetic types and range of the sum also need to be suitable: converting after an overflowing integer addition would not repair that addition.

The median is not necessarily one of the original observations in the even case. That is expected. The mean, by contrast, uses every observation's contribution to the sum, whether or not it lies near the middle.

Build tests with an expected state #

For each test, predict used, the active sequence after storage, the sorted sequence, and the median before running. Use an odd count, an even count, one value, repeated values, an already sorted sequence, and reverse order. If empty input is allowed, check its separately defined response.

Test the full-capacity boundary and one extra attempted append. The extra observation must either be rejected under the stated policy or handled by an explicit expansion strategy. It must not disappear into an out-of-bounds write. Also verify that rejection of an input pair never consumes a slot.

Practice and explanation #

Suppose four active observations sort to minus five, zero, two, and eight. The middle indexes are one and two, holding zero and two; the median is one. The negative and zero observations remain valid members of the dataset.

If capacity is ten but used is four, which count determines those indexes? Four. Capacity describes available room, not the number of observations that define the statistic.