Rekomenduojama, 2020

Redaktoriaus Pasirinkimas

Skirtumas tarp burbulo rūšiavimo ir parinkimo Rūšiuoti

Rūšiavimas yra viena svarbiausių užduočių kompiuterių programose, kuriose masyvo elementai yra išdėstyti tam tikroje eilėje. Rūšiavimas palengvina paiešką. „Bubble Sort“ ir „Selection sort“ yra rūšiavimo algoritmai, kurie gali būti diferencijuojami pagal metodus, kuriuos jie naudoja rūšiavimui. „Bubble sort“ iš esmės keičia elementus, o atrankos rūšiavimas atlieka rūšiavimą, pasirinkdamas elementą.

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 pagrindasBubble rūšiuoti
Pasirinkimas rūšiuoti
PagrindinisPalyginamas ir keičiamas gretimas elementasDidžiausias elementas yra pasirinktas ir pakeistas su paskutiniu elementu (didėjančia tvarka).
Geriausias atvejo laiko sudėtingumasO (n)O (n 2 )
EfektyvumasNeefektyvusGeresnis efektyvumas, lyginant su burbuliukų rūšimi
StabiliTaipNe
MetodasKeitimasisPasirinkimas
GreitisLėtasGreitas, 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.

Pasirinkimo tvarka rūšiuojama ir nerūšiuota masyvas neturi jokio skirtumo ir sunaudoja n2 ( O (n2) ) eilę tiek geriausiu, tiek blogiausiu atveju. Pasirinkimas yra greitesnis nei „Bubble sort“.

Pagrindiniai skirtumai tarp burbulo rūšiavimo ir pasirinkimo Rūšiuoti

  1. 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.
  2. 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.
  3. „Bubble sort“ yra stabilus algoritmas, priešingai, atrankos rūšys yra nestabilios.
  4. 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ų.

Top