FC2ブログ

# マージソート MergeSort
# 引数 値 (\@Price)
# 戻り値 マージソート (@MergeSort)
sub MERGESORT{
my ($Price) = @_;
my @MergeSort = @$Price;
my $Loop = 0;
my $Count = @$Price - 1;
my @InfoDivide = ([$Count + 1]);

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

# 分割数を 1以下にする
while(($InfoDivide[$Loop][0] > 1)){
$Loop++;
for(my $i = 0; $i < @{$InfoDivide[$Loop - 1]}; $i++){
my $id = $InfoDivide[$Loop - 1][$i] / 2;
# 分割情報
$InfoDivide[$Loop][2 * $i] = int($id);
$InfoDivide[$Loop][(2 * $i) + 1] = int($id + 0.5);
}
}

# 昇順ソート
for(my $i = @InfoDivide - 1; $i >= 0; $i--){
my $Start = 0;
my @Temp = ();
$Loop = @{$InfoDivide[$i]};

for(my $j = 0; $j < $Loop; $j++){
# 分割情報
my $DivideA = int($InfoDivide[$i][$j] / 2);
my $DivideB = $InfoDivide[$i][$j] - $DivideA;
# 配列の位置
my $CountA = 0;
my $CountB = 0;
my $Num = 0;
# 配列の位置を調整
my $MoveB = $DivideA;

# 分割 昇順ソート
while(($CountA < $DivideA) && ($CountB < $DivideB)){
if($MergeSort[$Start + $CountA] > $MergeSort[$Start + $CountB + $MoveB]){
$Temp[$Start + $Num] = $MergeSort[$Start + $CountB + $MoveB];
$CountB++;
}else {
$Temp[$Start + $Num] = $MergeSort[$Start + $CountA];
$CountA++;
}
$Num++;
}

# 残り
my ($CountC, $CompC, $MoveC) = ($CountA != $DivideA ? ($CountA, $DivideA, 0) : ($CountB, $DivideB, $MoveB));
while($CountC < $CompC){
$Temp[$Start + $Num] = $MergeSort[$Start + $CountC + $MoveC];
$CountC++;
$Num++;
}

# 配列の開始位置を移動する
$Start += $InfoDivide[$i][$j];
}

# 配列のコピー
@MergeSort = @Temp;
}

return @MergeSort;
}


参考URL
マージソート - Wikipedia
YouTube - マージソート

一言
むずい・・
ソート内での分割数の出し方が思いつかない
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

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

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

検索フォーム


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