Bubble Sort je preprost algoritem za razvrščanje, ki večkrat koraka skozi seznam, primerja sosednje elemente in jih zamenja, če so v napačnem vrstnem redu. Imenuje se »Bubble Sort«, ker se manjši elementi »mehurčijo« na vrh seznama. Čeprav ni najbolj učinkovit algoritem za razvrščanje, ga je enostavno razumeti in implementirati, zaradi česar je dobro izhodišče za učenje o algoritmih za razvrščanje. V tem članku se bomo poglobili v koncept Bubble Sort, zagotovili izvedbo Python z izhodom in razpravljali o časovni kompleksnosti algoritma.
Razumevanje Bubble Sort
Osnovna ideja Bubble Sort je večkratno ponavljanje seznama, primerjanje sosednjih elementov in njihova zamenjava, če niso v redu. Postopek se nadaljuje, dokler zamenjave niso več potrebne, kar pomeni, da je seznam zdaj razvrščen. Algoritem je dobil ime po tem, kako se manjši elementi postopoma premikajo na vrh seznama, podobno kot mehurčki, ki se dvigajo na površje.
Razčlenimo korake algoritma Bubble Sort:
- Ponovite seznam: Začnite od začetka seznama in primerjajte vsak par sosednjih elementov.
- Primerjaj in zamenjaj: če so elementi v napačnem vrstnem redu, jih zamenjaj. To zagotavlja, da se večji element 'napihne', manjši pa se premakne navzdol.
- Nadaljujte s ponavljanjem: postopek ponavljajte za vsak par sosednjih elementov, dokler ne dosežete konca seznama.
- Ponavljajte, dokler ni razvrščeno: Nadaljujte s ponavljanjem po seznamu, dokler zamenjave niso potrebne več. Na tej točki je seznam razvrščen.
Čeprav je Bubble Sort enostavno razumeti, ni najučinkovitejši algoritem za razvrščanje, zlasti za velike nabore podatkov. Njegova časovna kompleksnost je v najslabšem primeru O(n^2), kjer je 'n' število elementov na seznamu. Zaradi te kvadratne časovne kompleksnosti je manj primeren za velike nabore podatkov v primerjavi z naprednejšimi algoritmi za razvrščanje.
Izvedba Bubble Sort v Pythonu
Zdaj pa implementirajmo Bubble Sort v Python in opazujmo njegovo vedenje z vzorčnim seznamom:
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)
V tej izvedbi funkcija bubble_sort vzame seznam (arr) kot svoj parameter in ga razvrsti na mestu. Ugnezdena zanka primerja sosednje elemente in jih zamenja, če so v napačnem vrstnem redu. Zunanja zanka zagotavlja, da se postopek ponavlja, dokler ni razvrščen celoten seznam.
Izhod in razlaga
Zaženimo priloženo kodo Python s seznamom vzorcev in opazujmo rezultat:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
Tukaj je izvirni seznam [64, 34, 25, 12, 22, 11, 90] uspešno razvrščen z algoritmom Bubble Sort, rezultat pa je razvrščeni seznam [11, 12, 22, 25, 34, 64, 90].
Algoritem večkrat preleti seznam, primerja in zamenjuje elemente, dokler ni razvrščen celoten seznam. V vsakem prehodu se največji nerazvrščeni element 'povzpne' na pravilen položaj. Ta postopek se nadaljuje, dokler zamenjave niso več potrebne, kar pomeni, da je seznam v celoti razvrščen.
Medtem ko Bubble Sort uspešno razvrsti seznam, je pomembno omeniti, da je zaradi časovne zapletenosti manj učinkovit za velike nabore podatkov v primerjavi z drugimi algoritmi za razvrščanje, kot sta Razvrščanje z združitvijo ali Hitro razvrščanje.
Časovna zapletenost Bubble Sort
Razumevanje časovne kompleksnosti algoritma je ključnega pomena za ovrednotenje njegove učinkovitosti, zlasti ko imamo opravka z velikimi zbirkami podatkov. Časovna kompleksnost Bubble Sort je v najslabšem primeru O(n^2), kjer je 'n' število elementov na seznamu.
Razčlenimo analizo časovne kompleksnosti:
- Zunanja zanka se izvaja za 'n' iteracij, kjer je 'n' število elementov na seznamu.
- Notranja zanka se v najslabšem primeru izvaja tudi za 'n' iteracij. Vendar pa se z napredovanjem algoritma število ponovitev v notranji zanki zmanjša, saj se največji nerazvrščeni element v vsakem prehodu postavi na pravilno mesto.
- V najslabšem primeru je število primerjav in zamenjav sorazmerno s kvadratom števila elementov na seznamu, kar povzroči O(n^2) časovno kompleksnost. Zaradi tega je mehurčasto razvrščanje neučinkovito za velike nabore podatkov, v aplikacijah v resničnem svetu pa imajo pogosto prednost naprednejši algoritmi za razvrščanje z boljšo časovno kompleksnostjo.
Zaključek
V tem članku smo raziskali koncept Bubble Sort, preprostega algoritma za razvrščanje, ki vedno znova primerja in zamenjuje sosednje elemente, dokler ni razvrščen celoten seznam. Zagotovili smo implementacijo Bubble Sort v Pythonu, jo zagnali z vzorčnim seznamom in analizirali izhod. Poleg tega smo razpravljali o časovni zapletenosti Bubble Sort, pri čemer smo poudarili njeno najslabšo časovno zapletenost O(n^2) in njene posledice za učinkovitost.