Bubble Sort Algorithm with Python a List példa segítségével

Tartalomjegyzék:

Anonim

Mi az a Bubble Sort?

A Bubble Sort egy rendezési algoritmus, amelyet a listaelemek növekvő sorrendbe rendezéséhez használnak 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, míg a második érték az első értéket veszi fel. Ha az első érték alacsonyabb, mint a második érték, akkor nem történik csere.

Ezt a folyamatot addig ismételjük, amíg a listában szereplő összes értéket összehasonlítják és szükség esetén fel nem cserélik. Minden iterációt rendszerint passznak nevezünk. A buborékok rendezése során a passzok száma megegyezik a lista elemeinek számával mínusz egy.

Ebben a Bubble Sorting in Python bemutatóban megtudhatja:

  • Mi az a Bubble Sort?
  • A Bubble Sort algoritmus megvalósítása
  • Optimalizált Bubble Sort algoritmus
  • Vizuális ábrázolás
  • Python példák
  • Kód Magyarázat
  • Buborékfajta előnyei
  • Buborékfajta hátrányai
  • A Bubble Sort összetettségének elemzése

A Bubble Sort algoritmus megvalósítása

Három (3) szakaszra bontjuk a megvalósítást, nevezetesen a problémát, a megoldást és az algoritmust, amellyel bármely nyelvhez kódot írhatunk.

A probléma

Az elemek listája véletlenszerű sorrendben van megadva, é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 két szomszédos elem összehasonlításával és felcserélésével, ha az első érték magasabb, mint a második érték.

Az eredmény a következő legyen:

[3,6,9,21,33]

Algoritmus

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

1. lépés: Szerezze meg az elemek teljes számát. Szerezd meg a megadott lista összes elemét

2. lépés: Határozza meg az elvégzendő külső passzusok számát (n - 1). Hossza lista mínusz egy

3. lépés: Végezze el a belső passzokat (n - 1) a külső menethez 1. Szerezze meg 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ő, akkor cserélje fel a pozíciókat

4. lépés) Ismételje meg a 3. lépést, amíg el nem éri a külső menetet (n - 1). Szerezze be a lista következő elemét, majd ismételje meg a 3. lépésben végrehajtott folyamatot, amíg az összes értéket a megfelelő növekvő sorrendbe nem helyezi.

5. lépés: Adja vissza az eredményt, amikor az összes passz elkészült. Visszaadja a rendezett lista eredményeit

6. lépés: Optimalizálja az algoritmust

Kerülje a felesleges 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, amelyeket növekvő sorrendben rendeztek, akkor korán megszakíthatjuk a ciklust.

Optimalizált Bubble Sort algoritmus

Alapértelmezés szerint a Python buborék-rendezés algoritmusa ö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, akkor az összes érték összehasonlítása idő- és erőforráspazarlás.

A buborék rendezés optimalizálása segít elkerülni a felesleges ismétléseket, időt és erőforrásokat takaríthat 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 iterációjára. Az iteráció befejeződik, és a következő folyamat elindul, amíg a folyamat be nem fejeződik, amint az az alábbi Bubble Sort példában látható.

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

1. lépés: Hozzon létre egy flag változót, amely figyeli, hogy történt-e csere a belső hurokban

2. lépés) Ha az értékek felcserélték a pozícióikat, folytassa a következő iterációval

3. lépés: Ha az előnyök nem cseréltek helyet, akkor fejezze be a belső hurkot, és folytassa a külső hurkot.

Az optimalizált buborék-rendezés hatékonyabb, mivel csak a szükséges lépéseket hajtja végre, és kihagyja azokat, amelyekre nincs szükség.

Vizuális ábrázolás

Öt elemből álló listát adva a következő képek szemléltetik, hogy a buborék hogyan rendezi az értékeket az osztályozás során

A következő kép a nem rendezett listát mutatja

Első iteráció

1. lépés)

A 21. és 6. értékeket összehasonlítjuk annak ellenőrzésével, hogy melyik nagyobb a másiknál.

A 21 nagyobb, mint 6, tehát a 21 a 6-ot foglalja el, míg a 6 a 21-et foglalta el

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

2. lépés)

Összehasonlítjuk a 21. és 9. értéket.

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

Az új lista most a fentiekhez hasonló

3. lépés)

A 21. és a 33. értéket összehasonlítva megtaláljuk a nagyobbat.

A 33 érték nagyobb, mint 21, így nem történik cserélés.

4. lépés)

A 33. és 3. értékeket összehasonlítjuk, hogy megtaláljuk a nagyobbat.

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

Az első iteráció végén rendezett lista olyan, mint a fenti

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

Az alábbi kód bemutatja a Bubble Sort algoritmus Python-ban történő megvalósítását.

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

A fenti buborék rendezési program Pythonban történő végrehajtása a következő eredményeket eredményezi

[6, 9, 21, 3, 33]

Kód Magyarázat

A Python Bubble Sort programkód magyarázata a következő

ITT,

  1. Meghatározza a bubbleSort függvényt, amely elfogadja az aSeq paramétert. A kód nem ad ki semmit.
  2. Megkapja a tömb hosszát, és az n változóhoz rendeli az értéket. A kód nem ad ki semmit
  3. Elindít egy for ciklust, amely a buborék rendezési algoritmust (n - 1) futtatja. Ez a külső hurok. A kód nem ad ki semmit
  4. Meghatározza a flag változót, amely arra szolgál, hogy megállapítsa, történt-e csere vagy sem. Ez optimalizálási célokat szolgál. A kód nem ad ki semmit
  5. Elkezdi 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ással ellenőrzi, hogy a bal oldalon lévő érték nagyobb-e, mint a közvetlen jobb oldalon. A kód nem ad ki semmit.
  7. Hozzárendeli aSeq [j] értékét a tmp időbeli változóhoz, ha a feltétel igaznak bizonyul. A kód nem ad ki semmit
  8. ASeq [j + 1] értékét aSeq [j] pozíciójához rendeljük. A kód nem ad ki semmit
  9. A tmp változó értékét aSeq [j + 1] pozícióhoz rendeljük. A kód nem ad ki semmit
  10. A flag változóhoz 1 értéket rendelünk, jelezve, hogy cserére került sor. A kód nem ad ki semmit
  11. Az if utasítás segítségével ellenőrzi, hogy a változó zászló értéke-e 0. A kód nem ad ki semmit
  12. Ha az érték 0, akkor hívjuk a break ciklust, amely kilép a belső hurokból.
  13. Visszaadja aSeq értékét rendezés után. A kód a rendezett listát adja ki.
  14. Meghatározza az el változót, amely véletlenszerű számok listáját tartalmazza. A kód nem ad ki semmit.
  15. Hozzárendeli a bubbleSort függvény értékét egy változó eredményhez.
  16. Kiírja a változó eredmény értékét.

Buborékfajta előnyei

Az alábbiakban bemutatjuk a buborék rendezési algoritmus néhány előnyét

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

Buborékfajta hátrányai

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

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

A Bubble Sort összetettségének elemzése

A komplexitásnak három típusa van:

1) Rendezés összetettsége

A rendezés bonyolultsága a végrehajtási idők és a tér rendezéséhez szükséges terület kifejezésére szolgál. A buborék rendezése (n - 1) ismétlést végez a lista rendezéséhez, ahol n a lista összes elemének száma.

2) Az idő összetettsége

A buborékfajta időbeli összetettsége O (n 2 )

Az idő bonyolultsága a következő kategóriákba sorolható:

  • Legrosszabb esetben - itt a megadott lista csökkenő sorrendben van. Az algoritmus a végrehajtások maximális számát hajtja végre, amelyet [Big-O] O (n 2 ) formában fejeznek ki.
  • Legjobb eset - ez akkor fordul elő, amikor a megadott lista már rendezve van. Az algoritmus végrehajtja a végrehajtások minimális számát, amelyet [Big-Omega] Ω (n) formájában fejeznek ki.
  • Átlagos eset - ez akkor fordul elő, ha a lista véletlenszerű sorrendben van. Az átlagos komplexitás [Big-theta] ⊝ (n 2 )

3) A tér összetettsége

A tér bonyolultsága méri a lista rendezéséhez szükséges extra hely mennyiségét. A buborék-rendezéshez csak egy (1) extra hely szükséges az értékek cseréjéhez használt időbeli változó számára. Ezért térösszetétele O (1).

Összegzés

  • A buborék rendezési algoritmus két szomszédos érték összehasonlításával és felcserélésével működik, ha a bal oldali érték kisebb, mint a jobb oldali.
  • A buborék rendezési algoritmus megvalósítása viszonylag egyszerű a Pythonban. Csak ciklusokra és if utasításokra kell használni.
  • A buborék rendezési algoritmus által megoldott probléma az, hogy véletlenszerű tételeket vesz fel és rendezett listává alakítja.
  • Az adatstruktúrában található buborék rendezési algoritmus akkor teljesít legjobban, ha a lista már rendezve van, mivel minimális számú iterációt hajt végre.
  • A buborék rendezési algoritmus nem működik jól, ha a lista fordított sorrendben van.
  • A buborékoló fajta O (n 2 ) időbeli összetettsége és O (1) térbeli összetettsége
  • A buborékos rendező algoritmus a legalkalmasabb tudományos célokra, és nem a valós alkalmazásokhoz.
  • Az optimalizált buborék-rendezés hatékonyabbá teszi az algoritmust azáltal, hogy kihagyja a felesleges iterációkat a már rendezett értékek ellenőrzésekor.