Különbség a Bubble Sort és a Selection Sort között
Tartalom
A rendezés a számítógépes programok egyik legfontosabb feladata, amelyben a tömb elemei bizonyos sorrendben vannak elrendezve. A rendezés megkönnyíti a keresést. A Bubble sort és a Selection sort a rendezési algoritmusok, amelyek megkülönböztethetők a rendezéshez használt módszerekkel. A Bubble sort lényegében kicseréli az elemeket, míg a selection sort az elem kiválasztásával hajtja végre a rendezést.
Egy másik jelentős különbség a kettő között az, hogy a buborékfajta stabil algoritmus, míg a szelekciós rendezés egy instabil algoritmus. Az algoritmus úgy tekinthető, hogy állandó elemek ugyanazzal a kulccsal, ugyanabban a sorrendben fordulnak elő, mint amelyek a listában vagy a tömbbe történő rendezés előtt fordultak elő. A legtöbb stabil és gyors algoritmus általában további memóriát igényel.
- Összehasonlító táblázat
- Meghatározás
- Főbb különbségek
- Következtetés
Összehasonlító táblázat
| Az összehasonlítás alapja | Bubble sort | Kiválasztás rendezése |
|---|---|---|
| Alapvető | A szomszédos elemet összehasonlítjuk és felcseréljük | A legnagyobb elem kerül kiválasztásra és felcserélésre az utolsó elemmel (növekvő sorrend esetén). |
| A legjobb eset összetettsége | Tovább) | Tovább2) |
| Hatékonyság | Nem hatékony | Javított hatékonyság a buborékfajtahoz képest |
| Stabil | Igen | Nem |
| Eljárás | csere | Kiválasztás |
| Sebesség | Lassú | Gyors, mint a buborékfajta |
A Bubble Sort meghatározása
Bubble sort A legegyszerűbb iteratív algoritmus működik, ha összehasonlít minden elemet vagy elemet a mellette lévő elemmel, és szükség esetén cseréli őket. Egyszerű szavakkal összehasonlítja a lista első és második elemét, és felcseréli azokat, kivéve, ha azok rendben vannak. Hasonlóképpen összehasonlítják és felcserélik a második és a harmadik elemet, és ez az összehasonlítás és a csere a lista végére megy. Az összehasonlítások száma az első iterációban n-1, ahol n a tömb szám elemei. A legnagyobb elem az első iteráció után n-edik helyzetben lenne. És minden iteráció után az összehasonlítások száma csökken, és végre iterációra csak egy összehasonlítás kerül sor.
Ez az algoritmus a leglassabb rendezési algoritmus. A Buborék rendezése a legjobb eset összetettségének (ha a lista rendben van) n sorrendben van (Tovább)), és a legrosszabb eset bonyolultsága Tovább2). A legjobb esetben az n sorrendű, mert csak összehasonlítja az elemeket, és nem cseréli őket. Ez a technika további helyet igényel az ideiglenes változó tárolására.
A kiválasztási sorrend meghatározása
Kiválasztás rendezése valamivel jobb teljesítményt ért el, és hatékony, mint a buborékrendezési algoritmus. Tegyük fel, hogy növekvő sorrendben akarunk elrendezni egy tömböt, akkor úgy működik, hogy megtaláljuk a legnagyobb elemet, és kicseréljük azt az utolsó elemre, és ismételjük meg a következő eljárást az altömbökön, amíg a teljes lista rendezésre nem kerül.
- A buborékrendezés során az egyes elemeket és a szomszédos elemeket összehasonlítják és szükség esetén cserélik. Másrészt a szelekciós rendezés az elem kiválasztásával és az adott elemnek az utolsó elemre való cseréjével működik. A kiválasztott elem lehet a legnagyobb vagy a legkisebb, a sorrendtől függően, azaz növekvő vagy csökkenő.
- A legrosszabb eset komplexitása mindkét algoritmusban azonos, azaz O (n2), de a legjobb összetettség eltérő. A buborék rendezése n időrendű, míg a szortírozás n sorrendű2 idő.
- A Bubble Sort egy stabil algoritmus, ezzel szemben a szelekciós rendezés instabil.
- A szelekciós rendezési algoritmus gyors és hatékony, mint a buborék rendezés, amely nagyon lassú és nem hatékony.
Következtetés
A buborék rendezési algoritmust tekintik a legegyszerűbb és leghatékonyabb algoritmusnak, de a szelekciós rendezési algoritmus hatékony a buborék rendezéséhez képest. A buborékrendezés további helyet igényel az ideiglenes változó tárolására, és további csereprogramokra van szüksége.
