# rows.incl.a68: array related utilities for Algol 68 RC tasks #
# prints the elements of an array of integers separated by spaces #
OP SHOW = ( []INT list )VOID:
FOR i FROM LWB list TO UPB list DO
print( ( " ", whole( list[ i ], 0 ) ) )
OD # SHOW # ;
# prints the elements of an array of reals separated by spaces #
OP SHOW = ( []REAL list )VOID:
FOR i FROM LWB list TO UPB list DO
print( ( " ", fixed( list[ i ], -14, 8 ) ) )
OD # SHOW # ;
# returns the kth lowest element of list usng the quick select algorithm #
PRIO QUICKSELECT = 9;
OP QUICKSELECT = ( REF[]INT list, INT k )INT:
IF LWB list > UPB list THEN
# empty list #
0
ELSE
# non-empty list #
# partitions the subset of list from left to right #
PROC partition = ( REF[]INT list, INT left, right, pivot index )INT:
BEGIN
# swaps elements a and b in list #
PROC swap = ( REF[]INT list, INT a, b )VOID:
BEGIN
INT t = list[ a ];
list[ a ] := list[ b ];
list[ b ] := t
END # swap # ;
INT pivot value = list[ pivot index ];
swap( list, pivot index, right );
INT store index := left;
FOR i FROM left TO right - 1 DO
IF list[ i ] < pivot value THEN
swap( list, store index, i );
store index +:= 1
FI
OD;
swap( list, right, store index );
store index
END # partition # ;
INT left := LWB list, right := UPB list, result := 0;
BOOL found := FALSE;
WHILE NOT found DO
IF left = right THEN
result := list[ left ];
found := TRUE
ELSE
INT pivot index = partition( list
, left
, right
, left + ENTIER ( ( random * ( right - left ) + 1 ) )
);
IF k = pivot index THEN
result := list[ k ];
found := TRUE
ELIF k < pivot index THEN
right := pivot index - 1
ELSE
left := pivot index + 1
FI
FI
OD;
result
FI # QUICKSELECT # ;
# returns the median element from data #
OP MEDIAN = ( REF[]INT data )REAL:
IF INT len = ( UPB data - LWB data ) + 1;
INT mid = ( len OVER 2 ) + LWB data;
ODD len
THEN data QUICKSELECT mid
ELSE ( ( data QUICKSELECT ( mid - 1 )
+ data QUICKSELECT mid
)
/ 2
)
FI # MEDIAN # ;
# returns the average of the elements of a #
OP AVERAGE = ( []INT a )REAL:
IF INT len = ( UPB a - LWB a ) + 1;
len < 1
THEN 0
ELSE INT sum := 0;
FOR i FROM LWB a TO UPB a DO
sum +:= a[ i ]
OD;
sum / len
FI # AVERAGE # ;
# END rows.incl.a68 #