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 $X=\langle x_1,\dots,x_n\rangle$ be a sequence of elements from a totally ordered set. A run of $X$ is a maximal increasing sequence $\langle x_i,x_{i+1},\dots, x_{j-1},x_j \rangle$ . That is, $x_{i-1}>x_i$ and $x_{j}>x_{j+1}$ {{clarify|reason=In order to match with definition of "increasing sequence" and with that of Runs, ≥ should be used instead of >.|date=May 2021}} assuming that $x_{i-1}$ and $x_{j+1}$ exists. For example, if $n$ is a natural number, the sequence $\langle n+1,n+2,\dots, 2n, 1,2,\dots, n\rangle$ has the two runs $\langle n+1,\dots, 2n \rangle$ and $\langle 1,\dots,n \rangle$ .

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

Sorting sequences with a low number of runs

The function $\mathtt{runs}$ is a measure of presortedness. The natural merge sort is $\mathtt{runs}$ -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

{{cite report |last1=Powers |first1=David M. W. |last2=McMahon |first2=Graham B. |date=1983 |section=A compendium of interesting prolog programs |title=DCS Technical Report 8313 |publisher=Department of Computer Science, University of New South Wales}}
{{cite journal |last1=Mannila |first1=H |title=Measures of Presortedness and Optimal Sorting Algorithms |journal=IEEE Trans. Comput. |date=1985 |issue=C-34 |pages=318–325|doi=10.1109/TC.1985.5009382 }}

Category:Sorting algorithms