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

A. = 1

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

The thorough test examines FACT(N) permutations for N in [1,smallint], where smallint is equal to 5, for example. See Generation of permutation sequences.

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

For a typical example of test see PROGRAM1 in Technique: Universal Unit