TECHNIKA: ZARÁŽKY

Zarážka je zvláštní prvek dodaný na konec pole či seznamu. Zajistí ukončení cyklu bez nutnosti testovat, zda byly prozkoumány všechny prvky pole. Jednoduchým příkladem využití zarážky je algoritmus SEQUENTIAL_SEARCH:
 

SEQUENTIAL_SEARCH: procedure expose A.
parse arg N, V
Np1 = N + 1; A.Np1 = V
do J = 1 until A.J = V; end
return J

 

Je bezesporu elegantní a trošku rychlejší než obvyklé řešení. Pro N=15000 v průměru o 20%, ale hovoříme tu o rozdílu mezi 0.28 sec a 0.22 sec:

 

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

 

Předpokládejme, že máme dvě vzestupně uspořádaná celočíselná pole A.1,...,A.M a B.1,...,B.N, která chceme sloučit do jediného vzestupně uspořádaného pole C. rozsahu M+N. Užití zarážky vede k velmi jednoduchému algoritmu (srovnej se slučováním bez zarážky u 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

 

NĚKTERÉ DALŠÍ PŘÍKLADY

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


Obálka Obsah Index Hlavní stránka

změněno 30. července 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.