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ófajta egy instabil algoritmus. Egy algoritmust úgy kell tekinteni, hogy az azonos kulcsú elemeket ugyanolyan sorrendben, mint a listában vagy tömbben rendezés előtt rendezték meg. Általában a legtöbb stabil és gyors algoritmus további memóriát használ.
Összehasonlító táblázat
| Az összehasonlítás alapja | Buborékfajta | Kiválasztás rendezése |
|---|---|---|
| Alapvető | A szomszédos elemet összehasonlítják és cserélik | A legmagasabb elem kiválasztása és cseréje az utolsó elemgel (növekvő sorrend esetén). |
| A legjobb eseti idő összetettsége | Tovább) | O (n 2 ) |
| Hatékonyság | Nem hatékony | A buborékfajtához képest jobb hatékonyság |
| Stabil | Igen | Nem |
| Eljárás | csere | Kiválasztás |
| Sebesség | Lassú | Gyors, mint a buborékfajta |
A Bubble Sort meghatározása
A Bubble sort a legegyszerűbb iteratív algoritmus, amely az egyes elemeket vagy elemeket a mellette lévő elemhez hasonlítja, és szükség esetén cseréje. Egyszerű szavakkal összehasonlítva a lista első és második elemeit, és kicseréli azt, kivéve, ha azok nincsenek meghatározott sorrendben. Hasonlóképpen, a második és a harmadik elemet összehasonlítják és cserélik, és ez az összehasonlítás és csere folytatódik a lista végéig. Az összehasonlítások száma az első iterációban n-1, ahol n a tömb számelemei. A legnagyobb elem az első iteráció után n. Minden egyes iteráció után az összehasonlítások száma csökken, és az utolsó iterációnál csak egy összehasonlítás történik.
Ez az algoritmus a leglassabb válogatási algoritmus. A legjobb bonyolultság (amikor a lista rendben van) a Bubble sorrendben n ( O (n) ) sorrendű, és a legrosszabb esetben az O (n2) . A legjobb esetben n, 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ához.
A kiválasztás meghatározása Rendezés
A válogatásfajta valamivel jobb teljesítményt ért el, és hatékonyabb, mint a buborékfajta algoritmus. Tegyük fel, hogy növekvő sorrendben szeretnénk elrendezni egy tömböt, majd úgy működik, hogy megtaláljuk a legnagyobb elemet, és kicseréljük azt az utolsó elemgel, és ismételjük meg az alábbi folyamatot az alrendszereken, amíg a teljes listát rendezzük.
Kulcsfontosságú különbségek a Bubble Sort és a Selection között
- A buborékfajtában minden elemet és annak szomszédos elemét összehasonlítjuk, és szükség esetén cseréljük. Másrészről a kiválasztási rendezés az elem kiválasztásával és az adott elem utolsó elemgel való cseréjével működik. A kiválasztott elem a sorrendtől függően lehet legnagyobb vagy legkisebb, azaz emelkedő vagy csökkenő.
- A legrosszabb komplexitás mindkét algoritmusban azonos, azaz O (n2), de a legjobb komplexitás más. A Bubble sort egy n-es sorrendet veszi figyelembe, míg a kiválasztási rendezés n2-es sorrendet fogyaszt.
- A buborékfajta egy stabil algoritmus, ezzel szemben a szelekciófajta instabil.
- A kiválasztási rendezési algoritmus gyors és hatékony, mint a nagyon lassú és nem hatékony buborékfajta.
Következtetés
A buborékfajta algoritmus a legegyszerűbb és nem hatékony algoritmus, de a szelekciós rendezési algoritmus hatékony a buborékfajtához képest. A buborékfajta is több helyet foglal el az ideiglenes változók tárolásához, és több cserét igényel.
