Skirtumas tarp rūšiavimo burbule ir įterpimo

Burbulas Rūšiuoti vs Įterpti Rūšiuoti

„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ų. Įterpimo rūšiavimas taip pat yra rūšiavimo algoritmas, kuris veikia įterpiant elementą įvesties sąraše į reikiamą vietą jau surūšiuotame sąraše. Šis procesas atliekamas pakartotinai, kol sąrašas bus rūšiuojamas.

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 įterpimo rūšiavimas?

Įterpimo rūšiavimas yra kitas rūšiavimo algoritmas, kuris veikia įterpiant elementą įvesties sąraše į reikiamą sąrašo vietą (kuri jau yra rūšiuojama). Šis procesas atliekamas pakartotinai, kol sąrašas bus rūšiuojamas. Įterpimo metu rūšiavimas atliekamas vietoje. Taigi po i-osios algoritmo kartojimo pirmieji i + 1 sąrašo įrašai bus rūšiuojami, o likęs sąrašas bus nerūšiuotas. Kiekvienos kartojimo metu pirmasis nerūšiuotosios sąrašo dalies elementas bus paimtas ir įterptas į reikiamą vietą rūšiuotoje sąrašo dalyje. Įterpimo rūšiavimo vidutinis atvejo laiko sudėtingumas yra O (n2). Dėl to įterpimo rūšiavimas taip pat netinka rūšiuoti didelius sąrašus.

Kuo skiriasi rūšiavimas „Burbulas“ ir „Įterpimas“?

Nors tiek burbulų rūšiavimo, tiek intarpų rūšiavimo algoritmai turi vidutinį atvejo laiko sudėtingumą O (n2), burbulų rūšiavimas beveik visą laiką pralenkia intarpų 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. Taip pat yra įterpimo rūšies, vadinamos apvalkalu, variantas, kurio laiko sudėtingumas yra O (n3 / 2), kuris leistų jį praktiškai naudoti. Be to, įterpimo rūšiavimas yra labai efektyvus, norint rūšiuoti „beveik surūšiuotus“ sąrašus, palyginti su burbulų rūšiavimu.