Kiválasztás (algoritmus)

A kiválasztás egy egyszerű algoritmus, amellyel egy véges (nem feltétlenül numerikus) sorozat – vagy számítástechnikai szóhasználattal élve egy tömb – elemei közül megadunk egyet, amely T tulajdonságú. T egy tetszőleges tulajdonságfüggvényt jelent, egy sorozatbeli elemre nézve lehet igaz vagy hamis. Az algoritmus feltételezi, hogy biztosan van legalább egy ilyen tulajdonságú elem. Sorszám helyett visszaadhatjuk az elem értékét is, de célszerűbb a sorszámot, mivel szükségünk lehet rá (ez alapján az elem is egyszerűen meghatározható).

Az algoritmus

[szerkesztés]

Ez az algoritmus az első T tulajdonságú elem megtalálása után már nem folytatja a keresést. TOMB elemeit 0-tól n-1-ig indexeljük, ha a TOMB n elemű.

Az algoritmus elindulva a 0. indextől (i változó) megvizsgálja az aktuális elemet, hogy megfelelő e, és addig megy míg vagy megtalálja, vagy az adatszerkezet végére nem ér. Ha a SORSZAM = -1, akkor a sorszám változóban marad a -1 érték, tehát nincs ilyen tulajdonságú tömb elem. Amint megtalálja a megfelelő elemet a sorszám értékül kapja az aktuálisan vizsgált elem indexét, és mivel a sorszám innentől kezdve nem -1, így elhagyja a ciklust. Ezt az algoritmust hívjuk lineáris keresésnek. Íme az algoritmus:[1] 

sorszám = -1
i = 0
CIKLUS AMÍG (i < n) és (sorszám == -1) {
    HA T(TOMB[i]) {
        sorszám = i
    }
    i = i + 1
}

Csupán ezt a keresési eljárást folytathatjuk le rendezetlen tömbön, míg mód van a tömböt rendezni, minek folytán már számtalan gyorsabb keresési algoritmusra is lehetőségünk nyílik.

Ezeket a keresési és a rendezési algoritmusok között lehet megtalálni.

Kapcsolódó szócikkek

[szerkesztés]

Jegyzetek

[szerkesztés]
  1. ↑ Programozási alaptétel

Források

[szerkesztés]