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;