1 #!/usr/bin/perl 2 3 4 # Heapsort 5 # Author: John Bryan, Jr. 6 # Date: August 30, 2006 7 # Opens file, integers.txt, containing integers. 8 # Sorts integers using Heapsort and writes sorted 9 # integers to screen. 10 11 12 use strict; 13 14 15 sub GetIntegers 16 { 17 my $c; 18 $main::i=0;$main::j=0;$main::M=0;$main::k=0;$main::Number=0; 19 $main::file ='integers.txt'; 20 open(INTS, $main::file); 21 @main::integers1 = <INTS>; 22 close(INTS); 23 $main::M="$#main::integers1"+1; 24 for ($c=0;$c<$main::M;$c++) 25 { 26 push(@main::integers,split(' ',$main::integers1[$c])); 27 } 28 $main::N="$#main::integers"+1; 29 $main::Number=$main::N; 30 print "\nThe integers to be sorted are\n"; 31 &PrintIntegers; 32 } 33 34 35 sub PrintIntegers 36 { 37 my $c; 38 print("\n"); 39 for ($c=0;$c<$main::Number;$c++) 40 { 41 print ("$main::integers[$c] "); 42 } 43 } 44 45 46 sub BubbleDown 47 { 48 $main::j=$main::i; 49 do 50 { 51 $main::k=$main::j; 52 if(((2*$main::k+1)<$main::N)&& 53 ($main::integers[2*$main::k+1]>$main::integers[$main::j])) 54 {$main::j=2*$main::k+1;} 55 if(((2*$main::k+2)<$main::N)&& 56 ($main::integers[2*$main::k+2]>$main::integers[$main::j])) 57 {$main::j=2*$main::k+2;} 58 &Swap; 59 }while($main::k!=$main::j); 60 } 61 62 63 sub HeapSort 64 { 65 my $r; 66 for ($r=$main::N-1; $r>0; $r--) 67 { 68 $main::k=$r; 69 $main::j=0; 70 &Swap; 71 $main::i=0; 72 $main::N=$r; 73 &BubbleDown; 74 } 75 print "\nThe sorted integers are\n"; 76 &PrintIntegers; 77 } 78 79 80 sub Swap 81 { 82 my $temp; 83 $temp=$main::integers[$main::k]; 84 $main::integers[$main::k]=$main::integers[$main::j]; 85 $main::integers[$main::j]=$temp; 86 } 87 88 89 sub ConstructHeap 90 { 91 for ($main::i=$main::N-1; $main::i>=0; $main::i--) 92 {&BubbleDown;} 93 } 94 95 96 &GetIntegers; 97 &ConstructHeap; 98 &HeapSort;