Burbulinis rūšiavimas prieš pasirinkimo rūšiavimą
Burbulinis rūšiavimas yra rūšiavimo algoritmas, kuris veikia pakartotinai peržiūrint sąrašą ir lyginant gretimų elementų poras. Jei elementų pora yra neteisinga tvarka, jie sukeičiami, kad būtų išdėstyta teisinga tvarka. Šis judėjimas kartojamas tol, kol nebereikia atlikti apsikeitimo. Pasirinkimo rūšiavimas taip pat yra rūšiavimo algoritmas, kuris pradedamas suradus minimalų elementą sąraše ir pakeičiant jį pirmuoju. Šis procesas pakartojamas likusiai sąrašo daliai, sudėjus sukeistus elementus eilės tvarka.
Kas yra burbulų rūšiavimas?
Burbulinis rūšiavimas yra rūšiavimo algoritmas, kuris veikia pakartotinai peržiūrint sąrašą ir lyginant gretimų elementų poras. Jei elementų pora yra neteisinga tvarka, jie sukeičiami, kad būtų išdėstyta teisinga tvarka. Šis judėjimas kartojamas tol, kol nebereikia atlikti apsikeitimo sandorių (tai reiškia, kad sąrašas surūšiuojamas). Kadangi mažesni sąrašo elementai patenka į viršų, kai burbulas iškyla į paviršių, jam suteikiamas pavadinimas burbulo rūšiavimas. Burbulų rūšiavimas yra labai paprastas rūšiavimo algoritmas, tačiau rūšiuojant sąrašą su n elementų vidutinis atvejo sudėtingumas yra O(n2). Dėl šios priežasties burbulinis rūšiavimas netinka rūšiuoti sąrašus, kuriuose yra daug elementų. Tačiau dėl savo paprastumo burbulų rūšiavimas mokomas supažindinant su algoritmais.
Kas yra atrankos rūšiavimas?
Pasirinkimo rūšiavimas taip pat yra kitas rūšiavimo algoritmas, kuris pradedamas suradus minimalų elementą sąraše ir pakeičiant jį pirmuoju. Tada minimalus elementas randamas iš likusios sąrašo dalies (nuo antrojo elemento iki paskutinio elemento sąraše) ir pakeičiamas antruoju elementu. Šis procesas kartojamas likusiai sąrašo daliai, sudėjus sukeistus elementus eilės tvarka. Taigi atrankos rūšiavimo metu bet kuriame algoritmo žingsnyje sąrašas padalijamas į dvi dalis, kur vienoje dalyje yra surūšiuoti elementai, o kitoje – nerūšiuoti elementai. Vykstant algoritmui, surūšiuotas sąrašas didėja iš kairės į dešinę. Atrankos rūšiavimas taip pat turi vidutinį atvejo sudėtingumą O(n2). Todėl jis taip pat netinka rūšiuoti didelius sąrašus.
Kuo skiriasi burbulų rūšiavimas ir pasirinkimo rūšiavimas?
Nors ir burbulų rūšiavimo, ir atrankos rūšiavimo algoritmų vidutinis atvejo sudėtingumas yra O(n2), burbulų rūšiavimas beveik visada lenkia pasirinkimo rūšiavimą. Taip yra dėl apsikeitimo sandorių skaičiaus, kurio reikia dviem algoritmams (rūšiuojant burbulus reikia daugiau apsikeitimų). 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 – tai rūšiavimo algoritmas, kuris išsaugo įrašų tvarką, jei sąraše yra elementų su vienoda verte. Šia prasme pasirinkimo rūšiavimas nėra stabilus algoritmas, o burbulų rūšiavimas yra stabilus.
