Algoritmusok működés közben
Algoritmusok működés közben: ingyenes interaktív szimuláció a StudyFi Labből. Közvetlenül a böngészőben fut, regisztráció és telepítés nélkül.
Rendezés és keresés lépésről lépésre
Kísérletek
Buborékrendezés
A buborékrendezés a szomszédos elemeket hasonlítja össze, és felcseréli őket, ha rossz sorrendben vannak. Minden menet után a legnagyobb elem a végére „buborékozik”, így a rendezetlen rész rövidül. Ha egy menetben nincs csere, a tömb rendezett. A legrosszabb esetben n(n−1)/2 összehasonlítás kell, vagyis O(n²).
Próbáld ki: Válaszd a fordított bemenetet, és vesd össze az összehasonlítások számát n(n−1)/2-vel. Utána próbálj egy majdnem rendezett tömböt — néhány menet után megáll.
Beszúró rendezés
A beszúró rendezés úgy működik, mint a kártyák rendezése a kézben: a bal oldali rész már rendezett, és minden következő elem (key) addig lép balra, amíg kisebbel nem találkozik. Közben a nagyobb elemek egy hellyel jobbra csúsznak. Véletlen adatokon O(n²), majdnem rendezett adatokon viszont közel O(n) — egy rendezett tömbhöz csak n−1 összehasonlítás kell.
Próbáld ki: Futtasd le egy majdnem rendezett, majd egy fordított tömbön. Hányszor több eltolás kell a fordítottnak?
Összefésülő rendezés
Az összefésülő rendezés kettévágja a tömböt, mindkét felét ugyanígy rendezi (rekurzió), majd a két rendezett felet összefésüli: mindig a két elülső elem közül a kisebbet veszi. A felezés log₂ n szintet ad, és minden szint mind az n elemet feldolgozza, így a futási idő mindig O(n log n). Egyenlőségnél a bal oldali elemet veszi, ezért stabil.
Próbáld ki: Próbálj ki egy fordított, majd egy majdnem rendezett, azonos méretű tömböt. Az összehasonlítások száma alig változik — a bemenet sorrendje alig számít.
Gyorsrendezés
A gyorsrendezés választ egy pivotot — itt a szakasz utolsó elemét (Lomuto-féle felosztás) —, és úgy rendezi át a szakaszt, hogy a kisebb elemek balra, a többiek jobbra kerüljenek. A pivot így a végleges helyére kerül, a két részt pedig ugyanígy rendezi. Átlagosan O(n log n), de ha a pivot rosszul oszt (például már rendezett vagy fordított tömbnél), O(n²)-re romlik.
Próbáld ki: Hasonlítsd össze a véletlen bemenetet a fordítottal. A fordított tömbnél a pivot mindig a legnagyobb vagy a legkisebb — figyeld, hogyan ugrik meg az összehasonlítások száma.
Lineáris és bináris keresés
A lineáris keresés egyenként nézi végig az elemeket, így a legrosszabb esetben n lépés kell — O(n). A bináris keresés csak rendezett tömbön működik: a közepére néz, és az eredménytől függően egy egész felet eldob. Minden lépés után legfeljebb a fele marad, ezért legfeljebb ⌈log₂(n+1)⌉ lépés elég — O(log n). 40 elemnél ez 6 lépés 40 helyett.
Próbáld ki: Állíts be 40 elemet, és keresd az utolsó értéket. Utána válassz egy számot, amely nincs a tömbben — hány lépés kell az egyes kereséseknek, hogy ezt kiderítsék?
Rendezőalgoritmusok versenye
Mind a négy algoritmus ugyanazt a bemenetet rendezi, és minden sávban egy lépés egy összehasonlítás vagy egy mozgatás. Az O(n²)-es algoritmusok (buborék és beszúró) a tömb méretével sokkal gyorsabban nőnek, mint az O(n log n)-esek (összefésülő és gyors). A sorrend a bemenettől is függ: majdnem rendezett tömbön gyakran a beszúró rendezés nyer.
Próbáld ki: Indítsd el a versenyt egy 40 elemű véletlen tömbbel, majd válts majdnem rendezettre. Változik a győztes?
Gyakori kérdések
Mi az a(z) Algoritmusok működés közben?
Algoritmusok működés közben: ingyenes interaktív szimuláció a StudyFi Labből. Közvetlenül a böngészőben fut, regisztráció és telepítés nélkül. Rendezés és keresés lépésről lépésre
Ingyenes a(z) Algoritmusok működés közben?
Igen. A(z) Algoritmusok működés közben teljesen ingyenes. Böngészőben fut számítógépen, tableten és telefonon, és nem kell hozzá fiók.
Mit fedezhetek fel ebben: Algoritmusok működés közben?
Buborékrendezés, Beszúró rendezés, Összefésülő rendezés, Gyorsrendezés, Lineáris és bináris keresés, Rendezőalgoritmusok versenye.
Mit mutat a(z) „Buborékrendezés” kísérlet?
A buborékrendezés a szomszédos elemeket hasonlítja össze, és felcseréli őket, ha rossz sorrendben vannak. Minden menet után a legnagyobb elem a végére „buborékozik”, így a rendezetlen rész rövidül. Ha egy menetben nincs csere, a tömb rendezett. A legrosszabb esetben n(n−1)/2 összehasonlítás kell, vagyis O(n²).
Mit mutat a(z) „Beszúró rendezés” kísérlet?
A beszúró rendezés úgy működik, mint a kártyák rendezése a kézben: a bal oldali rész már rendezett, és minden következő elem (key) addig lép balra, amíg kisebbel nem találkozik. Közben a nagyobb elemek egy hellyel jobbra csúsznak. Véletlen adatokon O(n²), majdnem rendezett adatokon viszont közel O(n) — egy rendezett tömbhöz csak n−1 összehasonlítás kell.
Dolgozatra készülsz?
Töltsd fel a jegyzeteidet, és a StudyFi szókártyákat, teszteket és podcastokat készít belőlük.