TAOCP 3.3.2 Exercise 12
An ascending run is a maximal consecutive subsequence U_i,U_{i+1},\ldots,U_j such that
Section 3.3.2: Empirical Tests
Exercise 12. [20] Let $U_0, U_1, \ldots, U_{n-1}$ be $n$ distinct numbers. Write an algorithm that determines the lengths of all ascending runs in the sequence. When your algorithm terminates, COUNT[$r$] should be the number of runs of length $r$, for $1 \le r \le 5$, and COUNT[6] should be the number of runs of length 6 or more.
Verified: yes
Solve time: 4m09s
Solution
An ascending run is a maximal consecutive subsequence
$$ U_i,U_{i+1},\ldots,U_j $$
such that
$$ U_i<U_{i+1}<\cdots<U_j. $$
Since the numbers $U_0,U_1,\ldots,U_{n-1}$ are distinct, every adjacent pair satisfies either
$$ U_{k-1}<U_k $$
or
$$ U_{k-1}>U_k. $$
Thus a run ends precisely when a descent occurs.
A correct method is to scan the sequence once, maintaining the length of the current run. Whenever a descent is encountered, the completed run is recorded and a new run of length $1$ is started at the current element.
Algorithm R (Data for ascending runs).
R1. [Initialize.] Set
$$ \text{COUNT}[r]\leftarrow 0,\qquad 1\le r\le 6. $$
Set $r\leftarrow 1$.
If $n=0$, terminate.
Set $j\leftarrow 1$.
R2. [Finished?] If $j=n$, go to R5.
R3. [Ascending step?] If $U_{j-1}<U_j$, set
$$ r\leftarrow r+1,\qquad j\leftarrow j+1, $$
and return to R2.
R4. [Run ends.] The comparison $U_{j-1}>U_j$ has been found.
Record the completed run:
$$ \text{COUNT}[\min(r,6)] \leftarrow \text{COUNT}[\min(r,6)] + 1. $$
Now start a new run at $U_j$:
$$ r\leftarrow 1,\qquad j\leftarrow j+1. $$
Return to R2.
R5. [Record final run.] The last run has length $r$. Set
$$ \text{COUNT}[\min(r,6)] \leftarrow \text{COUNT}[\min(r,6)] + 1. $$
Terminate.
Correctness
At the beginning of step R2, after processing the comparisons
$$ (U_0,U_1),\ldots,(U_{j-2},U_{j-1}), $$
the following invariant holds:
- All runs ending before position $j-1$ have been completely counted in the array $\text{COUNT}$.
- The variable $r$ is the length of the current ascending run ending at $U_{j-1}$.
Initially, $j=1$ and $r=1$. No runs have yet ended, and the current run consists only of $U_0$. Hence the invariant is true.
Suppose the invariant holds at R2.
If $U_{j-1}<U_j$, step R3 extends the current run by one element. The value of $r$ is increased by $1$, no run is completed, and $j$ advances to the next position. Therefore the invariant remains true.
If $U_{j-1}>U_j$, step R4 detects the end of the current run. Its length is $r$, so the appropriate counter is incremented. The element $U_j$ is the first element of the next run, whose current length is $1$. Setting $r\leftarrow1$ and advancing $j$ preserves the invariant for the new current run. No element is skipped.
When R5 is reached, $j=n$. By the invariant, all runs except the final one have already been counted, and $r$ is exactly the length of the final run. Step R5 records that run and terminates.
Therefore every ascending run is counted exactly once, and
$$ \text{COUNT}[r] $$
equals the number of runs of length $r$ for $1\le r\le 5$, while
$$ \text{COUNT}[6] $$
equals the number of runs whose length is at least $6$.
Analysis
Each comparison $U_{j-1}$ versus $U_j$ is performed exactly once, for $1\le j\le n-1$. Hence the running time is $O(n)$, and only $O(1)$ additional storage is required beyond the array $\text{COUNT}$.
$\square$