FC2ブログ

# イントロソート IntroSort
# 引数 要素数 値 ($N, \@Price)
# 戻り値 イントロソート (@IntroSort)
sub INTROSORT{
my ($N, $Price) = @_;
my @IntroSort = @$Price;
my $Left = 0;
my $Right = 0;
my $StandardValue = 0;
my $Count = @$Price - 1;
my @InfoLeft = (0);
my @InfoRight = ($Count);
my $StackPoint = 1;

# 配列数の確認
if($Count <= 0){
return 0;
}

# 昇順ソート
while($StackPoint > 0){
# スタックポイント
$StackPoint--;
# 配列の位置
$Left = $InfoLeft[$StackPoint];
$Right = $InfoRight[$StackPoint];
# 基準値
# $StandardValue = ($IntroSort[$Left] + $IntroSort[int(($Left + $Right) / 2)] + $IntroSort[$Right]) / 3;
$StandardValue = $IntroSort[int(($Left + $Right) / 2)];
# 一つ前の配列の位置
my $PrevLeft = $Left;
my $PrevRight = $Right;

next if($Left >= $Right);

# 要素数 $N 以下になったらヒープソートに切り替える
if(($Right - $Left) < $N){
&HEAPSORT($Left, $Right, \@IntroSort);
next;
}

while($Left <= $Right){
# 左 基準値未満なら1足す
$Left++ while($IntroSort[$Left] < $StandardValue);
# 右 基準値超なら1引く
$Right-- while($StandardValue < $IntroSort[$Right]);

last if($Left > $Right);

# 要素の入れ替え
($IntroSort[$Left], $IntroSort[$Right]) = ($IntroSort[$Right], $IntroSort[$Left]);
$Left++;
$Right--;
}

# 分割情報 スタック 後入れ先出し
$InfoLeft[$StackPoint] = $PrevLeft;
$InfoRight[$StackPoint] = $Right;
$StackPoint++;
$InfoLeft[$StackPoint] = $Left;
$InfoRight[$StackPoint] = $PrevRight;
$StackPoint++;
}

return @IntroSort;
}

# ヒープソート HeapSort
# 引数 値 (\@Price)
# 戻り値 ヒープソート (@HeapSort)
sub HEAPSORT{
my ($Start, $End, $HeapSort) = @_;
my $Root = $Start;
my $Diff = $End - $Start;

# 半順序木 ヒープ構造の作成
for(my $i = 1; $i <= $Diff; $i++){
# 配列の位置
my $ParentNum = int(($i - 1) / 2);
my $ChildNum = $i;
my $ParentNumRoot = $ParentNum + $Root;
my $ChildNumRoot = $ChildNum + $Root;

while($ChildNum != 0){
# 根に最高値を持って行く
if($$HeapSort[$ChildNumRoot] > $$HeapSort[$ParentNumRoot]){
($$HeapSort[$ChildNumRoot], $$HeapSort[$ParentNumRoot]) = ($$HeapSort[$ParentNumRoot], $$HeapSort[$ChildNumRoot]);
}

# 配列の位置
$ChildNum = $ParentNum;
$ParentNum = int(($ParentNum - 1) / 2);
$ParentNumRoot = $ParentNum + $Root;
$ChildNumRoot = $ChildNum + $Root;
}
}

# 昇順ソート
for(my $i = $Diff; $i > 0; $i--){
# 配列の位置
my $ParentNum = 0;
my $ChildNum = (2 * $ParentNum) + 1;
my $ParentNumRoot = $ParentNum + $Root;
my $ChildNumRoot = $ChildNum + $Root;
# 根を後ろに持っていく
($$HeapSort[$ParentNumRoot], $$HeapSort[$i + $Root]) = ($$HeapSort[$i + $Root], $$HeapSort[$ParentNumRoot]);

# ヒープ構造の再構築
while($ChildNum < $i){
# $ChildNumは常に最初は子ノードAを指し示めしている
# 子ノードBがソート済みではない と 子ノードA < 子ノードB ならTrue
if((($ChildNum + 1) != $i) && ($$HeapSort[$ChildNumRoot] < $$HeapSort[$ChildNumRoot + 1])){
$ChildNum++;
$ChildNumRoot++;
}
# 親のノード < 子ノード
if($$HeapSort[$ParentNumRoot] < $$HeapSort[$ChildNumRoot]){
($$HeapSort[$ParentNumRoot], $$HeapSort[$ChildNumRoot]) = ($$HeapSort[$ChildNumRoot], $$HeapSort[$ParentNumRoot]);
}else {
last;
}

# 配列の位置
$ParentNum = $ChildNum;
$ChildNum = (2 * $ParentNum) + 1;
$ParentNumRoot = $ParentNum + $Root;
$ChildNumRoot = $ChildNum + $Root;
}
}
}


参考URL
イントロソート - Wikipedia
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

Author:雨宮
Firefoxを使用しているので気づかなかったけど、IE6でソースコードを上手くコピーできない

5/3
携帯用ならIE6でもソースコードをコピーできる
携帯用

検索フォーム


あわせて読みたいブログパーツ
一寸先は闇 RSS