Buborékos rendezés vs kijelölés 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 kijelölés rendezés is egy rendezési algoritmus, amely úgy indul, hogy megkeresi a listában a minimális elemet, és felcseréli az első elemre. Ez a folyamat a lista hátralévő részében megismétlődik a felcserélt elemek sorrendbe helyezésével.
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 kijelölés rendezése?
A kijelölés rendezése egy másik rendezési algoritmus is, amely úgy indul, hogy megkeresi a minimális elemet a listában, és felcseréli az első elemre. Ezután a minimális elemet megtalálja a lista maradékából (a második elemtől a lista utolsó eleméig), és felcseréli a második elemmel. Ez a folyamat megismétlődik a lista hátralévő részében a felcserélt elemek sorrendbe állításával. Tehát a kijelölési rendezésnél az algoritmus bármely lépésében a lista két részre oszlik, ahol az egyik rész rendezett, a másik pedig nem rendezett elemeket tartalmaz. Az algoritmus előrehaladtával a rendezett lista balról jobbra nő. A kiválasztási rendezés átlagos eset-időbeli összetettsége is O(n2). Ezért nagy listák rendezésére sem alkalmas.
Mi a különbség a buborékos rendezés és a kiválasztási rendezés között?
Annak ellenére, hogy mind a buborékok rendezése, mind a kijelölési rendezés algoritmusainak átlagos eset-időbeli összetettsége O(n2), a buborékrendezés szinte mindig felülmúlja a kiválasztá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. A stabilitás egy másik különbség e két algoritmus között. A stabil rendezési algoritmus olyan rendezési algoritmus, amely megtartja a rekordok sorrendjét, ha a lista azonos értékű elemeket tartalmaz. Ebben az értelemben a kiválasztási rendezés nem stabil algoritmus, míg a buborékos rendezés egy stabil algoritmus.
