FC2ブログ

# クイックソート QuickSort
# 引数 値 (\@Price)
# 戻り値 クイックソート (@QuickSort)
sub QUICKSORT{
my ($Price) = @_;
my @QuickSort = @$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 = ($QuickSort[$Left] + $QuickSort[int(($Left + $Right) / 2)] + $QuickSort[$Right]) / 3;
$StandardValue = $QuickSort[int(($Left + $Right) / 2)];
# 一つ前の配列の位置
my $PrevLeft = $Left;
my $PrevRight = $Right;

next if($Left >= $Right);

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

last if($Left > $Right);

# 配列の入れ替え
($QuickSort[$Left], $QuickSort[$Right]) = ($QuickSort[$Right], $QuickSort[$Left]);
$Left++;
$Right--;
}

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

return @QuickSort;
}


参考URL
クイックソート - Wikipedia
アルゴリズムとデータ構造I及び演習 (X121/X122) [14]クイックソート 講義資料(PDF)

メモ
基準値 $StandardValue = ($QuickSort[$Left] + $QuickSort[int(($Left + $Right) / 2)] + $QuickSort[$Right]) / 3 を使用すると無限ループすることがある
分割の仕方が悪いのか?
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

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

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

検索フォーム


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