Bubble Sort er en enkel sorteringsalgoritme som gjentatte ganger går gjennom listen, sammenligner tilstøtende elementer og bytter dem hvis de er i feil rekkefølge. Den heter 'Bubble Sort' fordi mindre elementer 'boble' til toppen av listen. Selv om den ikke er den mest effektive sorteringsalgoritmen, er den lett å forstå og implementere, noe som gjør den til et godt utgangspunkt for å lære om sorteringsalgoritmer. I denne artikkelen skal vi fordype oss i konseptet med Bubble Sort, gi en Python-implementering med utdata og diskutere tidskompleksiteten til algoritmen.

streng til int-konverter

Forstå boblesortering

Den grunnleggende ideen bak Bubble Sort er å iterere gjennom listen flere ganger, sammenligne tilstøtende elementer og bytte dem hvis de er ute av drift. Prosessen fortsetter til det ikke er behov for flere bytter, noe som indikerer at listen nå er sortert. Algoritmen har fått navnet sitt fra måten mindre elementer gradvis beveger seg til toppen av listen, omtrent som bobler som stiger til overflaten.

La oss bryte ned trinnene til Bubble Sort-algoritmen:

1. Iterer gjennom listen: Start fra begynnelsen av listen og sammenlign hvert par av tilstøtende elementer.
2. Sammenlign og bytt: Hvis elementene er i feil rekkefølge, bytt dem. Dette sikrer at det større elementet 'bobler opp' og det mindre beveger seg ned.
3. Fortsett å iterere: Gjenta prosessen for hvert par av tilstøtende elementer til slutten av listen er nådd.
4. Gjenta til sortert: Fortsett å gjenta gjennom listen til det ikke er behov for flere bytter. På dette tidspunktet er listen sortert.

Selv om Bubble Sort er enkelt å forstå, er det ikke den mest effektive sorteringsalgoritmen, spesielt for store datasett. Tidskompleksiteten er O(n^2) i verste fall, der 'n' er antall elementer i listen. Denne kvadratiske tidskompleksiteten gjør den mindre egnet for store datasett sammenlignet med mer avanserte sorteringsalgoritmer.

Python-implementering av Bubble Sort

La oss nå implementere Bubble Sort i Python og observere oppførselen med en prøveliste:

 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) 

I denne implementeringen tar bubble_sort-funksjonen en liste (arr) som parameter og sorterer den på plass. Den nestede løkken sammenligner tilstøtende elementer og bytter dem hvis de er i feil rekkefølge. Den ytre løkken sørger for at prosessen gjentas til hele listen er sortert.

Utgang og forklaring

La oss kjøre den medfølgende Python-koden med prøvelisten og observere utgangen:

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

Her er den opprinnelige listen [64, 34, 25, 12, 22, 11, 90] sortert ved hjelp av boblesorteringsalgoritmen, noe som resulterer i den sorterte listen [11, 12, 22, 25, 34, 64, 90].

Algoritmen itererer gjennom listen flere ganger, sammenligner og bytter elementer til hele listen er sortert. I hvert pass 'bobler' det største usorterte elementet opp til sin riktige posisjon. Denne prosessen fortsetter til det ikke er behov for flere bytter, noe som indikerer at listen er fullstendig sortert.

Mens Bubble Sort vellykket sorterer listen, er det viktig å merke seg at tidskompleksiteten gjør den mindre effektiv for store datasett sammenlignet med andre sorteringsalgoritmer som Merge Sort eller Quick Sort.

Tidskompleksiteten til boblesortering

Å forstå tidskompleksiteten til en algoritme er avgjørende for å evaluere effektiviteten, spesielt når man arbeider med store datasett. Tidskompleksiteten til Bubble Sort er O(n^2) i verste fall, der 'n' er antall elementer i listen.

La oss bryte ned tidskompleksitetsanalysen:

• Den ytre løkken kjører for 'n' iterasjoner, der 'n' er antall elementer i listen.
• Den indre sløyfen kjører også for 'n' iterasjoner i verste fall. Men etter hvert som algoritmen skrider frem, reduseres antall iterasjoner i den indre sløyfen, ettersom det største usorterte elementet blir plassert på sin riktige posisjon i hver pass.
• I verste fall er antall sammenligninger og bytter proporsjonal med kvadratet av antall elementer i listen, noe som resulterer i O(n^2) tidskompleksiteten. Dette gjør Bubble Sort ineffektiv for store datasett, og mer avanserte sorteringsalgoritmer med bedre tidskompleksitet foretrekkes ofte i virkelige applikasjoner.

Konklusjon

I denne artikkelen utforsket vi konseptet Bubble Sort, en enkel sorteringsalgoritme som gjentatte ganger sammenligner og bytter tilstøtende elementer til hele listen er sortert. Vi ga en Python-implementering av Bubble Sort, kjørte den med en prøveliste og analyserte utdataene. I tillegg diskuterte vi tidskompleksiteten til Bubble Sort, og fremhevet dens O(n^2) verste tidskompleksitet og dens implikasjoner for effektivitet.