Jerry Wayne Odom Jr. 


#!/usr/bin/perl
#heap sort source
sub heapSort;
sub siftDown;

open(T, "testdata.txt");
@masterarray;
$i = 0;
while($m = ){ chomp($m); $masterarray[$i] = $m; $i++ }
foreach $b(@masterarray){ print "$b\n" }
print "\n\n";
heapSort;
close(T);

sub heapSort {
  my $array_size = scalar(@masterarray);
  my $i;
  my $temp;

  for ($i = int ($array_size / 2) - 1; $i >= 0; $i--) {
	print "|$i|$array_size|\n";
  	siftDown($i, $array_size);
	foreach $b(@masterarray){ print "$b\n" }
	print "\n\n";
  }
  for ($i = $array_size - 1; $i >= 1; $i--){
  	$temp = $masterarray[0];
	$masterarray[0] = $masterarray[$i];
	$masterarray[$i] = $temp;

	print "|0|$i-1|\n";
	siftDown(0, $i-1);
	foreach $b(@masterarray){ print "$b\n" }
	print "\n\n";
  }
}


sub siftDown{   
  @a = @_;
  my $root = $a[0];
  my $bottom = $a[1];
  my $done = 0;
  my $maxChild;
  my $temp;
  my $temp2;
  while (($root*2 <= $bottom) && ($done != 1))
  {
	if ($root*2 == $bottom){ $maxChild = $root * 2 }
	elsif($masterarray[$root * 2] > $masterarray[$root * 2 + 1]) { $maxChild = $root * 2 }
	else{ $maxChild = $root * 2 + 1 }
	if ($masterarray[$root] < $masterarray[$maxChild]){
		$temp = $masterarray[$root];
		$masterarray[$root] = $masterarray[$maxChild];
		$masterarray[$maxChild] = $temp;
		$root = $maxChild;
	}
	else{ $done = 1 }
  }


}

 

© 2002, Jerry Odom