These notes recap Topic 4.5. Full explanations and worked examples are in the study guide.
Recap
The standard array algorithms are traversals with a little extra state:
- Minimum or maximum: keep a best so far, started at the first element.
- Sum or average: running total from 0; for an average divide as a
double. - At least one has a property:
return trueinside the loop on the first match;return falseafter the loop. - All have a property:
return falseinside the loop on the first failure;return trueafter the loop. - Count: a counter from 0, incremented when the property holds.
- Consecutive pairs:
a[i]anda[i + 1]withi < a.length - 1. - Duplicates: an inner loop starting at
i + 1. - Shift or rotate: save one element, move the others, write the saved one back.
- Reverse: swap from both ends towards the middle.
Key patterns
| Algorithm | Before the loop | In the loop | After the loop |
|---|---|---|---|
| Maximum | best = a[0] |
if a[i] > best, best = a[i] |
return best |
| Sum | total = 0 |
total += a[i] |
return total |
| Count | count = 0 |
if property, count++ |
return count |
| Any | nothing | if property, return true |
return false |
| All | nothing | if not property, return false |
return true |
| Rotate left | first = a[0] |
a[i] = a[i + 1] for i up to length - 2 |
a[length - 1] = first |
| Reverse | nothing | swap a[i] and a[length - 1 - i] for i < length / 2 |
nothing |
Results to remember
For t = {4, 9, 2, 7, 9}: maximum 9, minimum 2, sum 31, average 6.2, count above 5 is 3, rising pairs 3, duplicates present. Rotating {1, 2, 3, 4, 5} left gives 2 3 4 5 1; rotating right gives 5 1 2 3 4. Reversing {4, 8, 15, 16, 23} gives 23 16 15 8 4.
Assumptions
- The array has at least one element for min, max and average.
- Rotate, shift and reverse change the array that was passed, because the parameter holds a reference to it.
- The average needs a cast or a
doublesomewhere in the division.
Mistakes to avoid
- Starting a maximum at 0.
return truetoo early in an “all” loop.- Integer division in an average.
i < a.lengthwhen comparinga[i]witha[i + 1].- Rotating right from the front, or reversing all the way to the end.
Quick self-check
- For
{-4, -9, -2}, what does a maximum that starts at 0 return? Answer: 0, which is wrong; the maximum is -2. - How many rising pairs in
{1, 5, 3, 8, 9}? Answer: 3. - After
rotateLefton{1, 2, 3, 4, 5}, what is the last element? Answer: 1. - Why does the duplicates inner loop start at
i + 1? Answer: so an element is not compared with itself.