Zaradenie a popis

Sekvenčné vyhľadávanie je vyhľadávacia technika na nájdenie danej hodnoty v neutriedenom poli prvkov.
Je ľahko naprogramovateľná a používaná najmä ak počet prvkov medzi ktorými sa vyhľadáva nie je príliš veľký.
Pôvodný algoritmus prináša z hľadiska časovej zložitosti nekonzistentné výsledky – môže sa stať, že hľadaný prvok bude vždy umiestený na konci poľa. Pozmenený algoritmus rieši tento problém náhodným usporiadaním vstupného poľa.

^ TOP

Motivácia a špecifikácia

Máme neutriedené pole A a máme nájsť kde sa v ňom nachádza prvok s hodnotou v.
Vstup: postupnosť n čísel A=<a1, a2,..., a n> a hodnota v.
Výstup: Index i taký, že v=A[i] alebo v=NIL, ak sa v nenachádza v A.

^ TOP

Myšlienka algoritmu

Vstupné pole sa náhodne preusporiada, aby sa zabránilo opakovanému výskytu hľadaného prvku na konci poľa. Následne sa prechádza sekvenčne poľom, kým nenájde hľadaný prvok. Ak taký prvok v poli neexistuje, algorimus po n krokoch skončí a do v zapíše špeciálnu hodnotu NIL.

^ TOP

Vizualizácia

Postupne prebehlo sekvenčné vyhľadávanie, prvok sa našiel.

Sekvenčné vyhľadávanie - nejájdený prvok
Prebehlo sekvenčné vyhľadávanie, ale prvok sa nenašiel.

^ TOP

Zápis algoritmu

  var A: array [1..N]
  zamiesaj(A);  // do poľa A vloží náhodnú permutáciu jeho prvkov
  i:=0;
  repeat
    i:=i+1
  until ((A[i]=v) and (i=N))
  if a[i]<>v then v=NIL;

^ TOP

Vlastnosti algoritmu

Algoritmus má priemernú časovú zložitosť O(n) za predpokladu, že distribúcia prvkov v poli je rovnomerná.
Ak sa v poli nachádza viac prvkov s hľadaným kľúčom, časová zložitosť sa znižuje.

^ TOP

Implementácia a experimentovanie

Computer Science and Software Engineering, University of Canterbury, New Zealand
Java applet na pokusy s sekvenčným vyhľadávaním.
http://www.cosc.canterbury.ac.nz/mukundan/dsal/LSearch.html

Department of Mathematics, Arizona State University, USA
Applet na pokusy so sekvenčným vyhľadávaním.
http://desdemona.la.asu.edu/~mat243/applets/LS/LSApplet.php

^ TOP