Buborékos rendezés vs beszúrásos rendezés
A buborékos rendezés egy rendezési algoritmus, amely úgy működik, hogy ismételten végigmegy a listán, és a szomszédos elempárokat összehasonlítja. Ha egy pár elem rossz sorrendben van, akkor a rendszer felcseréli őket, hogy a megfelelő sorrendbe kerüljenek. Ezt a bejárást addig ismételjük, amíg nincs szükség további cserékre. A beszúrásos rendezés is egy rendezési algoritmus, amely úgy működik, hogy a beviteli listában egy elemet beszúr a megfelelő helyre a már rendezett listában. Ezt a folyamatot ismételten alkalmazzák, amíg a listát rendezik.
Mi az a buborékos rendezés?
A buborékos rendezés egy rendezési algoritmus, amely úgy működik, hogy ismételten végigmegy a listán, és a szomszédos elempárokat összehasonlítja. Ha egy pár elem rossz sorrendben van, akkor a rendszer felcseréli őket, hogy a megfelelő sorrendbe kerüljenek. Ez a bejárás addig ismétlődik, amíg nincs szükség további swapokra (ami azt jelenti, hogy a lista rendezve van). Mivel a lista kisebb elemei úgy kerülnek a tetejére, ahogy egy buborék a felszínre kerül, ezért a buborék rendezés nevet kapja. A buborékos rendezés egy nagyon egyszerű rendezési algoritmus, de átlagos eset-időbeli összetettsége O(n2) n elemű lista rendezésekor. Emiatt a buborékos rendezés nem alkalmas nagy elemszámú listák rendezésére. De egyszerűsége miatt a buborékok rendezése az algoritmusok bevezetésekor tanítható.
Mi az a beillesztési rendezés?
A beillesztési rendezés egy másik rendezési algoritmus, amely úgy működik, hogy a beviteli listában egy elemet beszúr a lista megfelelő pozíciójába (amely már rendezve van). Ezt a folyamatot ismételten alkalmazzák, amíg a lista rendeződik. A beszúrásos rendezésnél a rendezés helyben történik. Ezért az algoritmus i-edik iterációja után a lista első i+1 bejegyzései rendeződnek, a lista többi része pedig törlődik. Minden iterációnál a lista rendezetlen részének első eleme kerül beillesztésre a lista rendezett részében a megfelelő helyre. A beillesztési rendezés átlagos eset-időbeli összetettsége O(n2). Emiatt a beszúrásos rendezés sem alkalmas nagy listák rendezésére.
Mi a különbség a buborékos rendezés és a beszúrásos rendezés között?
Annak ellenére, hogy mind a buborékrendezés, mind a beillesztési rendezés algoritmusának átlagos eset-időbeli összetettsége O(n2), a buborékok rendezése szinte mindig felülmúlja a beillesztési rendezést. Ez a két algoritmus által igényelt swapok számának köszönhető (a buborékok rendezéséhez több csere szükséges). De a buborékos rendezés egyszerűsége miatt a kód mérete nagyon kicsi. Létezik a beszúrási rendezésnek egy shell rendezésnek nevezett változata is, amelynek időbonyolítása O(n3/2), ami lehetővé tenné a gyakorlati felhasználást. Ezenkívül a beillesztési rendezés nagyon hatékony a „majdnem rendezett” listák rendezésére, összehasonlítva a buborékos rendezéssel.
