葉数適応整列法LOASの最適性

概要

論文の詳細を見る
現実の問題として数列のソーティングを扱う場合には、与えられた数列が殆ど整列済みである場合が多いと言われている。我々は整列済みに近い数列ほど速く整列するソーティングアルゴリズムLOAS(Leaves-Optimal-Adaptive-Sort)を文献[3]で発表した。そこでは数列の整列度を計る為に葉数と呼ばれる事前整列性測度を導入し、その測度に関して数列の整列度が良い時には、LOASが既存のQUICKソートやMERGEソート等よりも高性能であることを示した。またより詳しい性能比較評価、およびLOASの実現方式の詳細については本大会の別講演で報告する。本稿ではLOASが葉数に関して最適なアルゴリズムであることを詳しく論じる。以下では長さnの順列のみを扱う。数列Xの長さおよび集合Sの濃度を各々|X|および‖S‖で表す。対数の底は2、即ちlog n=log_2 nとする。merge(X,Y)は2つの整列済み数列XとYをマージする関数である。例えばX=<l,3,5>かつY=<2,4,6>ならばmerge(X,Y)=<1,2,3,4,5,6>である。適応整列法に関する既存の表記法および概念については[6]に従う。
一般社団法人情報処理学会の論文
1995-03-15