It is elegant and a bit faster than the following solution. For
N=15000, it averages about
20%
faster, but it is the difference between
0.28 and
0.22 seconds.
SEQUENTIAL_SEARCH_WITHOUT_SENTINEL:
procedure expose A.
parse arg N, V
do J = 1 to N
if A.J = V then leave
end
return J
|
Now suppose that we have two sorted arrays (in ascending order)
A.1,...,A.M and
B.1,...,B.N of integers which we wish to merge into a third
C. array of
M+N elements. Using sentinels provides a way to write a very simple algorithm (compare with merging without sentinel:
SPARSE_POLYADD).
MERGING: procedure expose A. B. C.
parse arg M, N
Mp1 = M + 1; Np1 = N + 1
if A.M > B.N
then B.Np1 = A.M
else A.Mp1 = B.N
K = 1; L = 1
do J = 1 to N + M
if A.K < B.L
then do
C.J = A.K; K = K + 1
end
else do
C.J = B.L; L = L + 1
end
end
return
|
A FEW OTHER EXAMPLES
Literature
Kruse R. L. Data Structures and Program Design
Prentice Hall International Editions, ISBN 0-13-196049-0.
Sedgewick R., Algorithms
Addison-Wesley, Reading, Massachusetts, 1984
