「ヒープソート」(2009/11/04 (水) 00:00:47) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
//perl/linenumber
use strict;
use warnings;
my $LIST_SIZE ||= 20;
my @heap;
for(my $i = 0; $i < $LIST_SIZE; $i++){
$heap[$i] = int($i);
}
#ランダムに並び替える
srand;
for (my $i = @heap; --$i; ) {
my $j = int rand ($i + 1);
next if $i == $j;
@heap[$i, $j] = @heap[$j, $i];
}
# 1個目はダミー
my @g_heap = (-1);
print_array(\@heap); # 実行前
&heapsort(\@heap);
print_array(\@heap); # 実行後
sub heapsort{
my $array = shift;
&insertheap($array);
for(my $i = 0; $i < scalar(@$array); $i++){
$array->[$i] = &get_root;
}
}
sub insertheap{
my $array = shift;
for(my $i = 0; $i < scalar(@$array); $i++){
push @g_heap, $array->[$i];
upheap($#g_heap);
}
}
sub upheap{
my $index = shift;
my $tmp = $g_heap[$index];
while( ($index > 1) && ($g_heap[int($index / 2)] > $tmp)){
$g_heap[$index] = $g_heap[int($index / 2)];
$index = int($index / 2);
}
$g_heap[$index] = $tmp;
}
sub get_root{
my $tmp;
if( scalar(@g_heap) < 1){
print "ヒープが空です";
exit;
}
$tmp = $g_heap[1];
$g_heap[1] = $g_heap[$#g_heap];
pop @g_heap;
&downheap;
return $tmp;
}
sub downheap{
if(scalar(@g_heap) < 2){
return;
}
my $tmp = $g_heap[1];
my $i = 1;
while($i <= int($#g_heap / 2)){
my $j = $i * 2;
if( ($j + 1 <= $#g_heap) && ($g_heap[$j] > $g_heap[$j + 1]) ){
$j++;
}
if($tmp <= $g_heap[$j]){
last;
}
$g_heap[$i] = $g_heap[$j];
$i = $j;
}
$g_heap[$i] = $tmp;
}
sub print_array{
my $ref_array = shift;
for my $i(@$ref_array){
print "$i ";
}
print "\n";
}
表示オプション
横に並べて表示:
変化行の前後のみ表示: