Burbulinis rūšiavimas prieš įterpimo 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. Įterpimo rūšiavimas taip pat yra rūšiavimo algoritmas, kuris veikia įterpiant elementą įvesties sąraše į reikiamą vietą sąraše, kuris jau yra surūšiuotas. Šis procesas taikomas pakartotinai, kol sąrašas bus surūšiuotas.
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 įterpimo rūšiavimas?
Įterpimo rūšiavimas yra kitas rūšiavimo algoritmas, kuris veikia įterpiant elementą įvesties sąraše į teisingą sąrašo vietą (kuri jau surūšiuota). Šis procesas kartojamas tol, kol sąrašas surūšiuojamas. Rūšiuojant įterpiant, rūšiavimas atliekamas vietoje. Todėl po i-osios algoritmo iteracijos pirmieji i+1 įrašai sąraše bus surūšiuoti, o likusi sąrašo dalis bus išrūšiuota. Kiekvienos iteracijos metu pirmasis elementas nerūšiuotoje sąrašo dalyje bus paimtas ir įterpiamas į reikiamą vietą surūšiuotoje sąrašo dalyje. Įterpimo rūšiavimo vidutinis atvejo sudėtingumas yra O(n2). Dėl šios priežasties įterpimo rūšiavimas taip pat netinka dideliems sąrašams rūšiuoti.
Kuo skiriasi burbulų rūšiavimas ir įterpimo rūšiavimas?
Nors ir burbulų rūšiavimo, ir įterpimo rūšiavimo algoritmų vidutinis atvejo sudėtingumas yra O(n2), burbulų rūšiavimas beveik visą laiką lenkia įterpimo 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. Taip pat yra įterpimo rūšiavimo variantas, vadinamas apvalkalo rūšiavimu, kurio laiko sudėtingumas yra O(n3/2), kuris leistų jį praktiškai panaudoti. Be to, įterpimo rūšiavimas yra labai efektyvus rūšiuojant „beveik surūšiuotus“sąrašus, palyginti su burbulų rūšiavimu.
