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

Mi az a Bubble Rendezés?

Bubble Rendezés egy rendezési algoritmus, amellyel a listaelemeket két szomszédos érték összehasonlításával növekvő sorrendbe rendezik. Ha az első érték magasabb, mint a második, akkor az első érték a második, míg a második érték az első érték pozíciót foglalja el. Ha az első érték kisebb, mint a második, akkor nem történik csere.

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 tanulni fogsz:

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 nyelvhez kódot tudunk írni.

A probléma

Véletlenszerű sorrendben adjuk meg a tételek listáját, és szeretnénk a tételeket rendezetten elrendezni

Vegye figyelembe a következő listát:

[21,6,9,33,3]

A megoldás

Ismételje meg a listát, hasonlítson össze két szomszédos elemet, és cserélje ki ő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) Szerezze meg az elemek teljes számát. Nézze meg az adott lista elemeinek teljes számát

Step 2) Határozza meg a végrehajtandó külső lépések számát (n – 1). A hossza lista mínusz egy

Step 3) Végezze el a belső áthaladást (n – 1) alkalommal az 1. külső lépéshez. Vegye ki az első elem értékét, és hasonlítsa össze a második értékkel. Ha a második érték kisebb, mint az első érték, akkor cserélje fel a pozíciókat

Step 4) Ismételje meg a 3. lépést, amíg el nem éri a külső áthaladást (n – 1). Szerezze be a következő elemet a listából, majd ismételje meg a 3. lépésben végrehajtott eljárást, amíg az összes értéket a megfelelő növekvő sorrendbe nem helyezi.

Step 5) Adja vissza az eredményt, ha minden passz megtörtént. A rendezett lista eredményeinek visszaadása

Step 6) Algoritmus optimalizálása

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) Hozzon létre egy jelzőváltozót, amely figyeli, hogy történt-e csere a belső hurokban

Step 2) Ha az értékek pozíciót cseréltek, folytassa a következő iterációval

Step 3) Ha az előnyök nem cserélték fel a pozíciókat, fejezze be a belső hurkot, és folytassa a külső hurokkal.

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ó lista alapján a következő képek szemléltetik, hogy a buborékos rendezés hogyan iterál 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.

A 21 nagyobb, mint 6, tehát a 21 a 6 által elfoglalt pozíciót veszi fel, míg a 6 a 21 által elfoglalt pozíciót

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.

A 21 nagyobb, mint 9, ezért felcseréljük a 21 és 9 pozícióit

Az új lista most a fenti

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, így nem történik csere.

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évő rendezett lista hasonló a fentihez

Második iteráció

Az új lista a második iteráció után a következő

Harmadik iteráció

Az új lista a harmadik iteráció után a következő

Negyedik iteráció

Az új lista a negyedik iteráció után 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

[6, 9, 21, 3, 33]

Kód Magyarázat

A magyarázat a Python Bubble A programkód rendezése a következő

ITT,

1. Egy bubbleSort függvényt határoz meg, amely elfogadja a theSeq paramétert. A kód nem ad ki semmit.
2. Lekéri a tömb hosszát, és hozzárendeli az értéket egy n változóhoz. A kód nem ad ki semmit
3. Elindít egy for ciklust, amely lefuttatja a buborékrendezési algoritmust (n – 1) alkalommal. Ez a külső hurok. A kód nem ad ki semmit
4. 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 az optimalizálás célja. A kód nem ad ki semmit
5. 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.
6. 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.
7. A Seq[j] értékét hozzárendeli egy tmp időbeli változóhoz, ha a feltétel kiértékelése igaz. A kód nem ad ki semmit
8. A Seq[j + 1] értéke a Seq[j] pozíciójához van rendelve. A kód nem ad ki semmit
9. A tmp változó értéke a Seq[j + 1] pozícióhoz van hozzárendelve. A kód nem ad ki semmit
10. A jelzőváltozóhoz 1-es érték tartozik, jelezve, hogy csere történt. A kód nem ad ki semmit
11. Egy if utasítással ellenőrzi, hogy a változó jelzőjének értéke 0-e. A kód nem ad ki semmit
12. Ha az érték 0, akkor a belső ciklusból kilépő break utasítást hívjuk.
13. A rendezés után a theSeq értékét adja vissza. A kód a rendezett listát adja ki.
14. Meghatároz egy el változót, amely véletlen számok listáját tartalmazza. A kód nem ad ki semmit.
15. A bubbleSort függvény értékét hozzárendeli egy változó eredményhez.
16. Kiírja a változó eredményének értékét.

Bubble fajta előnyöket

Az alábbiakban bemutatjuk a buborékrendezési algoritmus előnyeit

• Könnyen érthető
• Nagyon jól teljesít, ha a lista már vagy majdnem rendezve van
• 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

Az alábbiakban bemutatjuk a buborékrendezési algoritmus néhány hátrányát

• Nem teljesít jól nagy listák rendezésekor. Túl sok időt és erőforrást igényel.
• Leginkább tanulmányi célokra használják, nem pedig valós alkalmazásra.
• 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 komplexitásnak három típusa van:

1) Rendezés bonyolultsága

A rendezés bonyolultsága a végrehajtási idők és a lista rendezéséhez szükséges hely mennyiségének kifejezésére szolgál. A buborékos rendezés (n – 1) iterációkat hajt végre 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 rendezve van. Az algoritmus a minimális számú végrehajtást hajtja végre, amely [Big-Omega] Ω(n)
• Átlagos eset – ez akkor fordul elő, ha a lista véletlenszerű sorrendben van. Az átlagos komplexitást [Big-theta] ⊝(n²)

3) A tér összetettsége

A tér összetettsége azt méri, hogy mennyi extra hely szükséges a lista rendezéséhez. A buborékos rendezés csak egy (1) extra helyet igényel az értékek felcseréléséhez használt időbeli változó számára. Ezért a térkomplexitása O (1).

Összegzésként

• A buborékos rendezési algoritmus úgy működik, hogy összehasonlít két szomszédos értéket, és felcseréli őket, ha a bal oldali érték kisebb, mint a jobb oldali érték.
• A buborékrendezési algoritmus megvalósítása viszonylag egyszerű Python. Csak a ciklusokhoz és az if utasításokhoz kell használnia.
• A buborékos rendezési algoritmus által megoldott probléma az, hogy véletlenszerű tétellistát vesz, és rendezett listává alakítja.
• Az adatszerkezetben a buborékos rendezési algoritmus akkor teljesít a legjobban, ha a lista már rendezve van, mivel minimális számú iterációt hajt végre.
• A buborékos rendezési algoritmus nem teljesít jól, ha a lista fordított sorrendben van.
• A buborékoló rendezés időbeli összetettsége O (n²) és O térkomplexitása (1)
• A buborékos rendezési algoritmus a legalkalmasabb a tudományos célokra, és nem a valós alkalmazásokra.
• Az optimalizált buborékrendezés hatékonyabbá teszi az algoritmust azáltal, hogy kihagyja a szükségtelen iterációkat a már rendezett értékek ellenőrzésekor.