Arrays Enter the Lab

Every program so far has worked on a handful of named variables. Week 10 needs a collection: N numbers read into an array, then processed by loops that walk it. The three programs are chapter 7 in lab form. Mean, variance, and standard deviation need two passes over the data, which is the reason the numbers must be stored at all. Bubble sort rearranges the array in place. Linear search walks it looking for a key. All three share the same opening: a capacity fixed at compile time, a count N read and checked against it, and a guarded loop that fills the array.

Program 1: Mean, Variance, and Standard Deviation

For N values, the mean is their sum divided by N, the variance is the mean of the squared distances from the mean, and the standard deviation is the square root of the variance.

Algorithm:

  1. Start.
  2. Read N; if it is below 1 or above the capacity, print a message and stop.
  3. Read N values into an array, adding each to a running sum.
  4. mean = sum / N.
  5. For each value, add (value − mean)² to a running total; variance = that total / N.
  6. Standard deviation = √variance.
  7. Print the three results.
  8. Stop.

Type 8 and then 2 4 4 4 5 5 7 9: the mean is 5, the variance 4, the standard deviation 2, the example every statistics textbook opens with. The program cannot compute the variance until it knows the mean, and it cannot know the mean until it has seen every value, so the values have to be kept: that is the whole case for the array. The first loop reads and sums, the second measures distances from the mean it just computed.

The range check on N is not decoration. values has room for 100 numbers, and a read loop that trusted N would write past the end of the array for N of 101, which is undefined behaviour and which the sandbox's AddressSanitizer stops on the spot. Checking N against CAPACITY before the loop is the chapter 7 habit, and the #define is what lets the check and the declaration agree by construction.

This is the population variance, dividing by N, which is what the syllabus's textbook uses. The sample variance divides by N − 1, and a viva examiner may ask which one you wrote and why; the honest answer is that N is the definition for a complete data set and N − 1 is the estimate when the data is a sample of a larger one. Either way the program's structure is the same, and the division is the only line that changes.

Program 2: Bubble Sort

Read N integers, sort them into ascending order, and print the array before and after under headings.

Algorithm:

  1. Start.
  2. Read N and the N values, with the same checks as before.
  3. Print the array under the heading "given array".
  4. For i from 0 to N − 2: for j from 0 to N − 2 − i, if values[j] > values[j + 1], swap them.
  5. Print the array under the heading "sorted array".
  6. Stop.

Type 5 and then 5 1 4 2 8. The chapter 7 algorithm lesson explained the mechanism: each pass of the inner loop compares neighbours and swaps any pair out of order, so the largest value left floats to the end, and the next pass can stop one place earlier, which is the - i in the inner bound. The - 1 in the same bound is what keeps values[j + 1] inside the filled part of the array on the last comparison. Drop it and the final comparison reads values[n], a slot no input was ever stored in: reading an indeterminate value is undefined behaviour, and here it quietly sorts a stray 0 into the output. With N at the array's full capacity the same read leaves the array altogether and AddressSanitizer stops the run.

Two lab-record habits are in the output. The heading is printed first with no trailing space, and every element is printed with a space before it, which produces given array: 5 1 4 2 8 with no space at the end of the line and no special case for the first element. And the array is printed twice by two identical loops rather than once, because the sort changes it in place and the "given" version is gone once the sort has run; if you want to print it afterwards, you need a copy.

The exam question that follows this program is the trace: write the array after each pass of the outer loop. For 5 1 4 2 8 the passes give 1 4 2 5 8, then 1 2 4 5 8, and the remaining passes change nothing. A version that notices a pass with no swaps and stops early is a common improvement and worth mentioning; the plain version is what the syllabus asks for.

Program 3: Linear Search

Read N integers and a key, and report where the key is or that it is absent.

Algorithm:

  1. Start.
  2. Read N and the N values, then the key, with the same checks.
  3. Set found to −1.
  4. For i from 0 to N − 1: if values[i] equals the key, set found to i and stop looking.
  5. If found is −1, report failure; otherwise report the index.
  6. Stop.

With 5, 5 1 4 2 8, and a key of 4 the answer is index 2; with a key of 9 it is not found. The result variable starts at −1, a value that cannot be an index, so that after the loop its value alone says whether the search succeeded; break stops at the first match, so a repeated key reports its earliest position. Indices count from 0 here, as they do everywhere in C. A lab manual that wants "position 3" for the same input is counting from 1, and the only change is printing found + 1; say which convention you used in the record and be consistent.

Linear search is the right tool for an unsorted array and it is the last resort for a sorted one, since it looks at every element in the worst case. Week 11 sorts the array first and then searches it in a fraction of the comparisons.

Key Takeaways

  • Fix an array's capacity with a #define, read N, and refuse any N outside 1 to the capacity before the read loop; an unchecked N is a buffer overrun.
  • Variance needs the mean first, so the values must be stored and walked twice; population variance divides by N, sample variance by N − 1.
  • Bubble sort: neighbour compare-and-swap with a temporary, inner bound n - 1 - i, largest value settling at the end of each pass.
  • Print an array as a heading followed by a space and each element, so the line has no trailing space and no special first case.
  • Linear search: result index starts at −1, break on the first match, and the result alone tells success from failure.
  • C indices count from 0; a lab manual counting from 1 wants found + 1, and the record should say which.