Sorozatok algoritmusai: keresések

2. A három algoritmus

Feladat: listában keresünk egy bizonyos elemet.


Három nagyon hasonló algoritmus

  • Eldöntés: van-e olyan elem.
  • Kiválasztás: tudjuk, hogy létezik. Melyik az?
  • Lineáris keresés: hol van a keresett elem? Esetleg nincs is?

Mi a különbség a fentiek között?

Van három algoritmusunk, amelyeket gyakran pongyolán mind „keresés” néven emlegetünk. A három algoritmus azonban kicsit eltér egymástól működésben. Az eltérő előfeltételezések miatt nagyon különböző megvalósítások adhatóak rájuk.

Az eldöntés esetén az a kérdésünk, hogy létezik-e egy bizonyos tulajdonsággal rendelkező elem a listában. Például van-e piros színű a körök között, van-e Aladár a tankörben. Esetleg van-e X betű egy fájlban, vagy van-e valódi osztója egy számnak, ugyanis nem feltétlenül kell listákra gondolnunk.

A kiválasztás algoritmusa abból a feltételezésből indul ki, hogy a keresett elem biztosan szerepel a sorozatban, csak meg kell keresnünk, hogy hol.

A lineáris keresést felfoghatjuk az előző kettő keverékének is. A kérdésre adott válasz itt is egy hely megjelölése (a sorozat melyik eleme rendelkezik az adott tulajdonsággal). Azonban nem feltételezzük, hogy biztosan lesz ilyen, hanem a válasz az is lehet, hogy nincs.

Legyen szó akármelyikről is, tőrődjünk most mindig csak az első előfordulással.


Generikus algoritmusok

  • Akármilyen típusú az adat (szám, sztring, ember, ...)
  • Akármilyen tulajdonság (adott értékű elem, páros elem, ...)

Legyen szó akármilyen típusú adatokról, vagy akármilyen vizsgálandó tulajdonságról, maguk az algoritmusok ugyanúgy működnek.

3. Kiválasztás: hol van?

Lássuk előbb a kiválasztást, az a legegyszerűbb.

Feladat: keressünk meg a betű első előfordulását egy sztringben!

def melyik_az(sztring, betu):
    i = 0
    while sztring[i] != betu:   # !
        i += 1
    return i
  • Mit jelent a ciklusfeltétel?
  • Mi a helyzet a sztring hosszával?

A ciklusfeltétel egyszerű. Addig megyünk előre a sztringben, amíg meg nem találtuk a keresett elemet. Ha az i-edik betű nem az, amit kerestünk, akkor megyünk tovább – pörög a ciklus. Ha az, akkor viszont megállunk. Találat esetén már nem hajtódik végre a ciklus törzse, tehát amikor kijöttünk a ciklusból, akkor az i index pont a találat helyét mutatja, ami egyben a kérdésre adandó válasz.

Miért nem ellenőrizzük a sztring hosszát, nehogy túlindexelés legyen? Erre a kérdésre két válasz adható. Az egyik az, hogy rossz a kérdés. Kiválasztás algoritmusát kellett írnunk, ami azt jelenti, hogy valahonnan tudjuk, szerepel a megadott betű a sztringben, a kérdés csak az, hogy hol. Ezért teljesen biztosak lehetünk benne, hogy előbb-utóbb a sztring[i] != betu kifejezés hamissá válik, még azelőtt, hogy az i változó túl nagyra nőne. A másik válasz pedig az, hogy túlindexelésre amúgy is kivételt dob a sztring. Azt a kivételt persze itt nem kapjuk el, hanem eljut a hívóhoz. De azt ígérhetjük neki, hogy helyes paraméterezés esetén (ti. a sztringben tényleg van olyan betű, amit keresünk) nem fog kivételt dobni a függvény. Egyéb ígéretet nem kell tennünk, mert azzal a feltételezéssel írhatjuk meg a kódot, hogy lesz találat.

Ehhez hasonló gondolatmenettel rendelkezik az alábbi, elég lassú (és elég naiv) algoritmus, amely két szám legnagyobb közös osztóját határozza meg:

Feladat: legnagyobb közös osztó meghatározása.

Naiv algoritmus,
Euklidészé jobb!
def lnko(a, b):
    oszto = min(a, b)
    while a % oszto != 0 or b % oszto != 0:
        oszto -= 1
    return oszto

Itt is addig megy a ciklus, amíg el nem jutunk addig az osztóig, amely mindkét számot osztja maradék nélkül. Semmilyen határt nem kell ellenőriznünk, mert tudjuk, hogy a ciklus feltétele előbb-utóbb hamis lesz. Biztos lesz olyan szám, amelyik mindkét paraméternek osztója, mert az 1 minden számot maradék nélkül oszt.

Feltéve persze, hogy nem negatív számokat kaptunk paraméterként, mert akkor bajban vagyunk. Legjobb lenne ezt ellenőrizni. Meg azt is, hogy ne kapjunk valós számot. Meg listát se. Ja, és sztringet se. Nem bolondbiztos a függvény, de ha helyes bemeneteket kap, akkor jó eredményt is fog adni.

4. Eldöntés: van-e?

Feladat: létezik-e egy bizonyos szám a listában?

def van_e(lista, keresett):
    van_talalat = False
    i = 0
    while i < len(lista) and not van_talalat:
        if lista[i] == keresett:
            van_talalat = True
        i += 1
    return van_talalat
  • „Van-e?” – elég egy olyat találni, és megállhat a ciklus (hogyan?)
  • Ha egyet sem találtunk, akkor hamis érték marad a változóban

A megvalósításban bevezetünk egy változót, amely a választ fogja adni. Kezdetben ezt hamis értékre állítjuk. Vizsgáljuk a lista elemeit; ha van találat, akkor igazra, végül pedig visszatérünk a függvényből. Ha volt találat, addigra igazra állítottuk a változót, ha pedig sehol nem leltük meg a keresett elemet, akkor hamis maradt benne.

Vegyük észre, hogy elég egyetlen egy találat, akkor már mondhatjuk, hogy a válasz igen. Csak akkor kell a ciklusnak végigmennie a teljes listán, ha nincs meg a keresett elem. Ha megvan, akkor viszont akár meg is állhat. Ezt a megállítást végzi az összetett ciklusfeltétel: addig futtatjuk a ciklust, amíg a listának van vizsgálandó eleme ÉS egyben igaz az is, hogy NEM találtunk még semmit. Innen jön az and not. A második kitételnek egyébként az eredmény szempontjából nincs jelentősége (akár tovább is mehetnénk, többször is igazra állítva a változót, ha több találat van). A sebesség szempontjából viszont annál inkább, mert az első találat után minden további vizsgálat felesleges lenne.

Az összetett ciklusfeltétel miatt két okból is megszakadhat a ciklus futása: a lista végén és találat esetén. Furcsa vonása az algoritmusnak, hogy az i változót megnöveli akkor is, ha talált valamit. Vegyünk példának egy 10 elemű listát, amely 0...9-ig indexelődik. Ha a ciklus végén i = 10, az lehetséges úgy is, hogy nem volt találat (és azért jöttünk ki, mert vége lett a számsornak). De úgy is, hogy a 9-edik az épp a keresett elem volt, de ennek ellenére az index még nőtt eggyel. Ez valójában mindegy, mert nem a hely volt a kérdés, hanem hogy létezik-e a keresett elem, az pedig kiderül a van_talalat változó értékéből.

A van-e függvényt, vagyis az eldöntés algoritmusát egyéb formákban is lekódolhatjuk. Ezekről már volt szó egy régebbi előadáson. Például megállíthatjuk a ciklust break segítségével is, de legegyszerűbb, ha találat esetén rögtön visszatérünk a függvényből egy return utasítással. Ez azért előnyös, mert eggyel kevesebb változóra van szükségünk, és így jobban érthető a ciklus:

def van_e(lista, keresett):
    i = 0
    while i < len(lista):
        if lista[i] == keresett:
            return True
        i += 1
    return False

A vezérlési szerkezet viszont kevésbé érthető, mert több visszatérési pontunk is lett. De általában igyekszünk minél előbb visszatérni, mert ez az elterjedten használt logika.

Ezzel az átalakítással egyébként elértük, hogy i = 0, i < len() alakú legyen a ciklus, úgyhogy akár for-t is használhatunk:

def van_e(lista, keresett):
    for x in lista:
        if x == keresett:
            return True
    return False

Persze egyébként ugyanezt csinálja az in operátor a listákra: keresett in lista. De most egy kicsit jobban értjük a működését.

5. Hol van? – lineáris keresés

Feladat: keressük meg az első előfordulást, vagy adjunk None-t!

def hol_van(lista, keresett):
    i = 0
    while i < len(lista) and lista[i] != keresett:
        i += 1
    if i < len(lista):
        return i
    else:
        return None

A „nincs találat” eset jelzésére a None mellett a -1-et is elterjedten használják; például a sztringek .find() függvénye is -1-et ad akkor, ha nem talált semmit.

def main():
    szavak = ["alma", "körte", "barack"]
    idx = hol_van(szavak, "körte")
    if idx is not None:
        print(f"A(z) {idx}. helyen.")
    else:
        print("Nincs.")

Lássuk az algoritmust! Itt megint egy összetett ciklusfeltételünk van, ÉS kapcsolattal. Ha valamelyik oldala nem teljesül (hamis), akkor meg fog állni a ciklus. Megállhat azért is, mert i < len(lista) már nem igaz; mivel egyesével nőtt az index, ez csak úgy lehetséges, hogy i == len(lista). Vagy megállhat találat esetén is, ha lista[i] == keresett. A ciklus feltétele egyébként nagyon hasonló, mint az eldöntés ciklusáé; ha a != operátort ==-re cseréljük, és az eredményt tagadjuk, ez sokkal jobban látszik. Ugyanúgy megjelenik az and not:

    while i < len(lista) and not lista[i] == keresett:

Tulajdonképp ez lenne az eldöntésben annak az elágazásnak a feltétele, ami abban az algoritmusban a találat változót igazra állította.

Hogy működik végeredményben a ciklus? Addig fut, amíg 1) van még elem ÉS NEM 2) a keresett elemet látjuk épp az i indexen keresztül. Érdekesség, hogy a ciklus törzse kvázi üres, nem csinál semmit, csak i += 1-gyel lép tovább a következő elemre. Ez a léptetés azonban csak akkor történik meg, ha a ciklustörzsbe bejöttünk; de most a találat ellenőrzése a ciklus feltételében van, tehát ez csak akkor fog megtörténni, ha az i-edik elem nem a keresett adat. Ha igen, akkor úgy áll meg a ciklus, hogy az index pont a kérdéses helyet mutatja.

Bár matematikailag x ÉS y ugyanaz, mint y ÉS x, itt nem lenne szabad megcserélnünk a kifejezés két oldalát. Pythonban az ÉS operátor balról jobbra haladva értékeli ki az operandusait; ha a bal oldalon hamis érték áll, a jobb oldal kiértékelése meg sem történik már. Ez itt nagyon fontos! Ugyanis abban az esetben, amikor már a bal oldalon álló i == len(lista) igaz, a lista végére értük, akkor a jobb oldal lista[i]-je kivételt dobna! Ezt viszont nem szeretnénk; nem kivétel dobása volt a feladat, hanem None értékkel visszatérés. Egyébként pont ugyanemiatt nem lista[i] == keresett a függvényt befejező if feltétele sem.

6. Hasonlóságok

Tegyük egymás mellé a fent bemutatott algoritmusok kiválasztott változatait! (A változónevek rövidítve vannak, és a függvények fejléce sem szerepel, hogy az előadáson ráférjenek egy diára a kódok.)

Melyik melyik?

Kiválasztás vs. lineáris keresés:

i = 0
while lis[i] != mi:
    i += 1
i = 0
while i < len(lis) and lis[i] != mi:
    i += 1

A kiválasztás és a lineáris keresés magja csak annyiban különbözik egymástól, hogy a lineáris keresés a lista végének elérésére is figyel.


Melyik melyik?

Eldöntés vs. lineáris keresés:

i = 0
while i < len(lis):
    if lis[i] == mi:
        return True
    i += 1
return False
i = 0
while i < len(lis):
    if lis[i] == mi:
        return i
    i += 1
return None

Ha a ciklus közepén return utasítással visszatérő változatokat vizsgáljuk, akkor az eldöntés és a lineáris keresés csak annyiban különbözik, hogy indexet vagy logikai értéket adnak vissza.

7. Lineáris keresés – ha a lista rendezett

Ha rendezett a lista...

Az alábbi listában keressük az 50-et. Benne lesz?

10 28 30 41 57 68 72 81 97

Néhány elemet már megvizsgáltunk: 10, 28, 30, ... A következő elem, amit vizsgálnánk, az 57. Ez sem a keresett elem, mert az 50-et keressük. De vajon benne lesz az 50 a listában? A válasz egyértelmű nem. Most 57-et látunk, és a lista fennmaradó részében az 57-nél nagyobb számok lehetnek csak. Ezért a keresést itt helyben meg is állíthatjuk.


Mit jelent ez az algoritmusunkra nézve? Azt, hogy a ciklus végét vizsgáló feltételt kicsit finomíthatjuk. Nem csak a listaindexet vizsgálhatjuk, hanem a tartalmat is:

def hol_van(lista, mi):
    i = 0
    while i < len(lista) and lista[i] <= mi: # !
        if lista[i] == mi:
            return i
        i += 1
    return None

Amíg van vizsgálandó elem, és az nem nagyobb a keresettnél (kisebb vagy egyenlő), addig kell futnia a ciklusnak. Ha elfogytak, vagy nagyobb elemet látunk, akkor megállhat. Így egy kicsit gyorsabb az algoritmus, mert átlagosan a lista felét nem kell megvizsgálnunk. De ha rendezett sorról van szó, akkor ennél jobbat is tudunk.

8. Bináris keresés – legyünk okosabbak!

Ha rendezett a lista...

Nem csak == és != van, hanem a < és a > is hasznos információ!

  • ==: Ezt keressük!
  • <: Valahol előrébb kell legyen.
  • >: Hátrébb kell legyen. 


def binkeres(lista, mit):
    min = 0                  # határok
    max = len(lista) - 1
    
    kozep = (min + max) // 2
    while min <= max and lista[kozep] != mit:
        if lista[kozep] < mit:
            min = kozep+1    # középtől jobbra
        else:
            max = kozep-1    # középtől balra
        kozep = (min + max) // 2

    if min <= max:
        return kozep
    else:
        return None

A bináris keresés minden lépésben megfelezi a vizsgálandó tartományt. A működésének lényege: megvizsgálja a középső elemet. Ha az rögtön az, amit keresett, akkor vissza is tér vele. Ha nem, akkor a kisebb-nagyobb relációtól függően tudja folytatni a vizsgálatot. Ha a keresett elem kisebb, mint a rendezett lista középső eleme, akkor valahol tőle balra kell keresni az elemet; ha nagyobb, akkor pedig valahol tőle jobbra. Ezért a min és a max változók (amely az épp vizsgált tartomány alsó és felső határát mutatják) ettől függően beállíthatók a középsőtől balra vagy jobbra lévő elemre.

Mindezt addig kell folytatni, amíg meg nem találjuk a keresett elemet, vagy a vizsgálandó tartomány nulla méretűvé nem zsugorodik. (Mivel a min-t és a max-ot mindig a középsőtől eggyel arrébb állítjuk, a tartomány eltűnését a min>max miatt vehetjük észre.) A ciklusnak itt is összetett feltétele van, a befejeződése után ezért meg kell vizsgálni, miért állt meg.

9. A keresések időigénye

hatékonyságörülünk-e
O(1), konstans
O(log n), logaritmikus
O(n), lineáris
O(n2), négyzetes
O(en), exponenciális

Lineáris keresés: O(n)

  • Lehet, hogy egyből megtaláljuk, lehet, hogy a végén lesz
  • Átlagosan a felét kell végignézni
  • A keresési idő egyenesen arányos a lista méretével

Bináris keresés: O(log2n)

  • Minden lépésben felezzük az intervallumot
  • A keresési idő ~ log2méret. 1 millió → 20 lépés!

Algoritmusok hatékonysága általában

Az O(n) jelöléssel szoktuk jellemezni egy algoritmus gyorsaságát. A jelölésben az n a bemenet hosszát, a bemeneti adatok számát jelenti. O(n) azt jelenti, hogy a lépésszám nagyjából lineárisan, O(n2) pedig, hogy nagyjából négyzetesen függ a bemeneti adatok számától.

Algoritmusok és gráfok
tárgyból szerepelt

Egy algoritmus lépésszáma annak vizsgálatával becsülhető, esetleg pontosan meg is határozható. Az így kapott függvénynél csak a leggyorsabban végtelenhez tartó tagot vesszük figyelembe, mert nagy bemenet esetén az a döntő. Az n2 gyorsabban tart a végtelenhez („bikább”), mint az n, mivel bármilyen nagy konstans szorzó, pl. 10000n esetén is lehet olyan n-et találni, amelyre n2 jóval nagyobb, mint 10000n. Az exponenciális függvény tart leggyorsabban a végtelenhez, míg a logaritmus függvény értéke pedig mindegyik közül a leglassabban.

Emiatt részesítjük előnyben az olyan algoritmusokat, amelyek O(1), O(log n) vagy O(n) időben futnak. Az O(n2) nagy n-ek esetén már lassú lehet; O(en) pedig valószínűleg lassú már kis n-ek esetén is. Éppen erre épülnek a titkosítások: ha jó az algoritmus, akkor a megfejtés csak próbálkozásra épülhet – ami viszont viszonylag kis kulcs esetén is beláthatatlanul hosszú ideig tart. (Titkosítás: ha a jelszó (titkosítás kulcsa) 128 bites, a végigpróbálandó lehetőségek száma: 2128=340282366920938463463374607431768211456 darab.)

Rendezések



11. Rendezések, helyben rendezés

Rendezett lista

  • Növekvő sorrend: a szomszédos elemekre t[i] <= t[i+1]
  • Tranzitív tulajdonság: ha A≤B és B≤C, akkor A≤C

A „helyben rendezés” fogalma

  • Nincs segédlista, a meglévő listával dolgozunk
  • Megengedett lépések: két elem összehasonlítása és cseréje
  • Nincs segédlista, cserékkel dolgozunk

A rendezések működése

  • Genericitás: az algoritmusok általánosak (sorrend, típus)
  • „Oszd meg és uralkodj” elv: divide and conquer (latinul: divide et impera)
  • A rendezett részt növeljük, amíg el nem fogy a rendezetlen rész
1 2 3 4 7 5 8 6 9

12. Buborékrendezés (bubble sort)

A buborékrendezés a rendezettség definíciójából indul ki, miszerint t[i] <= t[i+1] igaz kell legyen minden elempárra. Ez az algoritmus mindig egymás melletti elemeket hasonlít össze, és ha rossz sorrendben vannak, megcseréli őket. Mindezt természetesen szisztematikusan teszi, sorjában „végigfésülve” a lista elemeit az elejétől a végéig.



Lényege: egymás melletti elemek összehasonlítása és cseréje.
Egy sor csere által a legnagyobb elem a végére kerül.

A buborékrendezés egymás melletti elemeket hasonlít össze. Lépései:

  • Hasonlítsuk össze az első két elemet. Ha nincsenek jó sorrendben, cseréljük meg.
  • Hasonlítsuk össze a második párt (második és harmadik elem). Esetleg csere.
  • Folytassuk így a lista végéig.
  • A legnagyobb elem ezáltal a lista végére kerül, még akkor is, ha legelöl volt. Az már a végleges helye.
  • Csináljuk meg ugyanezt még egyszer, a lista elejétől az utolsó előttiig. Az utolsóhoz már nem kell nyúlni, hiszen az a legnagyobb.
  • Aztán ugyanezt megint, de az utolsó kettőhöz már nem nyúlunk stb.

Futás közben így a lista két részre oszlik: egy már rendezett és egy még rendezetlen részletre. A rendezetlen részlet egyre csökken; azon belül kell összehasonlítani és esetleg cserélni a párokat. Ezért az algoritmus két ciklust tartalmaz. A külső ciklus az egyre kisebb rendezetlen részt határozza meg; a belsejében lévő pedig az egymás melletti párok összehasonlítását vezérli. 

def buborek(lista):
    for i in range(len(lista)-1, 0, -1):
        for j in range(0, i):
            if lista[j+1] < lista[j]:
                temp = lista[j]
                lista[j] = lista[j+1]
                lista[j+1] = temp

Figyelni kell az indexekre! Észben kell tartani, hogy a range() az elején zárt, a végén nyílt intervallumot ad (tehát a range(0, 10) valójában a 0...9 számokat sorolja fel). Látszik, hogy a range() visszafelé felsorolásra is képes: a harmadik paraméternek -1-et kell megadni. A tartomány ilyenkor is elején zárt, végén nyílt.

Javított buborékrendezés (improved bubble sort)

Figyeli, hogy egy fésülés során volt-e csere. Ha nem, leállítható a rendezés.

1 2 3 4 5 6 7 8 9

Azért lehet ezt megtenni, mert a fésülések közben mindig ugyanazt a listarészletet vizsgáljuk, vagyis mindig annak egy egyre rövidebb darabját. Ha az egészet végignézve nem kellett cserélni, akkor egy kisebb részt vizsgálva sem fog kelleni.

Keverő rendezés (cocktail sort)

A sima buborékrendezésnél: nyulak és teknősök.

nyulak (rabbits)
nagy értékű elemek, amelyek a hamar a helyükre kerülnek
teknősök (turtles)
kicsi értékűek, amelyek lassan vándorolnak a lista elejére

Ötlet: a rendezést felváltva egyik-másik irányba végezzük. Így a cserék száma kicsit kevesebb lesz.

13. Közvetlen kiválasztással (selection sort)



Lényege: megkeresi a rendezetlen listarészlet legkisebb elemét, és az elejére rakja.

Ezt az algoritmust szélsőértékkeresős, vagy minimumkeresős rendezésnek is szokták nevezni. A működéséhez a buborék algoritmusnál tett megfigyelés adja az ötletet: ott a belső ciklus minden futása után a legnagyobb elem a rendezetlen részlet végére, és ezáltal a rendezett részlet elejére került. Az ötlet lényege, hogy ne cserékkel toljuk el odáig a legnagyobb elemet, hanem inkább keressük meg a listában azt, és végezzük el egy lépésben a cserét. Vagyis tegyük egyből a helyére a kérdéses elemet. Itt a legkisebb elemekkel történik ez.

A közvetlen kiválasztásos algoritmus előnye a buborékrendezéshez képest, hogy jóval kevesebb cserét végez a listában. Itt mindegyik elem egy lépésben a helyére kerül, vagyis legrosszabb esetben is a cserék száma db-1, ahol db a lista mérete. 

def kozvetlen(lista):
    for i in range(0, len(lista)-1):
        minidx = i            # minimum keresése
        for j in range(i+1, len(lista)):
            if lista[j] < lista[minidx]:
                minidx = j

        if minidx != i:
            temp = lista[minidx]      # csere
            lista[minidx] = lista[i]
            lista[i] = temp

A kód szerkezete hasonló az előzőéhez, itt is ciklusban ciklus kell. A külső ciklus i változója éppen azt az indexet tárolja mindig, amelyik helyre az odavaló elemet keressük. Első futásnál ez 0, vagyis az egész lista (lista[0]...lista[méret-1]) legkisebb elemét keresi meg a j-s, belső ciklus. A keresés után a legkisebbnek talált elem ide kerül, és később már nem is mozdul el innen.


Két változó (vagy listaelem) cseréjét egyébként Pythonban így is lehet írni: a, b = b, a. Így magát a cserét elvégezhetnénk így is:

if minidx != i:
    lista[i], lista[minidx] = lista[minidx], lista[i]

Jelen esetben mondjuk inkább rosszabb lett ettől a program; az előző verzió „csere” kommentje többet ért.

14. Rendezések hatékonysága – cserék száma

Melyik algoritmus gyorsabb, a buborékrendezés vagy a szélsőértékkereséses rendezés?



Algoritmusok és gráfok
tárgyban részletesebben

A fenti animáció kicsit csal. Nem túl igazságos, ugyanis az összehasonlítások idejére nem figyel, hanem csak a helycseréket animálja. Ugyanakkor a lényeg látszik: a buborékrendezés nagyon sok ideig bíbelődik a cserékkel, míg a közvetlen kiválasztásos módszer hamarabb végez a rendezéssel.

Ez azonban csak az általános eset. Lehetnek olyan speciális esetek, amelyeknél a buborékrendezés jobban teljesít: pl. ha csak egy-két elem van rossz helyen, azokat a buborékrendezés sokkal gyorsabban a helyükre tudja rakni, mintha egy szélsőértékkereséses algoritmust használnánk.

Ezért a rendezőalgoritmusok összehasonlításakor mindig meg szokták adni a minimális, átlagos és maximális lépésszámot.

Rendezések hatékonysága cserék alapján, n elemű listára
összehasonlításcserék
rendezés maxátlagminmaxátlagmin
javított buborék n2n2nn2n20
közvetlen kiválasztásn2n2n2nn0
gyorsrendezés n2n·lognn·lognn2n·logn0
kupacrendezés n·lognn·lognn·lognn·lognn·lognn·logn

15. Kertitörpe-rendezés (gnome sort)



Lényege: ha az egymás mellettiek jó sorrendben vannak, léphetünk egyet előre. Ha rossz sorrendben, akkor csere. Ha a csere által rossz sorrend keletkezik, az csak a csere előtt lehet, ezért visszafelé kell lépni egyet.

def torperendez(lista):
    i = 0
    while i < len(lista):
        if i == 0 or lista[i-1] <= lista[i]: # jó sorrend?
            i += 1              # előre
        else:
            temp = lista[i]     # csere
            lista[i] = lista[i-1]
            lista[i-1] = temp
            i -= 1              # vissza

Rekurzió

Az elv, hogy meg lehet hívni egy függvényből egy másikat, rögtön felveti a kérdést: vajon saját magát is?

17. Faktoriális rekurzív függvénnyel

Rekurzív függvény az, amely meghívja saját magát.

     ┌
     │ 1,        ha n = 1
n! = ┤
     │ n·(n-1)!, ha n > 1
     └

def fakt(n):
    if n == 1:
        return 1
    else:
        return n * fakt(n-1)

Ezt a működést a verem teszi lehetővé!

18. Faktoriális: a függvényhívás menete

A verem nevű memóriaterületre kerülnek függvényhíváskor a paraméterek és a visszatérés adatai. Ide kerülnek a lokális változók is. Ezt a működést azért nevezik veremnek, mivel ugyanúgy telik meg, mint egy verem (gödör). Amit legutoljára betettünk, azt látjuk legfelül, és kivenni is azt tudjuk legelőször.

Minden függvényhíváskor létrejönnek a függvény paraméterei és lokális változói a veremben, és a visszatéréskor megszűnnek azok. Egy konkrét függvényhíváshoz tartozó adatokat keretnek nevezzük (stack frame). Ha a függvényből egy másik függvényt is meghívunk, akkor egy ahhoz tartozó keret is létrejön a veremben – mindig legfelül, természetesen. A függvényhívás után a keret megszűnik, minden hozzá tartozó változó törlődik.

A rekurzió működésének kulcsa az, hogy ahányszor meghívjuk a függvényt, a paraméterei, lokális változói annyiszor újabb és újabb példányban létrejönnek! Lássuk vizualizálva, hogy is megy ez.

def fakt(n):
    if n == 1:    
        return 1    
    else:
        return n*    
                 fakt(n-1)    


def main():
    eredm = fakt(3)    
    print("3 !=", eredm)    
    return    


main()

main()
eredm:

A lokális változók csak addig léteznek, amíg a faktoriálist számoló függvény belsejében van a végrehajtás. Amint visszatér abból a main()-be, azok megszűnnek.

Gondoljunk bele: most használjuk ki igazán, hogy a függvény után a számítógép onnan folytatja a végrehajtást, ahonnan meg lett hívva a függvény! Ha ez sok függvényhívással odébb volt, akkor is. Ha sok rekurzív függvényhívással beljebb (lejjebb) volt, akkor is! Ezért mindig tudja a gép, hogy épp a fakt(n-1) kiszámítása ért véget, és visszaugrik abba a példányba, ahol a fakt(n) kiszámítása folyik.

Érdekesség: a vermet is Alan Turing találta ki. Amikor egy értéket az általa tervezett gép betett a verembe, azt a műveletet BURY-nek, azaz eltemetésnek nevezte. A kivétel pedig az UNBURY, vagyis a kiásás.

19. A leállási feltétel

Ahogy a ciklusoknak is van egy belépési feltételük, amely nem teljesülése esetén megállnak az iterációk, a rekurziónál is előbb-utóbb el kell jutnunk egy olyan pontra, amikor a függvény már nem hívja meg magát. Különben sose térne vissza. A rekurziónál ezt báziskritériumnak nevezzük.

Leállási feltétel

  • Kell legyen egy báziskritérium: amikor már nem hívja meg magát.
  • Minden lépésben közeledni kell a báziskritériumhoz.

Klasszikus példa a rekurzióra az ún. Fibonacci számsor. Ebben a számsorban minden elem az őt megelőző két elem összege.

       ┌ 
       │ n, ha n < 2
Fib(n) ┤ 
       │ Fib(n-2) + Fib(n-1) amúgy
       └ 

def fib(n):
    if n < 2: # báziskritérium
        return n
    else:
        return fib(n - 2) + fib(n - 1)

A fenti függvényben teljesül a leállási feltétel: n<2 esetén a függvény nem hívja meg már magát, és a hívások során mindig kisebb n szám a paraméter.

A számsor kiszámítására amúgy ez nem túl hatékony megoldás, inkább csak az egyszerűsége miatt szép a függvény. Vegyük észre a rajzon: pl. a fib(2) értékét többször is kiszámítjuk. Sőt a függvényhívások száma exponenciálisan növekszik. Erről lesz majd szó az Algoritmusok és gráfok tárgyon a dinamikus programozás kapcsán, és később mi is visszatérünk még rá.

20. Hanoi tornyai játék

Másik klasszikus példa a rekurzióra az ún. Hanoi tornyai játék. Ebben a korongokat át kell tenni az első rúdról a harmadikra, de úgy, hogy 1) egyszerre csak egy korongot mozgathatunk, 2) kisebb korongra nagyobbat nem tehetünk. (A középső oszlop ideiglenes tárolónak használható.) Négy korong esetén ez a lépéssorozat adja a megoldást: A→B, A→C, B→C, A→B, C→A, C→B, A→B, A→C, B→C, B→A, C→A, B→C, A→B, A→C, B→C. A látszólag bonyolult probléma rekurzív megoldása pár soros.


Ötlet: Rakjunk félre n-1 korongot... Akkor az alsó korong mozgatható! Na de arról volt szó, hogy egyszerre csak egy korong mozoghat...

Próbáld ki! A „következő” és „folyamatos” gombokat nyomva egyesével látszanak a lépések. A „start” után a „varázslat” gomb pedig megmutatja azt, min alapszik a megoldás ötlete.

21. Hanoi tornyai – a megoldás vázlata

Mennyire hiszel
a top-down
tervezésben?

Top-down tervezés

if prim_e(i):
    ...

Függvény = fekete doboz. Nem kell belelátnunk!


Hanoi tornyai: megoldásvázlat top-down tervezéssel

def hanoi_vazlat(n, honnan, seged, hova):
    varazslat(n - 1, honnan, hova, seged)
    print(f"rakj 1-et: {honnan} -> {hova}")
    varazslat(n - 1, seged, honnan, hova)

Ha szeretnénk honnan, hova pakolni a korongokat a seged oszlop használatával, a lépések:

  1. Varázsoljunk n-1 korongot a kiindulási (honnan) oszlopról a segédoszlopra. Eközben a cél, „hova” oszlop lehet az ideiglenes tároló.
  2. Ha ezt megoldottuk, akkor a legalsó korongot csak át kell rakni.
  3. És az átrakott legalsó, legnagyobb korongra a félretett n-1 korongot varázsoljuk. Vagyis a segédoszlopról (mert oda tettük őket félre) a céloszlopra (végleges helyükre), közben a kiindulási oszlop (honnan) lehet az ideiglenes tároló.

Tehát n-1 korongot varázsolunk, 1-et mozgatunk, végül megint n-1-et varázsolunk. Mit jelent a varázslat? Hogy n-1 korongot helyezünk át; ott viszont ugyanazt kell majd csinálni, mint amit itt kellett. Innen jön a rekurzió.

A megértés kulcsa az, ha nem (!) próbáljuk meg megérteni, a varazslat(n-1) belsejében mi történik. A top-down tervezést mindig úgy végeztük el, hogy feltételeztük bizonyos függvények létezését, amelyek részfeladatokat végeznek el. Ezekről a függvényekről azt feltételeztük, hogy helyes bemenetre helyes eredményt adnak. A rekurzió tervezésekor ezt gondoljuk az éppen írt függvényünkről is.

A rekurzió tervezésénél a következő két dolgot kell tehát végiggondolni:

  • Melyik az a legegyszerűbb eset, amelynél a megoldás egyértelmű? Jelen esetben ez az lesz, amikor 0 korongot kell mozgatni, mert olyankor már nincs is dolgunk.
  • Ha bonyolultabb esetről van szó, hogyan lehet visszavezetni egyszerűbb esetekre? Jelen esetben: n-1 korong mozgatása, egy korong mozgatása, n-1 korong mozgatása.

22. Hanoi tornyai – megoldás Pythonban

A fentiek alapján a teljes megoldás:

def hanoi(n, honnan, seged, hova):
    if n == 0:
        return
    hanoi(n - 1, honnan, hova, seged)
    print(f"rakj 1-et: {honnan} -> {hova}")
    hanoi(n - 1, seged, honnan, hova)


def main():
    hanoi(4, 'A', 'B', 'C')


main()

23. Gyorsrendezés

Feltalálója:
Tony Hoare

A gyorsrendezés (quick sort) egy rekurzív rendezőalgoritmus. Lényege: egy elemet vezérelemnek választva két részre osztjuk a listát: a vezérelemnél kisebbekre és nagyobbakra. Ha a kicsiket a lista elejére, a nagyokat a lista végére tesszük, azzal közelebb kerülünk a rendezett állapothoz.

A gyorsrendezés jól optimalizálható, ha számokat kell rendezni. Mivel minden összehasonlítás a vezérelemet vizsgálja, azt körönként csak egyszer kell kiolvasni a memóriából. C. A. R. Hoare angol programozó, matematikus. Legismertebb eredménye ez az algoritmus, amelyet 26 évesen dolgozott ki.

2 3 1 4 + 5 + 7 6 9 6

Lényege: oszd meg és uralkodj elvű. A működés:

  • Vezérelem kiválasztása (tetszőleges elem).
  • Szétválogatás: kicsik előre, nagyok hátra kerülnek.
  • Az így kapott két részlet külön-külön rendezendő.

A gyorsrendezés az „oszd meg és uralkodj” elven működik. Lépései a következők:

  • Kiválasztunk a listából egy tetszőleges elemet. Ez lesz az ún. vezérelem (pivot).
  • Az ennél kisebbeket a lista elejére, az ennél nagyobbakat a lista végére rendezzük. A vezérelemmel megegyező elemek mehetnek bármelyik oldalra.
  • Ezután az így keletkező két listarészletet külön rendezzük, az algoritmus rekurzív hívásával.

Az algoritmus hatékonysága azon múlik, hogy sikerül-e jó vezérelemet választani. Akkor lehet minden lépésben a kisebbekre és nagyobbakra szedett listarészeket egyenlő nagyságúvá tenni – felezni a listát –, ha a vezérelem éppen a lista mediánja, azaz a rendezett lista középső eleme. Sajnos a mediánt nem tudjuk megmondani, hiszen ahhoz rendezve kellene legyen a számsor... Ezért leginkább azt szokás csinálni, hogy találomra választunk vezérelemet, akár éppen az elsőt, és kész.

Ez persze nem optimális minden esetben. Néha a vezérelemnél kisebb vagy nagyobb elemek listája majdnem üres. Ilyenkor az első körben szinte semmi nem történik. Emiatt van az, hogy bár átlagos esetben ez az algoritmus O(n·log n) időben tud teljesíteni, de legrosszabb esetben ugyanúgy O(n2) időben fut le, mint egy buborékrendezés.

24. Gyorsrendezés – listák összefűzésével

A gyorsrendezés egy lehetséges megvalósításában a lista elemeit három különböző listába válogatjuk: a vezérelemnél kisebbek, azzal megegyezők, és nagyobbak; utána a listákat összefűzzük.

A Pythonban listákat a + operátorral tudunk összefűzni (merge):

szamok = [1, 2, 3] + [4, 5, 6, 7]

Ez egy új listát hoz létre, amelybe az operandusaiként megjelenő két lista elemeit másolja be.

Ezzel a gyorsrendezés nagyon egyszerű:

def gyorsrendez(lista):
    if len(lista) < 2:
        return lista
    
    pivot = lista[0]
    eleje = []
    kozepe = []
    vege = []
    for x in lista:
        if x < pivot: eleje.append(x)
        elif x > pivot: vege.append(x)
        else: kozepe.append(x)
    return gyorsrendez(eleje) + kozepe + gyorsrendez(vege)

2 3 1 4 + 5 + 7 6 9 6

A rekurzív függvény működése a következő:

  • Először is, a báziskritérium. Kettőnél kevesebb elemű, azaz 0 és 1 elemű listán nincs mit rendezni, úgyhogy ott visszatér a változatlan listával. Ha legalább 2 elem van, akkor megy csak innen tovább, mert akkor már van mit összehasonlítani.
  • Kiválasztja a lista legelején álló elemet vezérelemnek.
  • Létrehoz három üres listát, az elejét, a közepét és a végét. Ezekbe fogja szétválogatni az elemeket nagyság szerint.
  • Innentől az eddig megismert algoritmus következik: a kicsiket az első, a vezérelemmel megegyező elemeket a második, végül pedig a nagy (vezérelemnél nagyobb) elemeket a harmadik listához fűzi hozzá.
  • Ezután pedig a három listát összefűzi: kicsik + középsők + nagyok.
  • Középen egyforma elemek lesznek. Viszont a kicsik és a nagyok listájában még összevissza vannak az elemek, ezért összefűzés előtt azokat rekurzívan rendezi: gyorsrendez(eleje) és gyorsrendez(vege).

Ez a rendezőfüggvény szemantikailag más, mint az eddigiek. Ez nem egy meglévő listát rendez, hanem egy új listát ad vissza, amiben ugyanazok az elemek vannak más sorrendben. Vagyis a kapott listát be kell tennünk egy új változóba, esetleg a meglévő változót felül kell írnunk az új listával:

szamok = [9, 5, 8, 9, 4, 7, 3, 9, 1, 2, 5, 7]

# ugyanazok a számok másik listában
sorban = gyorsrendez(szamok)

# esetleg felülírva a változót saját magával
szamok = gyorsrendez(szamok)

Egyébként pontosan így kell használni a beépített sorted() függvényt is:

szamok = [9, 5, 8, 9, 4, 7, 3, 9, 1, 2, 5, 7]
sorban = sorted(szamok)
print(sorban)

A gyorsrendezésnek létezik egy másik verziója. Az nem épít új listákat, hanem a meglévő listában cserélgeti az elemeket, vagyis egy klasszikus helyben rendezést valósít meg. Erről egy külön írásban lehet olvasni.

25. Iterációval vagy rekurzióval?

Bizonyítható: minden rekurzív probléma megoldható iteratívan is, és minden iteráció átalakítható rekurzióvá.

rekurzív
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 2) + fib(n - 1)
iteratív
def fib(n):
    elozo = 1
    f = 0
    for _ in range(0, n):
        kov = f + elozo
        elozo = f
        f = kov
    return f

Mikor használjuk a rekurziót?

  • Sokszor egyszerű és szemléletes a rekurzív megoldás, pl. fib(n)
    • Egyszerűbb a helyességét is bizonyítani... pl. fib(n)
    • De nem biztos, hogy a leghatékonyabb... pl. fib(n)
  • Nem érdemes indokolatlanul használni ciklusok helyett
  • Leginkább rekurzív jellegű problémák esetén
    • Pl. 5+2*3 kifejezés értelmezése
  • Rekurzív adatszerkezetek esetén (erről Algoritmusokból volt szó)

26. A rekurzív hívás helye a függvényben

Az alábbi függvények mindketten a nekik paraméterként adott sztringeket írják ki. Ahogy a nevük mutatja, az előre függvény előrefelé, a hátra pedig hátrafelé, vagyis megfordítva teszi ezt.

def elore(sztring):
   if sztring == "":
      return
   print(sztring[0], end="")
   elore(sztring[1:])
előre("Python") # Python
   print("P")
   előre("ython")
      print("y")
      előre("thon")
         print("t")
         előre("hon")
            print("h")
            előre("on")
               print("o")
               előre("n")
                  print("n")
                  előre("")
                     pass
def hatra(sztring):
   if sztring == "":
      return
   hatra(sztring[1:])
   print(sztring[0], end="")
hátra("Python") # nohtyP
   hátra("ython")
      hátra("thon")
         hátra("hon")
            hátra("on")
               hátra("n")
                  hátra("")
                     pass
                  print("n")
               print("o")
            print("h")
         print("t")
      print("y")
   print("P")

Vegyük szemügyre az „előre” függvényt! Ez üres sztring esetén visszatér egyből, nem csinál semmit. Ha nem üres a sztring, akkor viszont legalább egy karaktere biztosan van. Kiírja azt az első karaktert, és végül pedig meghívja magát a fennmaradó részre. Az rekurzívan ki fogja írni a többi karaktert is, mert a vágott sztringben a következő karakter lesz legelöl, és így tovább.

A másik függvény a sztringet hátrafelé írja ki. Viszont ez mindössze két utasítás felcserélésén múlik! Az előre függvény ugyanis előbb az első karaktert írja ki, majd a többit. A hátra függvény ezzel szemben kiírja előbb a sztring hátsó részét, és csak utána az első karaktert – de mivel a hátsó részét is ugyanilyen módon jeleníti meg, az a hátsó rész is fordítva lesz.

A rekurzív hívás során az átadott sztring mindkét esetben ugyanaz lépésenként, hiszen az eredeti sztring nem fordul meg! Ez látható a lenti táblázatban, amely azt mutatja be, hogy mi történik a rekurzív hívás előtt és után az egyes esetekben. Érdemes ezt kipróbálni nyomkövetőben!

A függvények működése a "Python" sztringen
előrehátra
hívás előttprint("P")-
rekurzív híváselőre("ython")hátra("ython")
hívás után-print('P')

Listákat és sztringeket általában ciklusokkal dolgozunk fel, hiszen az a természetesen adódó eszköz erre a feladatra. Az itt bemutatott rekurzív sztringfeldolgozás célja kizárólag az, hogy a rekurzió működésére rávilágítson, és mindehhez egyszerű példát adjon. A sztring előre- és hátrafelé történő kiírása olyan egyszerű, magától értetődő iteratív feladat, amelyet Pythonban rekurzív módon megvalósítani pazarlás (a sok függvényhívás mind időbe telik).

27. Zárt terület kifestése (boundary fill)

Adott pont kifestése

  • Ha fekete, azt nem lehet festeni
  • Ha már ki van festve, nincs teendő
  • Amúgy ki kell festeni, a szomszédait is!

Miért rekurzív?

  • Mert ugyanaz a teendő minden pontnál
  • A konkáv alakzatoknál elágazik

Próbáld ki a kifestőt!

Az algoritmusról többet a linkre kattintva olvashatsz: zárt terület kifestése.

28. Labirintus generálása

Adott pontban...

  • Termet építeni
  • Mind a négy irányba véletlenszerűen:
    • Ha lehet, új járatot
    • És abból a pontból indulva: labirintus!

Rekurzió?

  • Ha visszatért egy irányból...
  • ... akkor a többi irányt is meg kell próbálni
  • Emlékezni kell, melyeket!
  • „Bejárni a területet”

Ez nagyon hasonlít a zárt terület kifestéséhez – itt is a téglalap alakú terület minden pontjába el kell jutni. Annyi a különbség, hogy itt véletlenszerűen kell megválasztani azt, hogy merre megyünk tovább.

A labirintus generálása mellett a megfejtése is megoldható rekurzívan. Ha elérkezünk az út során egy terembe, ahol egy elágazás van, akkor meg kell próbálni mind a négy irányt. Ha az egyikből visszatérünk, mert az zsákutca, akkor a másik irányba is meg kell próbálni. Az útvonalkereső algoritmusok, amelyek egy térképen megkeresik A és B város között a legrövidebb utat, általában is így működnek.

Az algoritmusokról többet a linkre kattintva olvashatsz: labirintusok generálása.