Turinys

• Palyginimo diagrama
• Burbulo rūšiavimo apibrėžimas
• Atrankos rūšiavimo apibrėžimas
• Išvada

Rūšiavimas yra viena iš svarbiausių užduočių kompiuterinėse programose, kurioje masyvo elementai išdėstomi tam tikra tvarka. Rūšiavimas palengvina paiešką. „Burbulo rūšiavimas“ ir „Rūšiuoti pagal atranką“ yra rūšiavimo algoritmai, kuriuos galima diferencijuoti naudojant metodus, kuriuos jie naudoja rūšiuodami. Burbulas rūšiuoja iš esmės elementus, o atrankos rūšiavimas atliekamas rūšiuojant elementą.

Kitas reikšmingas skirtumas tarp šių dviejų yra tas, kad „burbulas“ yra stabilus algoritmas, o pasirinkimo rūšiavimas yra nestabilus algoritmas. Laikoma, kad algoritmas yra pastovus elementai su tuo pačiu raktu, vykstantys ta pačia tvarka, kaip jie buvo prieš rūšiuojant sąraše ar masyve. Paprastai stabiliausi ir greičiausi algoritmai naudoja papildomą atmintį.

1. Palyginimo diagrama
2. Apibrėžimas
3. Pagrindiniai skirtumai
4. Išvada

Palyginimo diagrama

Palyginimo pagrindas	Burbulas rūšiuoti	Atrankos rūšiavimas
Pagrindinis	Gretimas elementas lyginamas ir keičiamas	Didžiausias elementas parenkamas ir keičiamas paskutiniu elementu (didėjančios eilės atveju).
Geriausio atvejo laiko sudėtingumas	O (n)	O (n2)
Efektyvumas	Neefektyvus	Patobulintas efektyvumas, palyginti su rūšiavimu
Stabilus	Taip	Ne
Metodas	Keitimasis	Pasirinkimas
Greitis	Lėtai	Greitas, palyginti su burbulų rūšiavimu

Burbulo rūšiavimo apibrėžimas

Burbulas rūšiuoti yra paprasčiausias iteracinis algoritmas, veikiantis lyginant kiekvieną elementą ar elementą su šalia esančiu elementu ir, jei reikia, keičiant juos. Paprastais žodžiais tariant, jis lygina pirmąjį ir antrąjį sąrašo elementus ir keičiasi juo, nebent jie yra ne pagal tam tikrą tvarką. Panašiai yra lyginamas ir keičiamas antrasis ir trečiasis elementai, o šis palyginimas ir keitimasis eina į sąrašo pabaigą. Palyginimų skaičius pirmoje iteracijoje yra n-1, kur n yra skaičių elementai masyve. Didžiausias elementas būtų pirmoje iteracijoje n-oje vietoje. Po kiekvienos iteracijos palyginimų skaičius mažėja ir pagaliau iteracija vyksta tik po vieną.

Šis algoritmas yra lėčiausias rūšiavimo algoritmas. Geriausias burbulo rūšiavimo atvejis (kai sąrašas tvarkingas) yra n eilės (O (n)), o blogiausias atvejis yra sudėtingas O (n²). Geriausiu atveju jis yra eilės n punktas, nes jis tik lygina elementus ir jų nekeičia. Ši technika taip pat reikalauja papildomos vietos laikinajam kintamajam laikyti.

Atrankos rūšiavimo apibrėžimas

Atrankos rūšiavimas pasiekė šiek tiek geresnį našumą ir yra efektyvesnis nei „burbulų rūšiavimo“ algoritmas. Tarkime, kad mes norime išdėstyti masyvą didėjančia tvarka, tada jis funkcionuoja surasdamas didžiausią elementą ir keisdamas jį paskutiniu elementu, ir pakartokite šį procesą antriniuose masyvuose, kol visas sąrašas bus rūšiuojamas.

Pasirinkus rūšiavimą, išrūšiuotas ir nerūšiuotas masyvas neturi jokio skirtumo ir sunaudoja eilę n² (O (n²)) tiek geriausiu, tiek blogiausiu atveju. Pasirinkimas rūšiuojamas greičiau nei burbulas.

1. Rūšiuojant burbulą, kiekvienas elementas ir greta jo esantis elementas yra palyginami ir keičiami, jei reikia. Kita vertus, atrankos rūšiavimas veikia pasirinkus elementą ir keičiant tą elementą paskutiniu elementu. Pasirinktas elementas gali būti didžiausias arba mažiausias priklausomai nuo tvarkos, t. Y., Kylančia ar mažėjančia.
2. Blogiausias atvejo sudėtingumas yra tas pats abiejuose algoritmuose, t. Y. O (n²), tačiau geriausias sudėtingumas skiriasi. Burbulas rūšiuojamas maždaug n laiko tvarka, o atrankos rūšiavimui sunaudojama n tvarka² laikas.
3. Burbulų rūšiavimas yra stabilus algoritmas, priešingai, pasirinkimo rūšiavimas yra nestabilus.
4. Atrankos rūšiavimo algoritmas yra greitas ir efektyvus, palyginti su burbulų rūšiavimu, kuris yra labai lėtas ir neefektyvus.

Išvada

Burbulo rūšiavimo algoritmas laikomas paprasčiausiu ir neefektyviausiu algoritmu, tačiau rūšiavimo algoritmas yra efektyvus, palyginti su rūšiavimu burbule. „Burbulas“ taip pat sunaudoja papildomos vietos laikinajam kintamajam laikyti ir reikia daugiau apsikeitimo sandorių.