ソート番号

ソートアルゴリズムで使用される最悪の比較回数

数学とコンピュータサイエンスにおいて、ソート数（ソートすう）とは、1950年にヒューゴ・シュタインハウスが比較ソートアルゴリズムの解析のために導入した数列である。これらの数は、バイナリ挿入ソートとマージソートの両方で使用される比較の最悪ケース数を表す。ただし、比較回数がより少ないアルゴリズムも存在する。

公式と例

番目のソート番号は式^{[1]で与えられる。} ${\displaystyle n}$

${\displaystyle \displaystyle n\lceil \log _{2}n\rceil -2^{\lceil \log _{2}n\rceil }+1.}$

この式で与えられる数列（ から始まる）は ${\displaystyle n=1}$

0、1、3、5、8、11、14、17、21、25、29、33、37、41、...（OEISのシーケンスA001855）。

同じ数列は再帰関係^[2]からも得られる。

${\displaystyle A(n)=A{\bigl (}\lfloor n/2\rfloor {\bigr )}+A{\bigl (}\lceil n/2\rceil {\bigr )}+n-1}$。

これは2-正規列の例である。^[2]

漸近的に、番目のソート番号の値は、と最も近い2の累乗 との比に応じて、およそ と の間で変動します。^[1] ${\displaystyle n}$ ${\displaystyle n\log _{2}n-n}$ ${\displaystyle n\log _{2}n-0.915n,}$ ${\displaystyle n}$

ソートへの応用

1950年、ヒューゴ・スタインハウスは、これらの数値が二項挿入ソートで使用される比較回数を数えていることに気づき、あらゆる比較ソートを用いて項目をソートするために必要な最小の比較回数を与えると（誤って）推測しました。この推測は1959年にLRフォード・ジュニアとセルマー・M・ジョンソンによって反証されました。彼らは、より少ない比較回数を使用する別のソートアルゴリズム、フォード・ジョンソン・マージ挿入ソートを発見しました。^[1] ${\displaystyle n}$

同じソート番号のシーケンスは、マージソートでアイテムをソートするために使用する比較の最悪ケースの数も示します。^[2] ${\displaystyle n}$

その他のアプリケーション

ソート番号（1つシフトしたもの）は、階層化された順列の可能な限り最短のスーパーパターンのサイズも与えます。^[3]

参考文献

1. フォード、レスター・R・ジュニア;ジョンソン、セルマー・M. (1959)、「トーナメント問題」、アメリカ数学月刊誌、66 (5): 387– 389、doi :10.2307/2308750、JSTOR  2308750、MR  0103159
2. Allouche, Jean-Paul; Shallit, Jeffrey (1992)、「- regularシーケンスの環」、理論計算機科学、98 (2): 163– 197、doi : 10.1016/0304-3975(92)90001-V、MR  1166363 ${\displaystyle k}$192ページの例28を参照。
3. Albert, Michael ; Engen, Michael; Pantone, Jay; Vatter, Vincent (2018)、「Universal layered permutations」、Electronic Journal of Combinatorics、25 (3): P23:1–P23:5、arXiv : 1710.04240、doi : 10.37236/7386、S2CID  52100342

「https://en.wikipedia.org/w/index.php?title=Sorting_number&oldid=1262729689」より取得