Kitas didelis skirtumas tarp šių dviejų yra tas, kad burbuliukų rūšiavimas yra stabilus algoritmas, o atrankos rūšys yra nestabilus algoritmas. Laikoma, kad algoritmas yra pastovus elementams, turintiems tą patį raktą, tokiu pačiu būdu, kaip jie įvyko prieš rūšiavimą sąraše ar masyve. Paprastai stabiliausi ir greiti algoritmai naudoja papildomą atmintį.
Palyginimo diagrama
| Palyginimo pagrindas | Bubble rūšiuoti | Pasirinkimas rūšiuoti |
|---|---|---|
| Pagrindinis | Palyginamas ir keičiamas gretimas elementas | Didžiausias elementas yra pasirinktas ir pakeistas su paskutiniu elementu (didėjančia tvarka). |
| Geriausias atvejo laiko sudėtingumas | O (n) | O (n 2 ) |
| Efektyvumas | Neefektyvus | Geresnis efektyvumas, lyginant su burbuliukų rūšimi |
| Stabili | Taip | Ne |
| Metodas | Keitimasis | Pasirinkimas |
| Greitis | Lėtas | Greitas, palyginti su burbuliukų rūšiavimu |
„Bubble Sort“ apibrėžimas
„Bubble sort“ yra paprasčiausias iteracinis algoritmas, lyginant kiekvieną elementą ar elementą prie jo esančio elemento ir prireikus juos pakeičiant. Paprastais žodžiais tariant, jis lygina pirmąjį ir antrąjį sąrašo elementus ir apsikeičia jais, išskyrus atvejus, kai jie nėra tam tikros eilės. Panašiai ir antrasis bei trečiasis elementai yra lyginami ir keičiami, o šis palyginimas ir keitimas vyksta sąrašo pabaigoje. Palyginimų skaičius pirmoje iteracijoje yra n-1, kur n yra masyvo elementų skaičius. Didžiausias elementas po pirmojo iteracijos būtų n. Ir po kiekvieno iteracijos palyginimų skaičius sumažėja, o paskutinis iteracijos metu atliekamas tik vienas palyginimas.
Šis algoritmas yra lėčiausias rūšiavimo algoritmas. Bubble rūšiuoti geriausias atvejo sudėtingumas (kai sąrašas yra tvarkingas) yra eilės n ( O (n) ), o blogiausio atvejo sudėtingumas yra O (n2) . Geriausiu atveju tai yra tvarka n, nes ji tik lygina elementus ir nesikeičia. Šis metodas taip pat reikalauja papildomos vietos laikinam kintamojo saugojimui.
Atrankos apibrėžimas Rūšiuoti
Atrankos rūšys pasiekė šiek tiek geresnį našumą ir yra efektyvesnės už burbulų rūšiavimo algoritmą. Tarkime, mes norime surengti masyvą didėjančia tvarka, tada jis veikia, ieškodamas didžiausio elemento ir keisdamas jį su paskutiniu elementu, ir pakartokite šį procesą ant sub-masyvų, kol visas sąrašas bus surūšiuotas.
Pagrindiniai skirtumai tarp burbulo rūšiavimo ir pasirinkimo Rūšiuoti
- Burbulų rūšiavimo metu kiekvienas elementas ir jo gretimas elementas yra palyginami ir keičiami, jei reikia. Kita vertus, atrankos rūšiavimas veikia pasirinkus elementą ir pakeičiant tą elementą su paskutiniu elementu. Pasirinktas elementas gali būti didžiausias arba mažiausias, priklausomai nuo užsakymo, ty didėjimo arba mažėjimo.
- Blogiausio atvejo sudėtingumas yra vienodas abiejuose algoritmuose, ty O (n2), tačiau geriausias sudėtingumas yra skirtingas. Burbulų rūšiavimas trunka n laiko eilės tvarka, o atrankos rūšiuoti sunaudojama n2 laiko tvarka.
- „Bubble sort“ yra stabilus algoritmas, priešingai, atrankos rūšys yra nestabilios.
- Atrankos rūšiavimo algoritmas yra greitas ir efektyvus, palyginti su burbuliukų rūšimi, kuri yra labai lėta ir neveiksminga.
Išvada
Burbulų rūšiavimo algoritmas laikomas paprastiausiu ir neefektyviausiu algoritmu, bet atrankos rūšiavimo algoritmas yra efektyvus, palyginti su burbuliukų rūšiavimu. „Bubble sort“ taip pat sunaudoja papildomos vietos laikinojo kintamojo saugojimui ir reikalauja daugiau apsikeitimo sandorių.
