FIND

PROBLÉM
Nalezení K-tého nejmenšího z N prvků: Je dáno pole A., obsahující N (různých) prvků, a přirozené číslo K, 1<=K<=N, určete K-tý nejmenší prvek A. a přerovnejte pole tak, aby tento prvek byl v A.K a všechny prvky s indexy menšími než K neměly větší hodnotu než A.K a všechny prvky s indexy většími než K neměly hodnotu menší než A.K.

ALGORITMUS
Autorem algoritmu Find je C. A. R. Hoare. Předložil jako první algortimus s průměrnou časovou složitostí O(N). V nejhorším případě má jeho algoritmus složitost O (N**2).

PRAXE
Algoritmy MODIFIND a SELECT jsou téměř vždy rychlejší než FIND. SELECT potřebuje méně operací porovnání než MODIFIND; MODIFIND potřebuje méně operací výměn prvků než SELECT. Následující tabulka uvádí průměrnou dobu výpočtu 10. testů naměřenou algoritmům FIND, MODIFIND, a SELECT při určování mediánu z 10000 prvků - řetězců délky L<=6 (jen čísla), L<=7, L<=500:

 

Porovnání algoritmů
Algoritmus L <= 6 L <= 7 L <= 500
FIND 0.957 1.475 4.104
MODIFIND 0.929 1.212 1.476
SELECT 0.602 0.828 0.985

 

IMPLEMENTACE
Jednotka: vnitřní funkce
 
Globální proměnné: pole A. libovolných prvků
 
Parametry: přirozené číslo N - počet prvků v A., přirozené číslo K, 1<=K<=N
 
Výsledek: Přerovnání vstupního pole tak, že v A.K je uložena tatáž hodnota, jakou bychom tu našli, kdyby bylo pole utříděno, L<=I<=K implikuje A.I<=A.K, a K<=I<=R implikuje A.I>=A.K
 
Vrací: A.K
 

FIND: procedure expose A.
parse arg N, K
L = 1; R = N
do while L < R
  X = A.K; I = L; J = R
  do until I > J
    do while A.I < X; I = I + 1; end
    do while X < A.J; J = J - 1; end
    if I <= J
      then do
        W = A.I; A.I = A.J; A.J = W
        I = I + 1; J =J - 1
      end
  end
  if J < K then L = I
  if K < I then R = J
end
return A.K

 

SOUVISLOSTI
Nalezení K-tého nejmenšího prvku
     Minimum a maximum současně
     Modifind
     Select

Literatura
Hoare C. A. R. Proof of a Program: FIND
CACM, Vol 14, No. 1, January 1971, pp. 39-45
Wirth N. Algorithms and data strucure
New Jersey, Prentice Hall, Inc., Engelwood Cliffs, 1986
Zábrodský V. Variace na klasické téma
Elektronika, č. 6, 1992, s. 33-34
Zábrodský V. FIND, SELECT, MODIFIND


Obálka Obsah Index Hlavní stránka

změněno 11. září 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.