Burbulų rūšiavimas yra paprastas rūšiavimo algoritmas, kuris pakartotinai peržiūri sąrašą, lygina gretimus elementus ir sukeičia juos, jei jie yra neteisinga tvarka. Jis pavadintas „Bubble Sort“, nes mažesni elementai „burbuliuoja“ sąrašo viršuje. Nors tai nėra pats efektyviausias rūšiavimo algoritmas, jį lengva suprasti ir įgyvendinti, todėl tai yra geras atspirties taškas norint sužinoti apie rūšiavimo algoritmus. Šiame straipsnyje mes įsigilinsime į „Bubble Sort“ koncepciją, pateiksime „Python“ diegimą su išvestimi ir aptarsime algoritmo sudėtingumą laiku.
Burbulų rūšiavimo supratimas
Pagrindinė Bubble Sort idėja yra pakartoti sąrašą kelis kartus, lyginant gretimus elementus ir keičiant juos, jei jie neveikia. Procesas tęsiamas tol, kol nebereikia atlikti apsikeitimo sandorių, o tai rodo, kad sąrašas dabar surūšiuotas. Algoritmas gavo savo pavadinimą dėl to, kaip mažesni elementai palaipsniui pereina į sąrašo viršų, panašiai kaip burbuliukai, kylantys į paviršių.
Išskaidykime burbulų rūšiavimo algoritmo veiksmus:
k-nn algoritmas
- Pakartokite sąrašą: pradėkite nuo sąrašo pradžios ir palyginkite kiekvieną gretimų elementų porą.
- Palyginkite ir pakeiskite: jei elementai yra neteisinga tvarka, pakeiskite juos. Taip užtikrinama, kad didesnis elementas „burbuliuotų aukštyn“, o mažesnis judės žemyn.
- Tęsti kartojimą: kartokite procesą kiekvienai gretimų elementų porai, kol pasieksite sąrašo pabaigą.
- Kartokite, kol surūšiuosite: kartokite sąrašą, kol nebereikės apsikeitimo. Šiuo metu sąrašas surūšiuojamas.
Nors „Bubble Sort“ yra nesudėtinga suprasti, tai nėra pats efektyviausias rūšiavimo algoritmas, ypač dideliems duomenų rinkiniams. Jo sudėtingumas laike yra O(n^2) blogiausiu atveju, kur 'n' yra sąrašo elementų skaičius. Dėl šio kvadratinio laiko sudėtingumo jis yra mažiau tinkamas dideliems duomenų rinkiniams, palyginti su pažangesniais rūšiavimo algoritmais.
Python „Bubble Sort“ diegimas
Dabar įdiegkime „Bubble Sort“ „Python“ ir stebėkime jo elgesį naudodami pavyzdinį sąrašą:
def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list)
Šiame įgyvendinime funkcija bubble_sort pasirenka sąrašą (arr) kaip savo parametrą ir surūšiuoja jį vietoje. Įdėta kilpa lygina gretimus elementus ir sukeičia juos, jei jie yra neteisinga tvarka. Išorinis ciklas užtikrina, kad procesas kartotųsi tol, kol bus surūšiuotas visas sąrašas.
Išvestis ir paaiškinimas
Paleiskite pateiktą Python kodą su pavyzdžių sąrašu ir stebėkime išvestį:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
Čia pradinis sąrašas [64, 34, 25, 12, 22, 11, 90] sėkmingai surūšiuotas naudojant burbulų rūšiavimo algoritmą, todėl gaunamas surūšiuotas sąrašas [11, 12, 22, 25, 34, 64, 90].
seleno
Algoritmas kartoja sąrašą kelis kartus, lygindamas ir keisdamas elementus, kol visas sąrašas bus surūšiuotas. Kiekviename pravažiavime didžiausias nerūšiuotas elementas „iškyla“ į tinkamą vietą. Šis procesas tęsiasi tol, kol nebereikia apsikeitimo sandorių, o tai rodo, kad sąrašas yra visiškai surūšiuotas.
Nors „Bubble Sort“ sėkmingai rūšiuoja sąrašą, svarbu atkreipti dėmesį, kad dėl jos laiko sudėtingumo jis yra mažiau efektyvus dideliems duomenų rinkiniams, palyginti su kitais rūšiavimo algoritmais, pvz., „Sujungti rūšiavimą“ arba „Greitasis rūšiavimas“.
Burbulų rūšiavimo laiko sudėtingumas
pabraukti naudojant css
Norint įvertinti jo efektyvumą, ypač kai kalbama apie didelius duomenų rinkinius, labai svarbu suprasti algoritmo sudėtingumą laiku. „Bubble Sort“ laiko sudėtingumas blogiausiu atveju yra O(n^2), kur „n“ yra elementų skaičius sąraše.
Išskaidykime laiko sudėtingumo analizę:
- Išorinis ciklas vykdomas „n“ iteracijų metu, kur „n“ yra elementų skaičius sąraše.
- Blogiausiu atveju vidinė kilpa taip pat atlieka „n“ iteracijas. Tačiau tobulėjant algoritmui, pakartojimų skaičius vidinėje kilpoje mažėja, nes didžiausias nerūšiuotas elementas kiekviename žingsnyje patenka į teisingą vietą.
- Blogiausiu atveju palyginimų ir apsikeitimų skaičius yra proporcingas sąrašo elementų skaičiaus kvadratui, todėl O(n^2) laiko sudėtingumas. Dėl to burbulų rūšiavimas neveiksmingas dideliems duomenų rinkiniams, o realaus pasaulio programose dažnai pirmenybė teikiama pažangesniems rūšiavimo algoritmams, kurių laikas yra sudėtingesnis.
Išvada
Šiame straipsnyje mes išnagrinėjome burbulų rūšiavimo koncepciją – paprastą rūšiavimo algoritmą, kuris pakartotinai lygina ir keičia gretimus elementus, kol bus surūšiuotas visas sąrašas. Pateikėme Python „Bubble Sort“ diegimą, paleidome jį su pavyzdiniu sąrašu ir išanalizavome išvestį. Be to, aptarėme „Bubble Sort“ laiko sudėtingumą, pabrėždami jo O(n^2) blogiausio atvejo laiko sudėtingumą ir jo poveikį efektyvumui.