Technique: Test Data Sets
The tests all have the same structure: an input is constructed, the routine is called, and the answer is checked for correctness. Target of a test can be debugging of code or empirical study of complexity of the algorithm or comparing one algorithm against others. For example: The suited test data sets to testing the MODIFIND function follow
CONSTANT ARRAY
SORTED ARRAY
do J = 1 to N; A.J = J; end
|
ARRAY OF DISTINCT ELEMENTS
For creating of such an array, we use the SHUFFLE subroutine:
do J = 1 to N; A.J = J; end
call SHUFFLE N
|
ELEMENTS UNIFORMLY RANDOM IN INTERVAL
For creating any input array of elements with values ranging from 0 (minimum) to 100000 (maximum), we use the RANDOM built-in function:
do J = 1 to N; A.J = RANDOM(0, 100000); end
|
For generation of elements with values ranging form 1 to 2147483646, there is the LCG function:
X = 171956486 /* "random" number */
do J = 1 to N; X = LCG(X); A.J = X; end
|
SORTED RANDOM ARRAY I
do J = 1 to N
A.J = RANDOM(1,1000)
end
call QUICKSORT N
|
SORTED RANDOM ARRAY II
A.0 = 0
do J = 1 to N
Jm1 = J - 1
A.J = A.Jm1 + RANDOM(1, 1000)
end
|
ALL PERMUTATIONS
N=5; Median = 3
C. = 1; Pr. = 1
do J = 1 to N; P.J = J; end
C.N = 0
do I = 1 to N; A.I = P.I; end
call MODIFIND N, Median
J = 1
do while J < N
X = 0
do J = 1 while C.J = N - J + 1
Pr.J = \Pr.J; C.J = 1
if Pr.J then X = X + 1
end
if J < N
then do
if Pr.J then K = C.J + X
else K = N - J + 1 - C.J + X
Kp1 = K + 1; W = P.K
P.K = P.Kp1; P.Kp1 = W
do I = 1 to N; A.I = P.I; end
call MODIFIND N, Median
C.J = C.J + 1
end
end
return
|
SHUFFLING ARRAY ACCORDING TO CERTAIN PERMUTATION
Shuffling the array A. according to certain permutation P. of set { 1,...,N}. Shuffling in place
do K = 1 to N
L = P.K
do while L < K; L = P.L; end
W = A.K; A.K = A.L; A.L = W
end
|
The fastest code with a temporary array follows
do K = 1 to N
L = P.K; B.K = A.L
end
do K = 1 to N
A.K = B.K
end
|
|
