シーケンスの実行

コンピュータサイエンスにおいて、シーケンスのランとは、シーケンスの非減少範囲であり、拡張できません。シーケンスのランの数は、シーケンスの増加部分シーケンスの数です。これは事前ソートの尺度であり、特にシーケンスをソートするためにどれだけの部分シーケンスをマージする必要があるかを表します。

意味

を全順序集合の要素の列とします。のラン は最大増加列です。つまり、と^{[説明が必要]}が存在すると仮定した場合、 となります。例えば、 が自然数 の場合、列にはと の2つのランが含まれます。 ${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$ ${\displaystyle X}$ ${\displaystyle \langle x_{i},x_{i+1},\dots ,x_{j-1},x_{j}\rangle }$ ${\displaystyle x_{i-1}>x_{i}}$ ${\displaystyle x_{j}>x_{j+1}}$ ${\displaystyle x_{i-1}}$ ${\displaystyle x_{j+1}}$ ${\displaystyle n}$ ${\displaystyle \langle n+1,n+2,\dots ,2n,1,2,\dots ,n\rangle }$ ${\displaystyle \langle n+1,\dots ,2n\rangle }$ ${\displaystyle \langle 1,\dots ,n\rangle }$

を かつ となる位置の数として定義します。これは、マイナス1の連続数として定義されることと同義です。この定義は、 、つまり が、かつ がソートされている場合に限り、となることを保証します。別の例として、および が挙げられます。 ${\displaystyle {\mathtt {runs}}(X)}$ ${\displaystyle i}$ ${\displaystyle 1\leq i<n}$ ${\displaystyle x_{i+1}$ ${\displaystyle X}$ ${\displaystyle {\mathtt {実行数}}(\langle 1,2,\dots ,n\rangle )=0}$ ${\displaystyle {\mathtt {runs}}(X)=0}$ ${\displaystyle X}$ ${\displaystyle {\mathtt {実行数}}(\langle n,n-1,\dots ,1\rangle )=n-1}$ ${\displaystyle {\mathtt {実行数}}(\langle 2,1,4,3,\dots ,2n,2n-1\rangle )=n}$

実行回数が少ないシーケンスのソート

この関数は、事前ソートの程度を表す尺度です。自然マージソートは r u n s {\displaystyle {\mathtt {runs}}} 最適です。つまり、シーケンスのラン数が少ないことが分かっている場合、自然マージソートを用いて効率的にソートできます。 ${\displaystyle {\mathtt {実行}}}$

長距離走

ロングランはランと同様に定義されますが、シーケンスが非減少または非増加のいずれかである点が異なります。ロングランの数は、事前ソートの尺度ではありません。ロングランの数が少ないシーケンスは、まず減少するランを逆順に並べ替え、次に自然マージソートを使用することで効率的にソートできます。

参考文献

• Powers, David MW; McMahon, Graham B. (1983). 「興味深いPrologプログラム集」 DCS技術レポート8313（レポート） ニューサウスウェールズ大学コンピュータサイエンス学部
• Mannila, H (1985). 「事前ソートの尺度と最適ソートアルゴリズム」IEEE Trans. Comput. (C-34): 318– 325. doi :10.1109/TC.1985.5009382.