5. Tömbök

Egy algoritmusban számos értéket kell nyílván tartanunk változók segítségével. Ha azonban minden értéket egyszerűen egy külön változóban tárolunk, az sokszor elég nehézkessé teszi az adatok kezelését. Gondoljunk például egy futó versenyre, ahol a különböző rajtszámmal induló versenyzők pontszámait szeretnénk eltárolni az alábbi módon:

   No_one = 92
   No_two = 88
   No_three = 43
   No_four = 95
   No_five = 74
   ...
   No_seventynine = 29
   No_eighty = 56

Ebben az esetben elég fárasztó lenne megírni azt az algoritmust, amely megmondja, hogy átlagosan hány pontot értek el a versenyzők. A legtöbb pontot elért versenyző pontszámának meghatározása pedig már gyakorlatilag kivitelezhetetlen. Ilyenkor 80 darab if utasításra lenne szükségünk, ahol mindegyik feltétel 79 logikai részfeltételt tartalmazna.

   if No_one>No_two AND No_one>No_three AND ... No_one>No_eighty then
      legtobb = No_one
   endif
   if No_two>No_one AND No_two>No_three AND ... No_two>No_eighty then
      legtobb = No_two
   endif
   ...
   if No_eighty>No_one AND No_eighty>No_two AND ... AND No_eighty>No_seventynine then
      legtobb = No_eighty
   endif
   output "A legmagasabb pontszám: ", legtobb

Hasonló helyzetekben egy tömb nevű eszköz használata jelentősen megkönnyíti a programozó munkáját. A tömb azonos jellegű, összetartozó értékek sorozata, ahol az egyes értékekre egy egész jellegű sorszámmal hivatkozhatunk. Ez az ún. index. Az egyes valós programozási nyelvek a tömbök indexelése szempontjából két csoportot alkotnak. Vannak olyan nyelvek, amelyekben a tömb első elemének az indexe 1 az emberi logikának megfelelően, míg más nyelvek esetén a legelső elemre a 0 indexszel kell hivatkozni, mert ez előnyös a számítógép számára. Az olvasó által hamarosan megismerendő nyelvek (C, Java) az utóbbi technikát használja, így didaktikailag célszerű ebben a jegyzetben is 0-val kezdeni a tömbök indexelését pszeudokódban. A tömböknek - akárcsak a változóknak - van nevük. Az adott elem indexét mindig közvetlenül a tömb neve után elhelyezett szögletes zárójelben tüntetjük fel. Az előbbieknek megfelelően, ha van egy pontok nevű tömbünk, amely N darab értéket tartalmaz, akkor az első elemre pontok[0] alakban hivatkozhatunk, míg az utolsóra pontok[N-1] formában.

A tömbök használatával a fenti átlag versenypontszám meghatározás jóval egyszerűbbé válik. Persze most is azzal kell kezdenünk, hogy eltároljuk a pontszámokat.

   pontok[0] = 92
   pontok[1] = 88
   pontok[2] = 43
   pontok[3] = 95
   pontok[4] = 74
   ...
   pontok[78] = 29
   pontok[79] = 56

Amennyiben az értékeket nem akarjuk beleégetni az algoritmusba, hanem menet közben szeretnénk bekérni a felhasználótól, akkor azt is könnyen megtehetjük tömbök esetén. Először is meg kell tudnunk hány értéket akar megadni a felhasználó, majd egy ciklussal végig kell mennünk a tömb elemein folytonosan inkrementálva egy indexként használandó változót és közben bemenettel feltöltve az adott tömbelemet.

   output "Hány versenyző van?"
   input elemszam
   index = 0
   while index <= elemszam-1 do
     input pontok[index]
     index = index+1
   enddo
   output "A pontszámok tárolása kész."

Ha ezután az összpontszámot kell meghatároznunk, nem egy 80 tagú összeget kell kézzel leírnunk. Ehelyett egy ciklussal végig kell mennünk a tömb elemein, közben pedig az aktuális tömbelem értékét egy részösszeget tartalmazó változóhoz kell hozzáadnunk. A ciklus végén a számok összegét természetesen elosztjuk a tömb elemeinek számával és a hányadost kiíratjuk.

   index = 0
   osszeg = 0
   while index <= elemszam-1 do
     osszeg = pontok[index]
     index = index+1
   enddo
   output "Átlag: ", osszeg/elemszam

Mi a helyzet a legmagasabb versenypontszám megtalálásával? Ez egyfajta szélsőérték keresési probléma, ami gyakran előfordul az informatikában. Egy tömböt tartalmazó pszeudokódban megfogalmazott algoritmus sokkal gyorsabban megírható, mint a korábbi 6320 darab kézzel megadott összehasonlítást tartalmazó verzió. Minden elemet csak egyszer vizsgálunk meg egy ciklusban, miközben tároljuk az eddig talált legnagyobb értéket. Az alábbi megoldásban és az összes további mintakódban feltételezzük, hogy a tömbök már fel vannak töltve értékekkel.

   elemszam = 80
   maximum = pontok[0]
   index = 1
   while index <= elemszam-1 do
     if pontok[index]>maximum then
        maximum = pontok[index]
     endif
     index = index+1
   enddo
   output "A legagasabb pontszám: ", maximum

Az algoritmus elején azt mondjuk, hogy az első elem az eddig talált legnagyobb érték. Ezután minden további elemet összehasonlítjuk a maximum változó értékével, és ha az aktuális érték nagyobb, akkor felülírjuk vele a skalár változó értékét.

Gyakran találkozhatunk egy olyan problémával, ami csak kicsit tér el az előzőtől, amikor is nem a szélsőérték érdekel bennünket, hanem annak a helye. Esetünkben például az, hogy milyen sorszámú (indexű) versenyző érte el a legtöbb pontot. Az előző algoritmuson csak kis változást kell eszközölnünk. Ahelyett, hogy magát az eddigi legnagyobb pontszámot tárolnánk (maximum), a legnagyobb értéket tartalmazó tömbelem indexét (nyertes) tároljuk.

   elemszam = 80
   nyertes = 0
   index = 1
   while index < elemszam do
     if pontok[index]>pontok[nyertes] then
        pontok[nyertes] = pontok[index]
     endif
     index = index+1
   enddo
   output "A legmagasabb pontszámú versenyző: ", nyertes+1
   output "Az ő pontszáma: ", pontok[nyertes]

Felhívnám a figyelmet arra, hogy az i sorszámmal rendelkező versenyző pontszáma a tömb i-1 indexű elemében van eltárolva. Tehát míg a pontszám kiírásához a nyertes változó értékét használjuk, addig a versenyző (emberi logikájú) sorszámának kiírásához a nyertes+1 kifejezés szükséges.

5.1. Keresés

Mint látható a tömbök használata számos probléma megoldása esetén előnyös lehet. A számítógéppel megoldandó problémák jelentős részében felmerül az a részfeladat, hogy el kell döntenünk, hogy egy érték el van-e már tárolva a tömbben. Néha az is fontos lehet, hogy megtudjuk a már tárolt érték a tömb milyen indexű elemében található meg. Ezt a problémacsoportot nevezzük keresés-nek. Számos megoldás ismert a problémára ezek közül az informatikai alap algoritmusok közül néhányat mutat be ez a fejezet.

Tételezzük fel tehát, hogy van egy A nevű N darab értékkel feltöltött tömbünk, amelyben keressük az X értéket. Az első ötlet, amely valószínűleg eszünkbe jut az, hogy sorban minden tömbelemet összehasonlítunk a keresett értékkel, amíg egyezést nem találunk. Ezt pszeudokóddal így oldhatjuk meg:

   i = 0
   while i<N AND A[i]!=X do
     i = i+1
   enddo
   if i==N then
     output "A keresett érték nincs a tömbben."
   else
     output "A keresett érték indexe: ", i
   endif

A ciklus feltétele egy összetett logikai kifejezés. Az ismétlés addig folytatódik, amíg van még hátra vizsgálandó tömbbelem és az aktuális elem nem a keresett érték. (Mindkét feltételnek egyszerre teljesülnie kell a logikai AND operátor miatt.) Ha elhagytuk a ciklust, akkor ennek két oka lehet. Egyik szerint az i index értéke elérte az elemek számát, azaz már megvizsgáltuk az N-1-dik (utolsó) elemet is. Ebben az esetben tudjuk, hogy a keresett X érték biztosan nem volt benne a tömbben. A másik ok az, hogy megtaláltuk az adott értéket az N-1-dik vagy korábbi cellában. Ekkor az i értéke éppen az X tárolási helyének indexe. Ezt az algoritmust nevezzük teljes keresés-nek.

Sok elem esetén az algoritmus végrehajtási idejének jelentős részét a ciklus teszi ki. Általános esetben a fenti ciklus N/2 alkalommal fut le vagyis a végrehajtási idő a tömb elemeinek számával egyenes arányosságban nő. Ebben az algoritmusban a ismétlési feltételben két összehasonlítási műveletet is el kell végezni ismétlésenként, azaz átlagosan N darabot.

Mindig léteznek alternatív algoritmusok. Ezeknek természetesen minden körülmények között ugyanazt az eredményt kell szolgáltatniuk, azonban bizonyos szempontokból egyik vagy másik előnyösebb lehet a többinél. Ennek szemléltetésére nézzük meg egy másik megoldását az előbbi keresési problémának. Támadhat egy olyan ötletünk, hogy a keresett elemet egy plusz lépéssel az algoritmus elején tegyük be a tömb utolsó eleme után. Ezután hajtsuk végre a keresést! Ilyenkor ez elemet mindenképpen megtaláljuk. A kérdés az, hogy hol. Az utolsó eredeti elem után vagy már korábban? Lássuk az ezt megvalósító pseudokódot!

   A[N] = X
   i = 0
   while A[i]!=X do
     i = i+1
   enddo
   if i==N then
     output "A keresett érték nincs a tömbben."
   else
     output "A keresett érték indexe: ", i
   endif

A változás látszólag elhanyagolható, ráadásul még egy plusz utasítássort is alkalmaznunk kell. Melyik a hatékonyabb módszer? Általános esetben itt is gyakorlatilag N/2 lépés után találjuk meg az értéket. Azonban a ciklus feltétele most csak egyetlen egyszerű logikai kifejezést tartalmaz, vagyis általános esetben itt csak N/2 összehasonlítást végzünk az ismétlések során. Ez fele annyi, mint az előző algoritmus esetén, határozottan gyorsítva ezzel az algoritmus végrehajtását, még a plusz egy utasítás ellenére is. Ezt tehát azáltal érhetjük el, hogy egy ún. őrszemet (a tömb végére helyezett X értéket) használunk arra, hogy a túlindexelést elkerüljük (azaz ne hajtsuk végre a ciklust nem létező tömbelemekre).

Eddig nem volt semmilyen kikötésünk a tömbre vonatkozóan. Azonban ha szűkítjük a tervezett algoritmusunk alkalmazási körét, akkor érdekes új lehetőségeket kell megfontolnunk. Tételezzük fel, hogy a tömbünk rendezett, azaz minden elemet nála nem nagyobb elemek előznek meg és nála nem kisebb elemek követnek. Másképp fogalmazva: az utolsó elem kivételével bármely i indexű elemre igaz az, hogy A[i]<=A[i+1]. (A növekvő rendezettség helyett természetesen a csökkenő rendezettséget is választhattuk volna.) Miért másabb a feladat ebben az esetben? A különbség megértéséhez tekintsük a következő esetet! Keressük a 27 értéket egy növekvő rendezettségű tömbben! Amennyiben a tömb egyik eleme 394, akkor biztosak lehetünk benne, hogy a hátralévő elemek között biztosan nem fordulhat elő a keresett érték, befejezhetjük a keresést. Írjuk meg a keresés pszeudokódját erre az esetre, feltételezve tehát, hogy a tömb rendezett!

   i = 0
   while i<N AND A[i]<X do
     i = i+1
   enddo
   if i==N OR A[i]>X then
     output "A keresett érték nincs a tömbben."
   else
     output "A keresett érték indexe: ", i
   endif

Mint látható a ciklusból kétféleképpen léphetünk ki. Vagy túllépünk az utolsó elemen is (i==N) vagy a keresett értéknél nem kisebb tömbelemet találunk (A[i]>=X). Ezek alapján meg tudjuk állapítani, hogy megtaláltuk-e a keresett értéket vagy nem.

Extrém esetben előfordulhat, hogy a ciklusmagba egyszer sem lépünk be, azaz már az első tömbelem nagyobb, mint a keresett érték. Általános esetben elmondhatjuk, hogy bár a keresési idő egyenesen arányos a tömb elemeinek számával, mégsem szükséges mindig minden tömbelem megvizsgálása. Ez hatékonyabb, mint a teljes keresés, aminek az az ára, hogy csak rendezett tömb esetén alkalmazható. Ennek az algoritmusnak a neve lineáris keresés, utalva arra, hogy sorrendben keresünk. A ciklus feltételében szereplő i<N logikai kifejezés akkor igazán hasznos, ha az összes tömbelem kisebb, mint a keresett érték. Ennek a helyzetnek az elkerülésére itt is használhatjuk az őrszem logikáját eltárolva X értékét a tömb N indexű pozíciójába. Ekkor a ciklusfeltétel csak egy egyszerű logikai kifejezést fog tartalmazni, tovább gyorsítva az algoritmust.

Bizonyára mindenki ismeri azt a játékot, amikor az A játékos gondol egy számra 1 és 100 között, a B pedig próbálja kitalálni melyik egész számra gondolt a társa. Mindezt úgy teszik, hogy B mond egy tippet, amire A megmondja, hogy a tipp nagyobb-e vagy kisebb, mint a kigondolt szám vagy esetleg megegyezik-e vele. Mindezt addig ismétlik, amíg B ki nem találja a számot. Egy okos játékos nem véletlenszerűen tippelget. Első tippje az intervallum közepén lévő érték. Ha például a gondolt szám ennél nagyobb, akkor tudja, hogy az csak az intervallum második felében lehet. Következő tippjével ezt a szűkebb intervallumot felezi meg, és így tovább. A játék mindig nagyon hamar véget érhet.

Ehhez nagyon hasonló módszert alkalmazhatunk abban az esetben, ha egy rendezett tömbben keresünk egy konkrét értéket. Persze a tömbelemek nem biztos, hogy egyenközűen elhelyezkedő egész értékek, de a számuk mindig véges egész így egy elem kiválasztásával mindig szét tudjuk osztani a tömb egy folytonos részét két közel azonos méretű intervallumra. Ezek közül pedig mindig csak az egyik rejti a keresett értéket. Ennek a ciklikus intervallum felezésen alapuló algoritmusnak a neve bináris keresés. Pszeudokód segítségével a következőképpen reprezentálhatjuk:

   first = 0
   last = N-1
   if N%2==0 then
     middle = N/2
   else
     middle = (N-1)/2
   endif
   while A[middle]!=x AND first<=last do
     if A[middle]>x then
       last = middle-1
     else
       first = middle+1
     eldif
     if (last+first)%2==0 then
       middle = (last+first)/2
     else
       middle = (last+first-1)/2
     endif
   enddo
   if first>last then
     output "A keresett érték nincs a tömbben."
   else
     output "A keresett érték indexe: ", middle
   endif

A keresés során egy folyton szűkülő intervallumot vizsgálunk. Az intervallum első elemének az indexe first, az utolsóé last. A tömbelem vizsgált folytonos szakaszának közepét a tömb middle indexű eleme jelöli. Egy 7 elemű tömbben (ahol ez elemek indexei 0-tól 6-ig terjednek) a középső elem indexe 3. Egy páros számú elemet tartalmazó tömbben nincs igazi középső elem. Amennyiben N=6 (azaz indexek 0-tól 5-ig), akkor az middle=2 és az middle=3 is jó választás lehet. (A bemutatott algoritmus az utóbbi választással él, azaz az middle indexű elem előtt eggyel több eleme van a tömbnek, mint utána.) Az intervallum kezeléséhez szükséges három segédváltozó (first, middle, last) a pszeudokód első 7 sorában kap kezdőértéket.

Az algoritmus jelentős része egy ciklus, ami addig ismétlődik, amíg meg nem találjuk a keresett értéket vagy az intervallum nulla elemű nem lesz (amikor is az első elem indexe nagyobb, mint az utolsóé). A ciklus magjában lévő első feltételes utasítás a vizsgált intervallum méretét csökkenti vagy az első elem indexét vagy az utolsó elem indexét megváltoztatva. Ezt a keresett érték és a középső elem viszonya dönti el. Ezután meg kell határozni az új lerövidült intervallum közepének választott elem indexét. Ezt végzi el a második elágaztató utasítás.

Amikor hamissá válik a ciklus összetett logikai kifejezése és elhagyjuk a ciklust, akkor tudnunk kell, hogy ez miért is történt meg. Erre utal a 20. sor feltétele. Ha üres az intervallumunk (first>last), akkor nincs meg a keresett elem, különben az aktuális intervallum közepén kell legyen, azaz az A tömb middle indexű eleme az.

Bizonyára észrevette a kedves olvasó, hogy ez az algoritmus sokkal bonyolultabb, a pszeudokód pedig sokkal hosszabb, mint például a teljes keresés esetén. Miért éri meg a bináris keresés használata a fejlesztésbe fektetett energiát? Tudnunk kell, hogy mondjuk legrosszabb esetben hány iterációs lépés szükséges X megtalálásához. Minden ismétlés során durván feleződik az intervallum hossza. Ha mondjuk egy 1000000 elemet tartalmazó rendezett tömböt használunk, akkor 21 ismétlés biztosan elég (mivel a kettő huszadik hatványa több, mint egymillió). Emlékezzünk vissza, hogy teljes kereséssel legrosszabb esetben egymillió ismétlés szükséges. Ez az óriási keresési idő különbség egyértelművé teszi, hogy megéri ügyes programozónak lenni.

5.2. Rendezés

A lineáris és bináris keresés gyorsaságának ára van. A tömb elemeinek rendezettnek kell lennie, tehát ahhoz, hogy alkalmazni tudjuk őket, először rendeznünk kell a tömböt. Tegyük fel, hogy növekvő rendezettségre van szükségünk, azaz bármely elem esetén igaznak kell lennie annak az álltásnak, hogy előtte nem lehetnek nála nagyobb elemek, mögötte pedig nem lehetnek kisebb elemek. Ha a tömb eredetileg véletlenszerű sorrendben tartalmazza az értékeket, akkor nekünk kell rendeznünk őket.

Az első ötlet az lehet, hogy hozzunk létre egy azonos méretű tömböt, majd keressük meg az eredeti tömb legkisebb elemét (a korábbi szélsőérték kereséssel) és azt tegyük az új tömb első helyére, a második legnagyobb elemet a második helyre és így tovább. Ez viszonylag egyszerű algoritmus, de szükségünk van egy új tömbre, azaz kétszer akkora lesz majd a programunk memóriaigénye. Általában emiatt helyben rendezzük az elemeket, azaz csak az eredeti tömbben dolgozunk és értékpárok megfelelő felcserélgetésével érjük el a rendezettséget.

Hogyan tudunk két értéket megcserélni? Tegyük fel, hogy az A változó értéke 5, a B változóé pedig 7. Írni akarunk egy algoritmust, aminek a hatására A értéke 7 lesz, B pedig 5 lesz. A legtöbb kezdő az alábbi pszeudokódot írná:

   A = B
   B = A

Értelmezzük ezt a két utasítást lépésenként! Az első azt jelenti, hogy B értéke, vagyis a 7 tárolódjon el az A változóba. Ekkor a korábbi tartalmat, vagyis az 5-öt felülírjuk az A változóban, B pedig változatlan marad. Vagyis mindkét változóban 7 lesz, elvesződött az egyik érték és azt már a második utasítás sem tudja visszaállítani. Tehát ez egy hibás lépéssorozat.

Egy jó ötlet lehet az, ha az egyik változó értékét ideiglenesen elmentjük egy új változóba és csak ezután írjuk felül a másik változó tartalmával, majd az új változó értékét másoljuk át a B változóba. Ezt teszi az alábbi pszeudokód.

   C = A
   A = B
   B = C

Ez a három lépés egy segédváltozó segítségével tehát képes felcserélni két változó értékét.

Átmeneti segédváltozó nélkül is megcserélhetjük az értékeket, csak egy kis trükkre van szükségünk. Nézzük az alábbi szintén háromlépéses megoldást pszeudokódban!

   A = A+B
   B = A-B
   A = A-B

Kövessük nyomon hogyan alakul az egyes változók értéke az utasítások végrehajtása során! Először A értéke 12 lesz, majd a második utasítás hatására B megkapja az 5-ös értéket, végül A 7-et kap értékül. Valóban felcserélődtek az értékek. Bár ez a megoldás nem igényel segédváltozót, az első megoldás szélesebb körben alkalmazható (és egyszerűbb is).

Ezek után már készen állunk elemcserék segítségével történő tömbrendezésre. Az egyik legkézenfekvőbb ötletet valósítja meg az ún. szélsőérték kiválasztásos rendezés. A növekvő sorba rendezést mondatszerű formában a következőképpen adhatjuk meg.

1. Vedd a teljes tömböt!

2. Keresd meg a vizsgált elemek közül a legkisebbet!

3. Cseréld meg a legkisebb elemet és a vizsgált elemek közül a legelsőt!

4. A vizsgált elemek közül hagyd ki a most előre helyezett legkisebbet!

5. Ha nincs több vizsgált elem, akkor kész vagy, különben folytasd a 2. lépéssel!

Ha alaposan megnézzük, ez a lépéssorozat már tartalmazz ismerős részeket. A legkisebb elem megtalálása nem más, mint egy szélsőérték keresés, ahol a legkisebb/legnagyobb elem értékét és indexét keressük meg. Ezt már korábban megírtuk, most csak újra fel fogjuk használni. (Jó példa ez az algoritmusok beágyazására.) A fenti algoritmusban a minimális elem helyét kell megtalálnunk. Emellett vegyük észre, hogy az ismétlések során nem mindig ugyanazokkal az elemekkel foglalkozunk. Kezdetben természetesen a teljes tömböt kell szem előtt tartanunk, de később az eredeti tömb végén lévő pásztázandó terület folyamatosan zsugorodik. A tömb elején eközben fokozatosan növekszik, az a szakasz, ahol az elemek már rendezetten helyezkednek el. Ez alapján rakjuk össze lépésről lépésre az algoritmus pszeudokódját!

A vizsgálandó szakasz kezdődjön a 0 indexű elemmel!

   start = 0

A korábban már megismert módon keressük meg a legkisebb elem helyét (indexét)!

     min_i = start
     i = start+1
     while i<N do
       if A[i]<A[min_i] then
         min_i = i
       endif
       i = i+1
     enddo

Tehát min_i tárolja a szélsőérték indexét. Ezt az elemet meg kell cserélnünk a vizsgált szakasz első elemével, aminek az indexe a start.

     tmp = A[start]
     A[start] = A[min_i]
     A[min_i] = tmp

Közben egy segédváltozót (tmp) is használunk. A legkisebb elem tehát a szakasz elejére került, aminek indexe a start változóban van. Az összes ez utáni elem még rendezetlen. Ezért a szélsőérték keresést és az elemcserét többször is meg kell ismételnünk, folyton növelve a rendezetlen szakasz kezdetének indexét. Ez utóbbi ciklust addig kell folytatni, amíg legalább 2 elem van a rendezetlen szakaszban (utoljára úgyis a legnagyobb marad). A teljes pszeudokód tehát így néz ki:

   start = 0
   while start<N-1 do
     min_i = start
     i = start+1
     while i<N do
       if A[i]<A[min_i] then
         min_i = i
       endif
       i = i+1
     enddo
     tmp = A[start]
     A[start] = A[min_i]
     A[min_i] = tmp
     start = start+1
   enddo

Bizonyára észrevette az olvasó, hogy van egy belső ciklusunk a szélsőérték helyének keresésére, ami egy külső ciklus magjában fordul elő. A külső ciklus majdnem N-szer fut le, míg a belső átlagosan N/2 alkalommal hajtódik végre minden egyes külső ciklusmagban. Összességében tehát elmondhatjuk, hogy a belső ciklus magjában lévő elempár összehasonlítás N(N-1)/2 alkalommal értékelődik ki. A végrehajtási idő tehát négyzetesen függ a rendezendő tömb méretétől.

Most nézzünk a tömb elemeinek rendezésére egy alternatív algoritmust, amely tehát teljesen más elvek szerint működik, mégis ugyanazt a rendezett tömböt adja eredményül. A most bemutatásra kerülő módszer neve buborék rendezés. Itt is cserélgetünk elemeket, de azok mindig szomszédos elemei a tömbnek. Először menjünk végig tömb összes szomszédos értékpárján, és ha az elempáros nagyobbik tagja megelőzi a kisebbet (növekvő rendezés esetén) akkor megcseréljük őket. Ennek hatására a nagy értékű elemek átlagosan kicsit hátrébb kerülnek, a kisebbek pedig kicsit előrébb. Amikor végére érünk ennek az ismétlésnek, akkor a tömb még nem rendezett, csak azt tudhatjuk biztosan, hogy a legnagyobb elem a tömb végére került. Ha ezt az egész ciklust még egyszer megismételjük, akkor a második legnagyobb elem is a helyére kerül. Ha pedig N-1 alkalommal hajtjuk végre a ciklust a tömb rendezetté válik. Pszeudokód segítségével tehát a rendezés így is kinézhet:

   i = 1
   while i<=(N-1) do
     j = 0
     while j<(N-1) do
       if A[j]>A[j+1] then
         tmp = A[j]
         A[j] = A[j+1]
         A[j+1] = tmp
       endif
       j = j+1
     enddo
     i = i+1
   enddo

Ebben az algoritmusban a j indexű elemnek és a rákövetkezőjének (A[j+1]) összehasonlítása (N-1)(N-1) alkalommal történik meg. Ez több, mint a kiválasztásos rendezés esetén, azonban ezen még sokat javíthatunk, ha nyilvánvaló lehetőségeket figyelembe veszünk. A legnagyobb elemek folyamatosan a tömb végére kerülnek, azaz mindig lesz egy szakasz, ami rendezett, azaz a következő ciklusban már nem is kell átnéznünk. Változtassuk meg a külső ciklus számlálóját! Ne azt tárolja, hogy hányadik iterációnál járunk, hanem azt, melyik indexű helyen ér véget a tömb elején lévő rendezetlen szakasz. Így a ciklusszámláló az idő előrehaladtával folyamatosan csökkenni fog. Emellett a belső ciklusban nem kell mindig végigmenni az összes elempáron csak a rendezetlen szakaszon, aminek a végét a új külső ciklusszámlálónk tárolja. Így a belső ciklus egyre rövidebb, ahogy haladunk a külső ismétléssel. A módosítások eredménye ez a pszeudokód:

   i = N-1
   while i>0 do
     j = 0
     while j<i do
       if A[j]>A[j+1] then
         tmp = A[j]
         A[j] = A[j+1]
         A[j+1] = tmp
       endif
       j = j+1
     enddo
     i = i-1
   enddo

Ezzel az érték összehasonlítások száma lecsökkenhet annyira, mint kiválasztásos rendezés esetén. Sőt ezt tovább is csökkenthetjük még egy kis trükkel. Ha egyszer végighaladunk a belső ciklus összes lépésén és közben egyszer sem volt szükséges elemcsere, akkor későb sem lesz rá szükség, mert a tömb hamar rendezetté vált. Így néha korábban is befejezhetjük a rendezést egy módosított algoritmusban.

Több rendezési algoritmus bemutatását a jegyzet terjedelme nem teszi lehetővé, de érdemes megemlíteni, hogy számtalan további népszerű rendezési algoritmus használatos. Példaként néhány: beszúrásos rendezés, gyorsrendezés, kupac rendezés, stb. A helyben rendezésekről általában elmondhatjuk, hogy a tömb méretének duplájára növelésénél a szükséges műveletek száma több, mint duplájára növekszik. Jobb esetben is végrehajtási idő az N log(N) kifejezéssel lesz arányos. Ha nem kell ragaszkodnunk ahhoz, hogy mennyi segédváltozót és segédtömböt használunk, akkor egy tömb rendezése lineáris idejű is lehet. Ilyen algoritmus például a számjegyes (radix) rendezés, de ez túlmutat a tárgy keretein.

5.3. Több dimenziós tömbök

Az eddig alkalmazott tömbjeink ún. egydimenziós tömbök más szóval vektorok voltak. Ez azt jelentette, hogy egyetlen indexszel el tudtuk érni az összes egymás utáni elemet. Vannak azonban olyan problémák, ahol szükség lehet ennél összetettem eszközre. Ilyen például a mátrix, ami elemek egy kétdimenziós, azaz sorokba és oszlopokba szervezett elrendezése. Az egyes elemekre két egymástól független indexszel hivatkozhatunk, amelyek megmondják melyik sornak és melyik oszlopnak a metszetében van a bizonyos elem. Jelölhetjük például így a 9. sorban és 3. oszlopban lévő elemet: M[8][2] (ne feledjük, az indexek mindkét dimenzióban 0-tól indulnak). A többdimenziós tömbök használatát bemutathatjuk egy olyan pszeudokóddal, amely létrehoz egy egységmátixot, azaz értékek egy 5x5-ös négyzetes elrendezését, ahol a főátlóban kizárólag 1 szerepel, míg az összes többi mátrixelem 0.

   sor = 0
   while sor<5 do
     oszlop = 0
     while oszlop<5 do
       if sor==oszlop then
         M[sor][oszlop]=1
       else
         M[sor][oszlop]=0
       endif
     enddo
   enddo

Lieáris algebrára épülő feladatokban gyakran használhatjuk majd ezt az eszközt.

5.4. Szójegyzék

index

Egy tömb elemeinek eléréséhez használt egész szám. Gyakorlatilag, mintha az adott elem sorszáma lenne az adott tömbön belül. Számos programozási nyelv az indexelést nullával kezdi, azaz a tömb első elemének indexe 0. Ezt a logikát használjuk mi is.

keresés

Az informatikai alapalgoritmusok azon csoportja, amelynek keretében egy adatról el kell dönteni, hogy szerepel-e egy adatszerkezetben (tömbben), és ha igen, akkor hol.

mátrix

Értékek téglalapszerű elrendezése sorokban és oszlopokban, ahol minden elem két index segítségével érhető el.

rendezés

Egy olyan lépéssorozat, aminek hatására egy tömb elemei átrendezéssel növekvő vagy csökkenő sorrendbe kerülnek. Számos különböző rendezési algoritmus közismert: szélsőérték kiválasztásos rendezés, beszúrásos rendezés, buborékrendezés, gyorsrendezés, kupacrendezés, radix rendezés, shell rendezés.

szélsőérték keresés

Ebben a témakörben a tömbben tárolt legnagyobb vagy legkisebb értéket megkeresését jelenti. Gyakran nem is magát az értéket, hanem annak helyét (indexét) keressük.

tömb

Több azonos jellegű mennyiség tárolása egy egységben úgy, hogy minden adatelemre egy nem negatív egész számmal, az index-szel hivatkozhatunk.

5.5. Kérdések, feladatok

• Írj le egy algoritmust pszeudokód segítségével, amely 10 darab értéket kér be a felhasználótól és fordított sorrendben kiíratja őket!

• Írj le egy algoritmust pszeudokód segítségével, amely egy A nevű N darab értékkel feltöltött tömb legkisebb értékű elemének indexét határozza meg!

• Írj le egy algoritmust pszeudokód segítségével, amely 10 darab számot vár bemenetként és meghatározza az értékek szórását!

• Adott egy A nevű és N elemű tömb, amelynek elemei kizárólag 10-20 zárt intervallumbeli egész számok lehetnek (egy érték akár többször is). Határozd meg a tömb elemeinek móduszát, azaz találd meg a leggyakrabban előforduló elemet (ha több ilyen is van, akkor csak az egyiket)! [S504]

• Írj meg a lineáris keresés algoritmusát őrszem használatával, amely egy A nevű N darab értékkel feltöltött tömbben keresi meg X értékét!

• Írj meg a bináris keresés algoritmusát csökkenő sorrendben rendezett A nevű N elemű tömbre, ahol a keresett értéket inputként várod a felhasználótól!

• Írj egy algoritmust, amely a felhasználótól bekér egy számot, majd ennek az értéknek az összes előfordulását az A nevű N elemű tömbben kicseréli nullára!

• Buborékrendezés segítségével rendezd az alábbi tömböt és rendszeresen írd le a tömb aktuális tartalmát! {92, 32, 4233, -23, 84, 93, 0, 11}

• Járj utána az Internet segítségével, hogy hogyan működik a beszúrásos rendezés és írd meg a pszeudokódját! [S509]

• Gondold át, hogyan gyorsíthatjuk az előbbi algoritmust bináris keresés használatával.

• Adott egy A nevű N darab számértéket tartalmazó tömb és egy B nevű M elemű tömb. Mindkét tömbben az értékek növekvő sorrendbe vannak rendezve. Hozz létre egy C nevű N+M elemű rendezett tömböt az előbbi két tömb elemeinek az összefésülésével! Az algoritmusod legyen hatékony! [S511]