Bubble Sort je jednostavan algoritam za sortiranje koji više puta prolazi kroz popis, uspoređuje susjedne elemente i mijenja ih ako su u pogrešnom redoslijedu. Naziva se 'Bubble Sort' jer manji elementi 'bublje' na vrhu popisa. Iako nije najučinkovitiji algoritam sortiranja, lako ga je razumjeti i implementirati, što ga čini dobrom polaznom točkom za učenje o algoritmima sortiranja. U ovom ćemo članku istražiti koncept Bubble Sort-a, dati Python implementaciju s izlazom i raspravljati o vremenskoj složenosti algoritma.

Razumijevanje Bubble Sort

Osnovna ideja Bubble Sort-a je iteracija kroz popis više puta, uspoređujući susjedne elemente i mijenjajući ih ako nisu u redu. Proces se nastavlja sve dok više ne budu potrebne zamjene, što znači da je popis sada sortiran. Algoritam je dobio ime po načinu na koji se manji elementi postupno pomiču na vrh liste, slično kao mjehurići koji se dižu na površinu.

Razdvojimo korake algoritma Bubble Sort:

1. Iterirajte kroz popis: Počnite od početka popisa i usporedite svaki par susjednih elemenata.
2. Usporedi i zamijeni: Ako su elementi u pogrešnom redoslijedu, zamijeni ih. To osigurava da se veći element 'napuha', a manji pomakne prema dolje.
3. Nastavite s ponavljanjem: Ponovite postupak za svaki par susjednih elemenata dok ne dođete do kraja popisa.
4. Ponavljajte dok ne bude razvrstano: Nastavite ponavljati kroz popis dok više ne budu potrebne izmjene. U ovom trenutku popis je sortiran.

Iako je Bubble Sort jednostavan za razumijevanje, to nije najučinkovitiji algoritam sortiranja, posebno za velike skupove podataka. Njegova vremenska složenost je O(n^2) u najgorem slučaju, gdje je 'n' broj elemenata na listi. Ova kvadratna vremenska složenost čini ga manje prikladnim za velike skupove podataka u usporedbi s naprednijim algoritmima sortiranja.

Python implementacija Bubble Sort-a

Sada implementirajmo Bubble Sort u Python i promatrajmo njegovo ponašanje pomoću popisa uzoraka:

 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) 

U ovoj implementaciji, funkcija bubble_sort uzima popis (arr) kao svoj parametar i sortira ga na mjestu. Ugniježđena petlja uspoređuje susjedne elemente i mijenja ih ako su u pogrešnom redoslijedu. Vanjska petlja osigurava da se proces ponavlja dok se cijeli popis ne sortira.

Izlaz i objašnjenje

Pokrenimo isporučeni Python kod s popisom uzoraka i promatrajmo izlaz:

 Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90] 

Ovdje je izvorni popis [64, 34, 25, 12, 22, 11, 90] uspješno razvrstan pomoću algoritma Bubble Sort, što je rezultiralo sortiranim popisom [11, 12, 22, 25, 34, 64, 90].

Algoritam ponavlja kroz popis više puta, uspoređujući i mijenjajući elemente dok se cijeli popis ne sortira. U svakom prolazu, najveći nerazvrstani element 'pomiče' se na svoju ispravnu poziciju. Ovaj se proces nastavlja sve dok više ne budu potrebne zamjene, što znači da je popis u potpunosti sortiran.

Iako Bubble Sort uspješno razvrstava popis, važno je napomenuti da ga njegova vremenska složenost čini manje učinkovitim za velike skupove podataka u usporedbi s drugim algoritmima za razvrstavanje kao što su Merge Sort ili Quick Sort.

Vremenska složenost mjehuričastog sortiranja

Razumijevanje vremenske složenosti algoritma ključno je za procjenu njegove učinkovitosti, posebno kada se radi o velikim skupovima podataka. Vremenska složenost Bubble Sort-a je O(n^2) u najgorem slučaju, gdje je 'n' broj elemenata na popisu.

Razdvojimo analizu vremenske složenosti:

• Vanjska petlja radi za 'n' iteracija, gdje je 'n' broj elemenata na popisu.
• Unutarnja petlja također radi 'n' iteracija u najgorem slučaju. Međutim, kako algoritam napreduje, broj ponavljanja u unutarnjoj petlji se smanjuje, budući da se najveći nesortirani element postavlja na svoje ispravno mjesto u svakom prolazu.
• U najgorem slučaju, broj usporedbi i zamjena proporcionalan je kvadratu broja elemenata na popisu, što rezultira vremenskom složenošću O(n^2). Zbog toga je Bubble Sort neučinkovit za velike skupove podataka, a napredniji algoritmi sortiranja s boljom vremenskom složenošću često se preferiraju u aplikacijama u stvarnom svijetu.

Zaključak

U ovom smo članku istražili koncept Bubble Sort-a, jednostavnog algoritma sortiranja koji više puta uspoređuje i mijenja susjedne elemente dok cijeli popis nije sortiran. Osigurali smo Python implementaciju Bubble Sort-a, pokrenuli je s popisom uzoraka i analizirali izlaz. Osim toga, razgovarali smo o vremenskoj složenosti Bubble Sort-a, naglašavajući njegovu O(n^2) vremensku složenost u najgorem slučaju i njegove implikacije na učinkovitost.