Bubble Rendezési algoritmus ezzel Python a listapélda segítségével

⚡ Okos összefoglaló

BubblA rendezés növekvő sorrendbe rendezi a listaelemeket az egymás melletti értékek ismételt összehasonlításával és felcserélésével.ping akkor, amikor a bal oldali elem nagyobb. Ez az egyszerű összehasonlító rendezés kis vagy közel rendezett adathalmazokhoz illik, és hatékonyan tanítja meg az alapvető rendezési logikát.

🔁 Alapmechanizmus: BubblAz e rendezés összehasonlítja a szomszédos elemek párjait, és felcseréli őket, minden menet után a legnagyobb rendezetlen értéket helyezve a végső pozíciójába.
🇧🇷 Optimalizált változat: Egy flag változó érzékeli, ha egy menet nem végez cserét, ezzel korán megszakítva a ciklust, így egy már rendezett lista egyetlen kereséssel befejeződik.
🐍 Python Végrehajtás: Két beágyazott ciklus és egy ideiglenes változó rendezi a listát, és a bejárás minden sort a pontos viselkedéséhez rendel.
📊 Komplexitási profil: Az időbonyolultság a legrosszabb és átlagos esetben O(n²), legjobb esetben Ω(n), állandó O(1) helyigénnyel.
🎯 Legjobban illeszkedő: BubblAz e-rendezés kiválóan alkalmas tanításra és közel rendezett listák készítésére, de nagy adathalmazokon gyengébben teljesít a fejlett algoritmusokhoz képest.

További információk

Mi az a Bubble Rendezés?

Bubble Rendezés egy rendező algoritmus, amely listaelemeket rendez növekvő sorrendbe két szomszédos érték összehasonlításával. Ha az első érték magasabb, mint a második érték, akkor az első érték a második érték pozícióját veszi fel, míg a második érték az első érték pozícióját. Ha az első érték alacsonyabb, mint a második érték, akkor nincs csere.ping kész.

Ezt a folyamatot addig ismételjük, amíg a listában szereplő összes értéket össze nem hasonlítjuk és szükség esetén felcseréljük. Minden iterációt általában passznak neveznek. A buborékos rendezésben a lépések száma megegyezik a lista elemeinek számával mínusz egy.

Ebben Bubble Rendezés Python oktatói Megtanulod a megoldandó problémát, optimalizált formáját, egy lépésről lépésre bemutatott vizuális bejárást, egy működőképes... Python program, és annak teljesítményjellemzői.

Végrehajtása a Bubble Rendezési algoritmus

A megvalósítást három (3) lépésre bontjuk, nevezetesen a problémára, a megoldásra és az algoritmusra, amellyel bármilyen nyelven kódot írhatunk.

A probléma

A tételek listája véletlenszerű sorrendben van megadva, és szeretnénk a tételeket rendezett módon elrendezni.

Vegye figyelembe a következő listát:

[21, 6, 9, 33, 3]

A megoldás

Iteráld végig a listát, összehasonlítva két szomszédos elemet, és cseréld felping őket, ha az első érték magasabb, mint a második érték.

Az eredménynek a következőnek kell lennie:

[3, 6, 9, 21, 33]

Algoritmus

A buborékrendezési algoritmus a következőképpen működik:

Step 1) Számold ki az elemek teljes számát. Számold ki az adott lista elemeinek teljes számát.

Step 2) Határozza meg a külső menetek számát (n – 1). A hossza lista mínusz egy.

Step 3) Végezzen el belső meneteket (n – 1) alkalommal az 1. külső menethez. Hasonlítsa össze az első elem értékét a második értékkel. Ha a második érték kisebb, mint az első érték, akkor cserélje meg a pozíciókat.

Step 4) Ismételje meg a 3. lépés meneteit, amíg el nem éri a külső menetet (n – 1). Vegye ki a lista következő elemét, majd ismételje meg a 3. lépésben végrehajtott folyamatot, amíg az összes érték a megfelelő növekvő sorrendbe nem kerül.

Step 5) Az összes menet elvégzése után adja vissza az eredményt. A rendezett lista eredményeit adja vissza.

Step 6) Optimalizáló algoritmus.

Kerülje a szükségtelen belső passzokat, ha a lista vagy a szomszédos értékek már rendezve vannak. Például, ha a megadott lista már tartalmaz elemeket, amelyek növekvő sorrendben vannak rendezve, akkor korán megszakíthatjuk a hurkot.

optimalizált Bubble Rendezési algoritmus

Alapértelmezés szerint a buborékok rendezési algoritmusa Python összehasonlítja a lista összes elemét, függetlenül attól, hogy a lista már rendezve van-e vagy sem. Ha az adott lista már rendezve van, az összes érték összehasonlítása idő- és erőforráspazarlás.

A buborékrendezés optimalizálása segít elkerülni a szükségtelen iterációkat, valamint időt és erőforrásokat takarít meg.

Például, ha az első és a második elem már rendezve van, akkor nincs szükség a többi érték ismétlésére. Az iteráció befejeződik, és a következő kezdődik, amíg a folyamat az alábbiak szerint be nem fejeződik Bubble Rendezési példa.

Az optimalizálás a következő lépésekkel történik:

Step 1) Hozz létre egy flag változót, amely figyeli, hogy van-e swapping a belső körben történt.

Step 2) Ha az értékek felcserélődtek, folytassa a következő iterációval.

Step 3) Ha az értékek nem cseréltek helyet, akkor fejezze be a belső ciklust, és folytassa a külső ciklussal.

Az optimalizált buborékok rendezése hatékonyabb, mivel csak a szükséges lépéseket hajtja végre, és kihagyja a nem szükséges lépéseket.

Vizuális ábrázolás

Egy öt elemből álló listán a következő képek szemléltetik, hogyan halad végig a buborékos rendezés az értékeken a rendezés során.

A következő kép a rendezetlen listát mutatja:

Első iteráció

Step 1)

A 21-es és 6-os értékeket a rendszer összehasonlítja, hogy ellenőrizze, melyik nagyobb a másiknál.

Ha a 21 nagyobb, mint a 6, akkor a 21 a 6 által elfoglalt helyet foglalja el, míg a 6 azt a helyet, amelyet korábban a 21 foglalt el.

A módosított listánk most úgy néz ki, mint a fenti.

Step 2)

A 21-es és 9-es értékeket összehasonlítjuk.

Mivel a 21 nagyobb, mint a 9, felcseréljük a 21 és a 9 helyét.

Az új lista most a fentiek szerint alakul.

Step 3)

A 21-es és 33-as értékeket a rendszer összehasonlítja, hogy megtalálja a nagyobbat.

A 33-as érték nagyobb, mint 21, ezért nincs csere.ping zajlik.

Step 4)

A 33-es és 3-as értékeket a rendszer összehasonlítja, hogy megtalálja a nagyobbat.

A 33 érték nagyobb, mint 3, ezért felcseréljük a pozíciójukat.

Az első iteráció végén látható rendezett lista hasonló a fentihez.

Második iteráció

A második iteráció utáni új lista a következő:

Harmadik iteráció

A harmadik iteráció utáni új lista a következő:

Negyedik iteráció

A negyedik iteráció utáni új lista a következő:

Python Példák

A következő kód bemutatja, hogyan kell megvalósítani a Bubble Rendezési algoritmus Python.

def bubbleSort(theSeq):
    n = len(theSeq)

    for i in range(n - 1):
        flag = 0

        for j in range(n - 1):
            if theSeq[j] > theSeq[j + 1]:
                tmp = theSeq[j]
                theSeq[j] = theSeq[j + 1]
                theSeq[j + 1] = tmp
                flag = 1

        if flag == 0:
            break

    return theSeq

el = [21, 6, 9, 33, 3]
result = bubbleSort(el)
print(result)

A fenti buborékrendezési program végrehajtása Python a következő eredményeket produkálja:

[3, 6, 9, 21, 33]

Code Magyarázat

A magyarázat a Python BubblA rendezési programkód a következő:

ITT,

Egy bubbleSort függvényt határoz meg, amely elfogadja a theSeq paramétert. A kód nem ad ki semmit.
Kiértékeli a tömb hosszát, és az értéket egy n változóhoz rendeli. A kód nem ad ki semmit.
Elindít egy for ciklust, amely lefuttatja a buborékos rendezési algoritmust (n – 1) alkalommal. Ez a külső ciklus. A kód nem ad ki semmit.
Meghatároz egy jelzőváltozót, amely annak meghatározására szolgál, hogy megtörtént-e a csere vagy sem. Ez optimalizálási célokat szolgál. A kód nem ad ki semmit.
Elindítja a belső ciklust, amely összehasonlítja a lista összes értékét az elsőtől az utolsóig. A kód nem ad ki semmit.
Az if utasítást használja annak ellenőrzésére, hogy a bal oldalon lévő érték nagyobb-e, mint a közvetlenül jobb oldalon. A kód nem ad ki semmit.
A theSeq[j] értékét hozzárendeli a tmp időbeli változóhoz, ha a feltétel igazra értékelődik. A kód nem ad ki semmit.
A theSeq[j + 1] értéke a theSeq[j] pozíciójához van rendelve. A kód nem ad ki semmit.
A tmp változó értéke a theSeq[j + 1] pozícióhoz van rendelve. A kód nem ad ki semmit.
A flag változó 1-es értéket kap, jelezve, hogy csere történt. A kód nem ad ki semmit.
Egy if utasítással ellenőrzi, hogy a flag változó értéke 0-e. A kód nem ad ki semmit.
Ha az érték 0, akkor a belső ciklusból kilépő break utasítást hívjuk.
A rendezés után a theSeq értékét adja vissza. A kód a rendezett listát adja ki.
Meghatároz egy el változót, amely véletlen számok listáját tartalmazza. A kód nem ad ki semmit.
A bubbleSort függvény értékét hozzárendeli egy változó eredményhez.
Kiírja a változó eredményének értékét.

Bubble fajta előnyöket

A buborékos rendezési algoritmus néhány előnye a következő:

Könnyen érthető.
Nagyon jól teljesít, ha a lista már rendezett vagy majdnem rendezett.
Nem igényel nagy memóriát.
Könnyű megírni az algoritmus kódját.
A helyigény minimális más rendezési algoritmusokhoz képest.

Bubble sort Hátrányok

A buborékos rendezési algoritmus néhány hátránya a következő:

Nem teljesít jól nagy listák rendezésekor. Túl sok időt és erőforrást igényel.
Leginkább tudományos célokra használják, nem pedig a valós alkalmazásokban.
A lista rendezéséhez szükséges lépések száma n nagyságrendű².

A komplexitás elemzése Bubble Rendezés

A bonyolultságnak három típusa van:

1) Rendezés bonyolultsága

A rendezési bonyolultságot a lista rendezéséhez szükséges végrehajtási idő és hely mennyiségének kifejezésére használjuk. A buborékos rendezés (n – 1) iterációt végez a lista rendezéséhez, ahol n a lista elemeinek teljes száma.

2) Időbeli összetettség

A buborékrendezés időbonyolultsága O(n²).

Az időbonyolítások a következő kategóriákba sorolhatók:

Legrosszabb esetben – itt van a megadott lista csökkenő sorrendben. Az algoritmus a maximális számú végrehajtást hajtja végre, amelyet [Big-O] O(n²).
Legjobb eset – ez akkor fordul elő, ha a megadott lista már rendezett. Az algoritmus a minimális végrehajtási számot hajtja végre, amelyet [Big-Omega] Ω(n)-ként fejezünk ki.
Átlagos eset – ez akkor fordul elő, ha a lista véletlenszerű sorrendben van. Az átlagos komplexitást a következőképpen ábrázoljuk: [Big-theta] ⊝(n²).

3) A tér összetettsége

A helybonyolultság a lista rendezéséhez szükséges extra hely mennyiségét méri. A buborékos rendezés csak egy (1) extra helyet igényel a swap-hoz használt időbeli változó számára.ping értékek. Ezért a térkomplexitása O(1).

GYIK

BubblAz e-rendezés ritkán fut éles mesterséges intelligenciában, de segít megtanítani az adat-előkészítés mögött álló rendezési logikát. A gépi tanulási folyamatok gyorsabb algoritmusok segítségével rendezik a jellemzőket, pontszámokat és predikciókat, míg a buborékos rendezés tisztábbá teszi az összehasonlítás és csere koncepcióját a kezdők számára.

Igen. A mesterséges intelligencia asszisztensei buborékos rendezést is tudnak írni. Python, Javavagy C++ és hozzáadhatják a rendezett lista elején leállító optimalizálási jelzőt. Gyorsabb algoritmusokat is javasolhatnak, amikor az adathalmaz nagyra nő.

Buborékrendezésnek nevezik, mert a nagyobb értékek minden egyes menettel fokozatosan „felbuborékolnak” a lista végére, hasonlóan ahhoz, ahogy a légbuborékok a víz felszínére emelkednek, míg a kisebb értékek a lista elejére süllyednek.

BubblA rendezés O(n²) idő alatt fut, ami jóval lassabb, mint a gyorsrendezés és az összevont rendezés O(n log n) idő alatt. BubblAz elektronikus rendezés kisebb esetekre vagy oktatási példákra alkalmas, míg a gyorsrendezés és az egyesítéses rendezés hatékonyan kezeli a nagy, valós adathalmazokat.