Algorithm::SISort - Select And Insert sorting algorithm

Location : Home > Languages > Perl > Package
Title : Algorithm::SISort

　Algorithm::SISort - 挿入ソート・選択ソートの組み合わせ

use Algorithm::SISort qw(Sort Sort_inplace);

@sorted_list = Sort {$_[0] <=> $_[1]} @unsorted_list;
# ... または ...
$number_of_comparisons = Sort_inplace {$_[0] <=> $_[1]} @unsorted_list;

説明

　本モジュールは BIT 28 (1988) の記事で見た Istvan Beck・Stein Krogdahl らによるソートアルゴリズムを実装している。この実装は主に Brian Ingerson による Inline モジュールの拡張を意図している。アルゴリズムは Straight Insertion Sort 及び Selection Sort の組み合わせである。Insertion Sort 及び Selection Sort はともに O(n**2) の計算量であるのに対し Select 及び Insert Sort は O(n**1.5) の計算量である。
　本モジュールでは Sort 及び Sort_inplace の２つの関数を定義しており、内部ソート関数とよく似た働きをする。違いは比較を定義する codref が常に必要なことと、比較対象の２つの値が $a 及び $b という形ではなくて @_ で渡されることである。（後に変更するかも知れないけれど。）
　Sort 関数は、配列であればソートされたコピーを返すが Sort_inplace 関数は置き換えた配列と比較結果の数を返す。（ソートは常に置き換えで実行されるので、配列をコピーするには内部ソート関数を呼び出す前に複製しておく必要があることに注意すること。）

バグ

　バグ報告は歓迎するので CPAN Request Tracker http://rt.cpan.org/NoAuth/Bugs.html?Dist=Algorithm-SISort まで報告してほしい。

参考資料

　Inline, Inline::C 及び BIT 28 (1988), 726-735 所収の A Select And Insert Sorting Algorithm （Istvan Beck and Stein Krogdahl） .

著者

　Hrafnkell F. Hlodverssono, <keli@panmedia.dk>

著作権

Updated : 2006/08/28