Skirtumas tarp rūšiavimo burbule ir atrankos

Burbulo rūšiavimas vs pasirinkimo rūšiavimas

„Burbulo rūšiavimas“ yra rūšiavimo algoritmas, veikiantis pakartotinai rūšiuojamo sąrašo metu, lyginant greta esančių elementų poras. Jei elementų pora yra netinkama tvarka, jie keičiami, kad išdėstytumėte teisinga tvarka. Šis važiavimas kartojamas tol, kol nebereikia jokių mainų. Atrankos rūšiavimas taip pat yra rūšiavimo algoritmas, kuris pradedamas surandant minimalų elementą sąraše ir sukeičiant jį su pirmuoju elementu. Šis procesas pakartojamas likusiai sąrašo daliai, sudedant sukeistus elementus.

Kas yra „Bubble Sort“?

„Burbulo rūšiavimas“ yra rūšiavimo algoritmas, veikiantis pakartotinai rūšiuojamo sąrašo metu, lyginant greta esančių elementų poras. Jei elementų pora yra netinkama tvarka, jie keičiami, kad išdėstytumėte teisinga tvarka. Šis perėjimas kartojamas tol, kol nebereikia jokių mainų (tai reiškia, kad sąrašas rūšiuojamas). Kadangi mažesni sąrašo elementai kyla į viršų, kai burbulas iškyla į paviršių, jam suteikiamas burbulų rūšies pavadinimas. Burbulų rūšiavimas yra labai paprastas rūšiavimo algoritmas, tačiau rūšiavimo sąrašo su n elementais atveju vidutinis atvejo laiko sudėtingumas yra O (n2). Dėl šios priežasties burbulų rūšiavimas netinka rūšiuoti sąrašus, kuriuose yra daug elementų. Bet dėl ​​savo paprastumo, burbulų rūšiavimas yra mokomas supažindinant su algoritmais.

Kas yra atrankos rūšiavimas??

Pasirinkimo rūšiavimas taip pat yra kitas rūšiavimo algoritmas, kuris pradedamas ieškant minimalaus sąrašo elemento ir keičiant jį pirmuoju elementu. Tada minimalus elementas randamas iš likusios sąrašo dalies (nuo antrojo elemento iki paskutinio sąrašo elemento) ir keičiamas su antruoju elementu. Šis procesas pakartojamas likusiai sąrašo daliai, sudedant sukeistus elementus. Taigi atrankos rūšiavimo metu bet kuriame algoritmo etape sąrašas yra padalintas į dvi dalis, kuriose vienoje dalyje yra surūšiuoti elementai, o kitoje - nerūšiuoti elementai. Kai algoritmas vykdomas, rūšiuotas sąrašas auga iš kairės į dešinę. Atrankos rūšis taip pat turi vidutinį atvejo laiko sudėtingumą O (n2). Todėl jis taip pat netinka rūšiuoti didelius sąrašus.

Kuo skiriasi „Bubble Sort“ ir „Selection Sort“?

Nors ir burbulų rūšiavimo, ir atrankos rūšiavimo algoritmai turi vidutinį atvejo laiko sudėtingumą O (n2), burbulų rūšiavimas beveik visą laiką pralenkia pasirinkimo rūšiavimą. Taip yra dėl to, kiek apsikeitimų reikia dviem algoritmams („burbulų rūšiavimui“ reikia daugiau apsikeitimo sandorių). Tačiau dėl burbulų rūšiavimo paprastumo jo kodo dydis yra labai mažas. Stabilumas yra dar vienas šių dviejų algoritmų skirtumas. Stabilus rūšiavimo algoritmas yra rūšiavimo algoritmas, kuris išlaiko įrašų tvarką, jei sąraše yra elementų, kurių vertė lygi. Ta prasme atrankos rūšiavimas nėra stabilus algoritmas, tuo tarpu burbulų rūšiavimas yra stabilus algoritmas.