• Szerző: Sallai András
• Copyright © Sallai András, 2011, 2014
• Licenc: CC BY-SA 4.0
• Web: https://szit.hu

Ez megegyezik a szimpla „Mondatszerű leírások résszel, azzal a különbséggel, hogy a Pascal nyelvhez igazodva, mindenhol 1-es indexel kezdődnek a tömbindexek.

A programozási tételek gyakran használt algoritmusokat takarnak. Ezeket az algoritmusokat általában tömbökön hajtjuk végre.

Az itt található feladatok t[] tömbön kerülnek végrehajtásra, a t[] tömbnek pedig n darab eleme van. Ahol több tömbbel dolgozunk ott az első tömb a[], amelynek n eleme van, a második tömb b[], amelynek m elem van. Harmadik tömb neve például c[]. Az a[] tömb ciklus változója szokásosan i, a b[] tömbbé j, a harmadik c[] tömbbé k.

A tömbök indexelését 1-gyel kezdem. Az értékadást egy kettőspont és egy darab egyenlőségjel (:=) jelenti, az egyenlőség vizsgálatot egy darab egyenlőségjel (=) jelzi, a nem egyenlőt egy kisebb-mint és egy nagyobb-mint jel jelzi (<>).

(A rendezés tételtelek egyelőre a pascal szintaxis szerint vannak leírva).

osszeg = 0
ciklus i = 1 .. n
    osszeg = osszeg + t[i]
ciklus vége
ki osszeg

Adott feltételek alapján a tömb bizonyos elemeit megszámolom.

Pl.: Megszámoljuk mennyi negatív szám van a tömbben

szamlalo = 0
ciklus i = 1 .. n
    ha t[i] < 0 akkor 
        szamlalo = szamlalo + 1
    ha vége
ciklus vége
ki szamlalo

Szeretnénk tudni, hogy egy érték megtalálható-e egy tömbben.

  van = 0
  ciklus i = 1 .. n
    ha tomb[i] = keresett_ertek akkor
        van = 1
    ha vége
  ciklus vége

A fenti megoldásnak az a hátránya, ha keresett értéket megtaláltuk, a ciklus akkor is tovább megy. Erre megoldást ad, ha a olyan ciklus állítunk munkába, amelyet akkor szoktunk használni, ha nem tudjuk meddig kell menni. Itt pedig ezzel van, dolgunk. Hogy hol lesz a keresett érték nem tudjuk, de ha meg van, le kell állni. Kell egy feltétel, hogy a ciklus addig menjen amíg nincs meg. Egy másik pedig, miszerint a ciklus addig menjen amíg van adat (nincs vége a tömbnek).A következő algoritmus megvalósítja ezt:

i = 1
ciklus amíg i<=n és t[i]<> ker
    i=i+1
ciklus vége

Ha i<=n akkor
    ki "Van ilyen" 
különben
    ki "A keresett érték nem található"
ha vége

A ker változó tartalmazza a keresett értéket, a tömb 0-tól van indexelve!

Az adott elem a tömb hányadik helyén van

i = 1
ciklus amíg tomb[i] <> ker
    i = i + 1
ciklus vége
ki i

A kiválasztás tételt akkor használjuk, ha tudjuk, hogy a keresett értéket tartalmazza a tömb. Ezért az nem vizsgáljuk, hogy vége van-e a tömbnek. A példában a ker változó tartalmazza a keresett értéket.

Lineáris vagy szekvenciális keresés néven is ismert, mivel végig megyünk a számokon sorba.

Adott elem szerepel-e a tömbben és hányadik helyen.

ker = 30
i = 1
ciklus amíg i<=n és t[i]<>ker
    i = i + 1
ciklus vége

Ha i<=n akkor
    ki "Van ilyen" 
    ki: "Indexe: ", i
különben
    ki: "A keresett érték nem található"
ha vége

Ha nincs ilyen elem, akkor erről értesítjük a felhasználót.

A tömb elemit egy másik tömbbe rakom, feltételhez kötve.

Például: Adott a és b tömb. Az a tömb egész számokat tartalmaz. Az a tömbből az 5-nél kisebb számokat átrakom b tömbbe.

j = 1
ciklus i = 1 .. n
    ha a[i] < 5 
        b[j] = a[i]
        j = j + 1
    ha vége
ciklus vége

Két tömbbe válogatjuk szét egy tömb elemeit

Adott „a” tömb, amely egész számokat tartalmaz. A „b” és „c” tömb pedig üres. Az „a” elemeit „b” tömbbe rakjuk ha kisebbek 5-nél, különben c-ben tároljuk.

j = 1
k = 1
ciklus i = 1 .. n
    ha a[i] < 5 
        b[j] = a[i]
        j = j + 1
    különben
        c[k] = a[i]
        k = k + 1
    ha vége
ciklus vége

Két tömb azonos elemeinek kiválogatása egy harmadik tömbbe

Adott például A és B tömb:

A közös elemeket szeretnénk C tömbben:

Algoritmus:

k = 1
ciklus i = 1 .. n
    j = 1
    ciklus amíg j<=m és b[j]<>a[i]
        j = j + 1
    ciklus vége
    ha j<=m akkor 
        c[k] = a[i]
        k = k + 1
    ha vége
ciklus vége

A és B tömb minden elemét szeretnénk C tömbbe tenni.

Adott például A és B tömb:

Az elemek uniója C tömbben:

Először C-be tesszük az A összes elemét, majd ami nem szerepel A-ban, azt beletesszük C-be.

ciklus i = 1 .. n
    c[i] = a[i]
ciklus vége 
k = n
ciklus j = 1 .. m
    i = 1
    ciklus amíg i<=n és b[j]<>a[i]
        i = i + 1
    ciklus vége
    ha i>n akkor
        c[k] = b[j]      
        k = k + 1
    ha vége
ciklus vége

Keressük a tömb legnagyobb elemét. A következő megoldás akkor működik, ha nincs negatív vagy nulla érték a tömbben:

max = 0
ciklus i = 1 .. n
    ha t[i]> max akkor 
        max = t[i]
    ha vége
ciklus vége

A másik lehetőség, hogy a max kezdeti értéke rögtön az első elem. Ez a megoldás bármilyen halmazon megállja a helyét:

max = t[1]
ciklus i = 2 .. n
    ha t[i]> max akkor 
        max = t[i]
    ha vége
ciklus vége

Ebben a formában viszont elég ha a második elemtől hasonlítunk össze.

Keressük a legkisebb elemet

min=t[1]
ciklus i = 1 .. n
    ha t[i] < min 
        min = t[i]
    ha vége
ciklus vége

A sorozat két utolsó elemét összehasonlítjuk, és ha fordított sorrendben vannak felcseréljük.

ciklus i := n-1 .. 1
  ciklus j := 1 .. i
    ha t[j] > t[j+1] akkor 
      b := t[j+1]
      t[j+1] := t[j]
      t[j] := b
    ha vége
  ciklus vége
ciklus vége

A buborék rendezés megvalósítható lentről felfelé és fentről lefelé is.

Az aktuális első elemet összehasonlítjuk az után következőkkel, ha a következő kisebb akkor csere. Utána a második, harmadik, stb. elemmel.

Ciklus i := 1 .. n-1
  Ciklus j := i+1 .. n
    Ha T[i] > T[j] akkor
       Csere(i,j)
    Elágazás vége
  Ciklus vége
Ciklus vége

Kiválasztjuk a legnagyobb elemet és a tömb végére rakjuk.

ciklus i := n .. 1
  max := i
  ciklus j := 1 .. i
    ha t[j] > t[max] akkor max := j
  ciklus vége
  csere(t[i], t[max])
ciklus vége

Például a tömb végétől kezdve feltételezem, hogy a legutolsó a legnagyobb. De nem magát a számot, hanem annak indexét jegyzem fel. Ezek után elölről kezdve átnézem, hogy a feltételezettnél nagyobb-e valamelyik. A végén mindenképpen cserélek.

Megkeressük a legkisebbet és a tömb elejére tesszük

ciklus i := 1 .. n-1
  min := i
  ciklus j := i+1  .. n
    ha T[j] < T[min] akkor 
      min := j 
    Elágazás vége
  ciklus vége
  ha min <> i akkor 
    Csere(i,min) 
  Elágazás vége
ciklus vége

Balról veszem a második elemet és haladok jobbra. Ez lesz az aktuális elem. Mindig az aktuális elemtől balra lévő elemhez hasonlítok. Ha a balra lévő nagyobb, cserélek. Ha cseréltem a csere kisebb elemét megint a baloldalihoz hasonlítom. Ha nem cserélek tovább balra haladva, akkor visszamegyek az aktuális elemhez, és ott újra kezdem.

ciklus i := 2 .. n
  kulcs := t[i]
  j := i-1
  ciklus amíg j>0 és t[j]>kulcs
    t[j+1] := t[j]
    j := j - 1
  ciklus vége
  t[j+1] := kulcs
ciklus vége

Nem csak a szomszédos elemeket hasonlítjuk össze, hanem először távoli indexű értékeket nézzünk, majd folyamatosan csökkentjük a távolságot. Az aktuális távolságot tárolhatom például h tömbben. (Az i értéke felvesz negatív értéket is)

Megvalósítás ha az első index 1

t = tömb(8, 9, 4, 7, 6, 3, 2, 1, 5);
h = tömb(5, 3, 1);

ciklus k := 1 .. 3 
  lepes := h[k]
  ciklus j := lepes + 1  .. n
    i := j - lepes; 
    x := t[j]
    ciklus amíg i > 0 és t[i] > x 
      t[i + lepes] := t[i]
      i = i - lepes
    Ciklus vége    
    t[i + lepes] := x
  Ciklus vége
Ciklus vége

A h tömb tartalmazza lépésszámot. Mindig az adott lépésszámú elemhez hasonlítok a sorozat végéig. Kezdetben ez 5 a példában. Ha elértük a sorozat végét, akkor kisebb lépésközre váltunk, esetünkben ez a 3. A végén 1-es lépésközzel végig megyünk. Ekkor biztosan rendezett a tömb. Az első lépésközt úgy számítjuk, hogy vesszük a tömb felét (n/2), és ahhoz közeli számot választunk. Az utolsó szám mindig az 1-es. A többi lépésköz kiszámítására több elmélet született.

1. 2^k (2 hatványai; ez a legrosszabb választás; nem hatékony)
   • 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, …
2. k · log(k) (Itt az egész részét vettem, ha kerekítek más számok jönnek:)
   • 2, 4, 8, 11, 15, 19, 24, 28, 33, 38, …
3. prímszámok (azok a számok, amelyeknek pontosan két osztójuk van)
   • 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, …
4. fibonacci-számok (Az első két elem 0 és 1, a továbbiakat az előző kettő összeadásával kapom)
   • 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, …
5. 2^k-1 (Hibbard ajánlása)
   • 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, …
6. 1-gyel indulunk, a következőben ezt szorozzuk 3-mal majd hozzáadunk 1-t (Knuth ajánlása, 1969)
   • 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, …
     • a = 1
     • a = (a * 3) + 1
7. 4ⁱ⁺¹ + 3·2ⁱ + 1 (i >= 0) Robert Sedgewick ajánlása. 20-30% gyorsabb mint a Knuth féle sorozat)
   • 1, 8, 23, 77, 281, 1073, 4193, 16577, …

Kis iskolai feladatnál, például 10 elem esetén a lépésköz lehet: 5, 3, 1, esetleg Hibbard ajánlása.

1. 1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, 463792, 1391376, 3402672, 8382192, 21479367, 49095696, 114556624, 343669872
2. 1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200
3. 1, 8, 23, 77, 281, 1073, 4193, 16577, 65921, 262913, 1050113, 4197377, 16783361, 67121153, 268460033, 1073790977

Az első Incerpi-Sedgewick féle ajánlás. A második Knuth féle ajánlás. Az utolsó a Sedgewick.

Nem helyben rendezünk, létrehozunk két másik tömböt, amelyben rendezetten vannak az elemek. A két segédlistára indexeket helyezünk el, amelyek mindig a legkisebb elemre mutatnak. A listák aktuális index által mutatott elemeit összehasonlítjuk, a kisebbet az eredeti tömbbe másoljuk. Oszd-meg-és-uralkodj algoritmusnak is nevezik.

Először két kisebb tömbre van szükségünk, amelyek rendezettek:

Indexel megjelölöm a legkisebbet:

A kettő közül a kisebbet elteszem:

Az indexmutató ugrik:

Az indexek által mutatott kisebbet megint elteszem:

Az indexet beállítom:

A kisebbet megint kiemelem:

Az indexeket igazítom:

Kisebbet elteszem:

Indexeket igazítom:

Elteszem:

Igazítom:

Elteszem a kisebbet:

Indexet állítok:

Az egész rendezést azzal kezdem, hogy két részre osztom a tömböt. A két részre osztott tömb ekkor nem rendezett, tehát alkalmatlan a fenti műveletekre. Viszont megtehetem, hogy a bal és jobb oldali tömböt is szintén ketté osztom, azok részeit is, mindaddig, amíg kettő nem marad. Ha csak kettő maradt, akkor már elvégezhető a fenti művelet, így rekurzívan visszafele az egész rendezhető.

összefésül(tömb, p, q, r)
   n1 := q - p + 1
   n2 := r - q
   a bal[1..n1+1] és a jobb[1..n2+1] tömbök létrehozása
   ciklus i := 1 .. n1
       bal[i] := tömb[p+i-1]
   ciklus vége
   ciklus j := 1 .. n2 
       jobb[j] := tömb[q+j]
   ciklus vége
   bal[n1+1] := ∞
   jobb[n2+1] := ∞
   i := 1
   j := 1
   ciklus k := p .. r
       ha bal[i] <= jobb[i]
           tömb[k] := bal[i]
           i := i + 1
       ellenben
           tömb[k] := jobb[j]
           j := j + 1
       ha vége
   ciklus vége
eljárás vége

Összefésülő-rendezés(tömb, p, r)
    ha p < r
        q := (p+r)/2
        Összefésülő-rendezés(tömb, p, q)
        Összefésülő-rendezés(tömb, q+1, r)
        Összefésülés(tömb, p, q, r)
eljrásá vége

A ∞ jel azt jelenti, a tömb legnagyobb eleménél nagyobb elem.

Ha a tömb rendezett a keresés gyorsabban elvégezhető.

Megnézzük a középső elemet. Ha az a keresett szám, akkor vége. Ha nem akkor megnézzük, hogy a keresett elem a tömb alsó vagy felső részében van. Amelyik tömbrészben benne van a keresett szám, a fentieknek megfelelően keresem a számot. A ciklus lépésszáma nagyjából log(n).

ciklus amíg  első <= utolsó  és  van = hamis
    Középső :=  (Első + Utolsó)  Div 2
    Ha keresett = t[középső] akkor 
      van := igaz
      index := középső
    else
        ha Keresett < t[középső] akkor 
            utolsó := Középső - 1
        Ellenben
            Első := Középső + 1
        Ha vége
ciklus vége

Itt is két tömb unóját szeretném megkapni, viszont a tömbök most rendezettek, és az unióképzés után szeretném megtartani a rendezettséget.

  i := 1
  j := 1
  k := 0
  ciklus amíg (i<= n) és (j<=m)
      k := k + 1

      ha a[i] < b[j] akkor 
          c[k] := a[i]
          i := i + 1
      ellenben
      ha a[i] = b[j] akkor 
          c[k] := a[i]
          i := i + 1
          j := j + 1
      ellenben
      ha a[i]> b[j] akkor
          c[k] := b[j]
          j := j + 1
      ha vége
  ciklus vége
  
  ciklus amíg i <= n 
      k := k + 1
      c[k] := a[i]
      i := i + 1
  ciklus vége
  
  ciklus amíg j <= m 
      k := k + 1
      c[k] := b[j]
      j := j + 1
  ciklus vége