Buborékfajta

PerformanceEdit

A buborékfajtának a legrosszabb esete és az átlagos komplexitása О (n2), ahol n a rendezendő elemek száma. A legtöbb gyakorlati rendezési algoritmus lényegesen jobb komplexitással rendelkezik a legrosszabb vagy átlagos esetben, gyakran O (n log n). Még más О (n2) rendezési algoritmusok is, például a beszúrási rendezés, általában gyorsabban futnak, mint a buborékok, és nem bonyolultabbak. Ezért a buborék rendezés nem praktikus rendezési algoritmus.

A buborék rendezés egyetlen jelentős előnye a legtöbb más algoritmussal szemben, még a quicksort, de nem a beszúrás rendezése, az, hogy képes észlelni a lista rendezését hatékonyan épül be az algoritmusba. Amikor a lista már rendezve van (a legjobb esetben), a buborék rendezésének összetettsége csak O (n). Ezzel szemben a legtöbb más algoritmus, még azok is, amelyek jobb átlagos esetbonyolultsággal bírnak, teljes rendezési folyamatát a halmazon hajtják végre, és így összetettebbek. Azonban nemcsak a beillesztéses rendezés osztja meg ezt az előnyt, hanem jobban teljesít egy olyan listán is, amely lényegében rendezve van (kevés inverzióval rendelkezik). Ezenkívül, ha ez a viselkedés kívánatos, akkor triviálisan hozzáadható bármely más algoritmushoz, ha az algoritmus futtatása előtt ellenőrzi a listát.

Nagy gyűjtemények esetén kerülni kell a buborékok rendezését. Ez nem lesz hatékony fordított sorrendű gyűjtemény esetén.

Nyulak és TurtlesEdit

Az a távolság és irány, amelyet az elemeknek a rendezés során kell elmozdítaniuk, meghatározza a buborék rendezés teljesítményét, mert az elemek különböző irányban mozognak, különböző sebességgel. Az az elem, amelynek a lista vége felé kell haladnia, gyorsan mozoghat, mert részt vehet egymást követő csereügyletekben. Például a lista legnagyobb eleme minden cserét megnyer, így rendezett helyzete az első menetben, még akkor is, ha a kezdet közelében kezdődik. Másrészt egy elem, amelynek a lista eleje felé kell haladnia, nem mozoghat gyorsabban egy lépésnél, mint egy lépés, ezért az elemek nagyon lassan mozognak a kezdet felé. a legkisebb elem a lista végén található, n-1 továbbításra lesz szükség ahhoz, hogy az elejére mozduljon. Ez azt eredményezte, hogy az ilyen típusú elemeket nyulaknak, illetve teknősöknek nevezték el az Aesop “meséjében szereplő karakterek után” A teknős és a nyúl.

Különböző erőfeszítéseket tettek a teknősök kiküszöbölésére a buborékfajták sebességének javítása érdekében. A koktélfajta kétirányú buborékfajta, amely elejétől a végéig halad, majd megfordítja önmagát, végről elejére haladva. Meglehetősen jól képes megmozgatni a teknősöket, de megtartja az O (n2) komplexitást a legrosszabb esetben. A fésűs rendezés összehasonlítja az elemeket, amelyeket nagy rések választanak el egymástól, és rendkívül gyorsan megmozgathatja a teknősöket, mielőtt egyre kisebb hézagokba kezdene a lista elsimítása érdekében. Átlagos sebessége összehasonlítható az olyan gyorsabb algoritmusokkal, mint a quicksort.

Lépésről lépésre szerkesztés

Vegyünk egy “5 1 4 2 8” számtömböt, és válasszuk a tömböt a legalacsonyabbtól szám a legnagyobb számra a buborék rendezésével. Minden lépésben félkövérrel írt elemeket hasonlítanak össze. Három lépésre lesz szükség;

Első lépés (5 1 4 2 8) → (1 5 4 2 8), Itt az algoritmus összehasonlítja az első két elemet, és 5 > 1. (1 5 4 2 8) → (1 4 5 2 8), Csere 5-től kezdve > 4 (1 4 5 2 8) → (1 4 2 5 8), Csere, mivel 5 > 2 (1 4 2 5 8) → (1 4 2 5 8), Most, mivel ezek az elemek már rendben vannak (8 > 5), az algoritmus nem cseréli fel őket. Második menet (1 4 2 5 8) → (1 4 2 5 8) (1 4 2 5 8) → (1 2 4 5 8), Csere 4 > 2 ( 1 2 4 5 8) → (1 2 4 5 8) (1 2 4 5 8) → (1 2 4 5 8)

A tömb már rendezve van, de az algoritmus nem tudja, hogy elkészült-e . Az algoritmusnak egyetlen egész lépésre van szüksége cseré nélkül, hogy tudja, hogy rendezve van.