Run of a sequence

In computer science, a run of a sequence is a non-decreasing range of the sequence that cannot be extended. The number of runs of a sequence is the number of increasing subsequences of the sequence. This is a measure of presortedness, and in particular measures how many subsequences must be merged to sort a sequence.

Definition

Let ${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$ be a sequence of elements from a totally ordered set. A run of ${\displaystyle X}$ is a maximal increasing sequence ${\displaystyle \langle x_{i},x_{i+1},\dots ,x_{j-1},x_{j}\rangle }$. That is, ${\displaystyle x_{i-1}>x_{i}}$ and ${\displaystyle x_{j}>x_{j+1}}$^{[clarification needed]} assuming that ${\displaystyle x_{i-1}}$ and ${\displaystyle x_{j+1}}$ exists. For example, if ${\displaystyle n}$ is a natural number, the sequence ${\displaystyle \langle n+1,n+2,\dots ,2n,1,2,\dots ,n\rangle }$ has the two runs ${\displaystyle \langle n+1,\dots ,2n\rangle }$ and ${\displaystyle \langle 1,\dots ,n\rangle }$.

Let ${\displaystyle {\mathtt {runs}}(X)}$ be defined as the number of positions ${\displaystyle i}$ such that ${\displaystyle 1\leq i<n}$ and ${\displaystyle x_{i+1}<x_{i}}$. It is equivalently defined as the number of runs of ${\displaystyle X}$ minus one. This definition ensure that ${\displaystyle {\mathtt {runs}}(\langle 1,2,\dots ,n\rangle )=0}$, that is, the ${\displaystyle {\mathtt {runs}}(X)=0}$ if, and only if, the sequence ${\displaystyle X}$ is sorted. As another example, ${\displaystyle {\mathtt {runs}}(\langle n,n-1,\dots ,1\rangle )=n-1}$ and ${\displaystyle {\mathtt {runs}}(\langle 2,1,4,3,\dots ,2n,2n-1\rangle )=n}$.

Sorting sequences with a low number of runs

The function ${\displaystyle {\mathtt {runs}}}$ is a measure of presortedness. The natural merge sort is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math alttext="{\displaystyle {\mathtt {runs}}}" xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mrow class="MJX-TeXAtom-ORD"> <mi mathvariant="monospace">r</mi> <mi mathvariant="monospace">u</mi> <mi mathvariant="monospace">n</mi> <mi mathvariant="monospace">s</mi> </mrow> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\mathtt {runs}}}</annotation> </semantics> </math></span><img alt="{\displaystyle {\mathtt {runs}}}" aria-hidden="true" class="mwe-math-fallback-image-inline mw-invert" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/18d9447c84e1a6fcc3b63642b4ebf5586eeec55e" style="vertical-align: -0.338ex; width:4.882ex; height:1.676ex;"/></span>-optimal. That is, if it is known that a sequence has a low number of runs, it can be efficiently sorted using the natural merge sort.

Long runs

A long run is defined similarly to a run, except that the sequence can be either non-decreasing or non-increasing. The number of long runs is not a measure of presortedness. A sequence with a small number of long runs can be sorted efficiently by first reversing the decreasing runs and then using a natural merge sort.

References

• Powers, David M. W.; McMahon, Graham B. (1983). "A compendium of interesting prolog programs". DCS Technical Report 8313 (Report). Department of Computer Science, University of New South Wales.
• Mannila, H (1985). "Measures of Presortedness and Optimal Sorting Algorithms". IEEE Trans. Comput. (C-34): 318–325.

This page was last edited on 26 February 2022, at 10:07