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 | 5, 3, 6, 2, 1 |
|---|
| B | 6, 2, 7, 8, 9 |
|---|
A közös elemeket szeretnénk C tömbben:
| C | 6, 2 |
|---|
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:
| A | 5, 3, 6, 2, 1 |
|---|
| B | 6, 2, 7, 8, 9 |
|---|
Az elemek uniója C tömbben:
| C | 5, 3, 6, 2, 1, 7, 8, 9 |
|---|
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.
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.
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:
| 3 | 6 | 7 |
| 2 | 5 | 8 |
Indexel megjelölöm a legkisebbet:
| 3 | 6 | 7 |
| ^ |
| 2 | 5 | 8 |
| ^ |
A kettő közül a kisebbet elteszem:
| 2 |
Az indexmutató ugrik:
| 3 | 6 | 7 |
| ^ |
| 2 | 5 | 8 |
| ^ |
Az indexek által mutatott kisebbet megint elteszem:
| 2 | 3 |
Az indexet beállítom:
| 3 | 6 | 7 |
| ^ |
| 2 | 5 | 8 |
| ^ |
A kisebbet megint kiemelem:
| 2 | 3 | 5 |
Az indexeket igazítom:
| 3 | 6 | 7 |
| ^ |
| 2 | 5 | 8 |
| ^ |
Kisebbet elteszem:
| 2 | 3 | 5 | 6 |
Indexeket igazítom:
| 3 | 6 | 7 |
| ^ |
| 2 | 5 | 8 |
| ^ |
Elteszem:
| 2 | 3 | 5 | 6 | 7 |
Igazítom:
| 3 | 6 | 7 | ||
| ^ |
| 2 | 5 | 8 |
| ^ |
Elteszem a kisebbet:
| 2 | 3 | 5 | 6 | 7 | 8 |
Indexet állítok:
| 3 | 6 | 7 | ||
| ^ |
| 2 | 5 | 8 | |
| ^ |
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