A Bubble Sort egy egyszerű algoritmus, amelyet a elemek tömb formájában, n elemek számával. A Bubble Sort az összes elemet egyesével hasonlítja össze, és értékeik alapján rendezi őket.
Ha az adott tömböt növekvő sorrendbe kell rendezni, akkor a buborék rendezése a tömb első elemének összehasonlításával kezdődik. a második elem, ha az első elem nagyobb, mint a második elem, akkor mindkét elemet felcseréli, majd folytatja a második és a harmadik elem összehasonlítását, és így tovább.
Ha összesen van n elemeket, akkor ezt a folyamatot meg kell ismételnünk n-1 alkalommal.
Buborékfajta néven ismert, mert minden teljes iterációval az adott tömb legnagyobb eleme az utolsó hely vagy a legmagasabb index felé buborékol, akárcsak egy vízbuborék emelkedik fel a víz felszínére.
A válogatás úgy történik, hogy végig lépünk az összes tömbön. az elemeket egyenként, összehasonlítva a szomszédos elemmel, és szükség esetén felcserélve őket. Első lépésként ismerje meg a rendezés alapjairól szóló tudnivalókat.
A Bubble Sort Algorithm megvalósítása
Az alábbiakban bemutatjuk a buborékok rendezésének lépéseit (egy adott tömb rendezéséhez növekvő sorrendben):
- Az első elemmel (index = 0) kezdve hasonlítsa össze az aktuális elemet a tömb következő elemével.
- Ha az aktuális elem nagyobb, mint a következő elem a tömbből, cserélje fel őket.
- Ha az aktuális elem kevesebb, mint a következő elem, lépjen a következő elemre. Ismételje meg az 1. lépést.
Vizsgáljuk meg a {5, 1, 6, 2, 4, 3}
értékeket tartalmazó tömböt annak ábrázolása, hogy a buborék rendezése hogyan rendezi az adott tömböt.
Tehát, amint a fenti ábrán láthatjuk, a az első iteráció, 6 az utolsó indexhez kerül, ami a számára megfelelő pozíció.
Hasonlóan a második iteráció után, 5 a második utolsó indexnél lesz, és így tovább.
Ideje megírni a kódot buborék rendezéshez:
Bár a fenti logika rendezni fogja a nem rendezett tömböt, a fenti algoritmus mégsem hatékony, mert a fenti logika szerint a külső for loop akkor is végrehajtja a 6 ismétlést, ha a tömb rendezésre kerül a második iteráció után.
Tehát egyértelműen optimalizálhatjuk algoritmusunkat.
Optimalizált buborék rendezési algoritmus
A buborékunk optimalizálása A rendezési algoritmus segítségével bevezethetünk egy flag elemet annak figyelemmel kísérésére, hogy az elemek felcserélődnek-e a belső for hurokban.
Ezért a belső for ciklusban mindig ellenőrizzük, hogy az elemek cseréje megtörténik-e vagy sem.
Ha egy adott iterációnál nem történt cserélés hely azt jelenti, hogy a tömb rendezésre került, és kiugorhatunk a for ciklusból, ahelyett, hogy az összes iterációt végrehajtanánk.
Vegyük fontolóra egy tömböt értékekkel {11, 17, 18, 26, 23}
Az alábbiakban bemutatjuk egy képi ábrázolást arról, hogy az optimalizált buborék-rendezés hogyan rendezi az adott tömböt.
Mint láthatjuk, az első iterációban cserére került sor, ezért az flag értéket 1, ennek eredményeként a végrehajtás ismét belép a for ciklusba. De a második iterációban nem történik csere, ezért az flag értéke megmarad 0, és a végrehajtás kitör a ciklusból.
A fenti kódban a bubbleSort függvényben, ha j iteráció egyetlen teljes ciklusa (belső for hurok), nem történik cserélés, majd flag marad 0, majd kitörünk a for hurokból, mert a tömb már rendezve van.
A buborékok rendezésének összetettség-elemzése
A buborék-rendezésnél az n-1 összehasonlításokat az 1. lépésben kell elvégezni, n-2 a 2. menetben, n-3 a 3. menetben és így tovább. Tehát az összehasonlítások teljes száma a következő lesz:
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2i.e O (n2)
Ezért a Bubble Sort időbeli összetettsége O (n2).
A Bubble Sort fő előnye az algoritmus egyszerűsége.
A Bubble Sort térbeli összetettsége O (1), mert csak egyetlen további memóriaterületre van szükség, azaz a temp változóhoz.
Ezenkívül a legjobb esetben az idő összetettsége O (n) lesz, amikor a lista már rendezve van.
Az alábbiakban a Bubble Sort algoritmus idő és tér összetettségét mutatjuk be.
Most, hogy megtanultuk a Bubble sort algoritmust, megnézheti ezeket a rendezési algoritmusokat és alkalmazásukat is:
- Insertion Sort
- Selection Sort
- Gyors rendezés
- Rendezés egyesítése
- Halom rendezés
- Rendezés számlálása
