Return to Mr Belvedere's Programming Nook
Test the Heap sort
© 1996 by Bobby Griggs.
(**************************************************************************)
(*
Robert C. Griggs, Jr.
User C181A09
Homework Assignment
Program name - HEAPTEST.P
September 17, 1991
*)
(**************************************************************************)
(*
This program is designed to randomly generate numbers, and to load them
into an array. Once loaded, the array is sorted into ascending order
using a heapsort algorithm. Finally, the sorted numbers are displayed
to the screen.
*)
(**************************************************************************)
(*
Algorithm:
1. Specify two constants to hold data for minimum and maxium elements
of the arrays.
MAX for maxium elements in the array
MIN for minimum array element
2. Use an array of integers to hold the randomly generated numbers.
numlist - array of integer
3. Specify variable for use within program.
numbers as type numlist to hold the randomly generated numbers
4. Run procedure to load the randomly generated numbers into the array.
A. use the following variables:
num to hold randomly generated number
counter for use in loading the array
randnum for use in generating random number
B. set randnum = 1
C. use a for loop to generate randum numbers and load array
5. Run procedure heapsort to sort random numbers in ascending order.
A. use the following variables:
tempnum to hold number while making heap
l set up by dividing array size by 2 + 1 to establish portion
of array that must initially be converted to heap form.
All elements equal to initial value of l or above are
already in heap form, since they do not have any
descendents.
r set equal to end of array for future operations of sift to
convert remaining portion of array into a heap again,
and continue sort the array elements.
B. Establish middle point of the array to determine portion that
will have to be converted to heap form. Any elements above
middle point are already in heap form since they have no
descendents.
C. Decrement the variable established by determining the mid
point of the array, and run procedure sift to put first half
of the array in heap form to prepare it for sorting. Continue
decrementing the variable by one, and process the array as
long as the variable value is greater than 1.
1. Procedure sift that is mentioned above is used to put
the array in heap form.
a. Variables to be used in sift:
i as position of parent array element
j as position of left descendent
exitsort as boolean to determine whether to stay in loop
b. set i equal to parent position
c. determine position of left descendent by multiplying
i by 2
d. set temporary hold variable equal to parent array element
e. if descendent is less than or equal end of array portion
to be converted to heap form do the following:
1. if position of left descendent is less than position
of the end of the portion to be converted to a heap,
then check to see whether the left descendent is
less than the right descendent, and have j point to
the descendent that has the greater value
2. if the value in the temporary hold variable is
greater than the larger descendent, then exit the
loop
3. otherwise, set the parent position equal the value
of the descendent
4. set parent position equal to position of descendent
in previous comparison, and set descendent position
to 2 times that to force exit from loop
2. Set the parent array element equal to the value in the
temporary hold variable. If the position was changed in the
while loop because the descendent was great then the parent,
then this will place the hold value into the array position
of the descendent rather than the parent.
D. As long as r which is set to the end of array portion to be put
into heap form is greater than 1, continue with the heapsort
procedure. Otherwise, exit the procedure at this point.
E. If procedure continues, set the temporary hold variable equal
to the first element of the array. This element will have the
largest value of any array element due to the previous execution
of sift that put the array into heap form.
F. Swap values between array element number 1 and the last array
element remaining to be sorted.
G. Decrement r by 1 to establish the new end of the portion of
the array to be sorted.
H. Run procedure sift again to put the remaining portion of the
array in heap form again.
6. Run procedure to display the random numbers to the screen.
A. use the following variables:
counter for use in for loop to display numbers to screen
B. execute the procedure to blank the screen
C. list the array elements on the screen
7. The main of the program will be executed in the following manner:
A. run procedure loadnums to load random numbers into the array
B. run procedure quicksort to sort numbers in ascending order
C. run procedure shownums to display numbers on screen
*)
(**************************************************************************)
(*
Constant dictionary:
MAX=15 for maximum elements in array to hold numbers
MIN=1 for minimum element identifier for array
*)
(**************************************************************************)
(*
Type dictionary:
numlist=array[MIN..MAX] of integer - array for random numbers
*)
(**************************************************************************)
(*
Variable dictionary:
numbers:numlist - array of randomly generated numbers
*)
(**************************************************************************)
program heaptest (input,output);
const
MAX=15; {maximum elements in array to hold numbers}
MIN=1; {minimum element identifier for array}
type
numlist=array[MIN..MAX] of integer; {definition of array}
var
numbers:numlist; {array of randomly generated numbers}
(***************************************************************************)
(* Procedure to blank screen *)
procedure blankscreen;
var
blank:integer; {line counter for blanking the screen}
begin {blankscreen}
for blank:=1 to 25 do
writeln;
end; {blankscreen}
(***************************************************************************)
(* Procedure to load the array with randomly generated numbers *)
procedure loadnums;
var
num, {to hold randomly generated number}
counter:integer; {for use in loading the array}
var
randnum:real; {for use in generating random number}
begin {loadnums}
randnum:=1;
for counter:=MIN to MAX do
begin {for loop}
num:=trunc(random(randnum)*10000);
numbers[counter]:=num;
end; {for loop}
end; {loadnums}
(***************************************************************************)
(* Procedure to execute heapsort *)
procedure heapsort;
var
tempnum, {to hold number while making heap}
l, {variable to be passed on to procedure sift}
r:integer; {variable for sorting}
(*****************************************************************)
(* Procedure to execute sift *)
procedure sift;
var
i, {variable for use in converting to heap}
j:integer; {variable for use in converting to heap}
var
exitsort:boolean; {stay in while statement if false}
begin {sift}
i:=l; {parent variable}
j:=i * 2; {establishes left descendent}
tempnum:=numbers[i]; {parent value in hold variable}
exitsort:=false;
while (j <= r) and (not exitsort) do
begin {while statement}
if (j < r) then {if descendent < remaining array to convert to a heap}
if (numbers[j] < numbers[j + 1]) then
j:=j + 1; {point to the largest of the two descendents}
if (tempnum >= numbers[j]) then
exitsort:=true {if parent is > largest descendent, exit loop}
else
begin {else statement}
numbers[i]:=numbers[j]; {otherwise, put value for largest descendent into parent}
i:=j;
j:=i * 2;
end; {else statement}
end; {while statement}
numbers[i]:=tempnum; {if parent was largest, set parent array element back to original value}
end; {sift}
(*****************************************************************)
begin {heapsort}
l:=(MAX div 2) + 1; {anything at this point or beyond is already a heap}
r:=MAX; {set r equal to end of array or elements to be sorted}
while (l > 1) do
begin {while statement}
l:=l-1; {set l equal to last element that needs to be put in a heap form}
sift; {run procedure to put array in heap form}
end; {while statement}
while (r > 1) do {do as long as last element in array area for heap is > 1}
begin {while statement}
tempnum:=numbers[1]; {set tempnum equal to first element of array}
numbers[1]:=numbers[r]; {move last element of new heap to first element}
{this puts largest element of heap from previous sift at bottom of heap}
numbers[r]:=tempnum; {move held value for first element to last element of new heap}
r:=r - 1; {decrement r for next next operation of sift}
sift; {put remaining portion of array into heap form again}
end; {while statement}
end; {heapsort}
(***************************************************************************)
(* Procedure to display the numbers to the screen *)
procedure shownums;
var
counter:integer; {for use in for loop}
begin {shownums}
blankscreen;
writeln ('The randomly generated numbers are: ');
writeln;
for counter:=MIN to MAX do
writeln (numbers[counter]);
end; {shownums}
(***************************************************************************)
begin {main}
loadnums;
heapsort;
shownums;
end. {main}