Bubble Sort er en enkel algoritme som brukes til å sortere et gitt sett med n -elementer gitt i form av en matrise med n antall elementer. Boblesortering sammenligner alle elementene en etter en og sorterer dem basert på verdiene.
Hvis den gitte matrisen må sorteres i stigende rekkefølge, begynner boblesorteringen med å sammenligne det første elementet i matrisen det andre elementet, hvis det første elementet er større enn det andre elementet, vil det bytte begge elementene, og deretter gå videre for å sammenligne det andre og det tredje elementet, og så videre.
Hvis vi har totalt n elementer, så må vi gjenta denne prosessen i n-1 ganger.
Det er kjent som boblesortering, fordi med hvert komplett iterasjon, det største elementet i den gitte matrisen, bobler opp mot det siste stedet eller den høyeste indeksen, akkurat som en vannboble stiger opp til vannoverflaten.
Sortering skjer ved å gå gjennom alle elementene en etter en og sammenligne den med det tilstøtende elementet og bytte dem om nødvendig.
MERK: Hvis du ikke er kjent med Sortering i datastruktur, bør du Lær først hva som er sortering for å vite om grunnleggende sortering.
Implementering av boblesorteringsalgoritme
Følgende er trinnene involvert i boblesortering (for å sortere en gitt matrise i stigende rekkefølge):
- Begynn med det første elementet (indeks = 0), sammenlign det nåværende elementet med det neste elementet i matrisen.
- Hvis det nåværende elementet er større enn det neste elementet i matrisen, bytt dem.
- Hvis det nåværende elementet er mindre enn neste element, flytt til neste element. Gjenta trinn 1.
La oss vurdere en matrise med verdier {5, 1, 6, 2, 4, 3}
Nedenfor har vi en billedlig fremstilling av hvordan boblesortering vil sortere den gitte matrisen.
Så som vi kan se i representasjonen ovenfor, etter første iterasjon, 6 er plassert ved den siste indeksen, som er riktig posisjon for den.
Tilsvarende etter den andre iterasjonen, 5 vil være på nest siste indeks, og så videre.
Tid for å skrive koden for boblesortering:
Selv om ovennevnte logikk vil sortere en usortert matrise, er algoritmen ovenfor ikke effektiv, men i henhold til ovennevnte logikk er den ytre for loop fortsetter å kjøre i 6 iterasjoner, selv om matrisen blir sortert etter den andre iterasjonen.
Så, vi kan tydelig optimalisere algoritmen vår.
Optimalisert boblesorteringsalgoritme
For å optimalisere boblen vår le sort algoritme, kan vi introdusere en flag for å overvåke om elementene blir byttet inne i den indre for sløyfen.
Derfor, i den indre for sløyfen, sjekker vi om bytte av elementer foregår eller ikke, hver gang.
Hvis det ikke var noe bytte for en bestemt iterasjon sted, betyr det at matrisen er sortert, og vi kan hoppe ut av for sløyfen, i stedet for å utføre alle iterasjonene.
La oss vurdere en matrise med verdier {11, 17, 18, 26, 23}
Nedenfor har vi en illustrasjon av hvordan den optimaliserte boblesorteringen vil sortere den gitte matrisen.
Som vi kan se, i den første iterasjonen fant bytting sted, derfor oppdaterte vi flag -verdien til 1, som et resultat går kjøringen inn i for sløyfen igjen. Men i den andre iterasjonen vil ingen bytte forekomme, derav verdien flag vil forbli 0, og utførelsen vil bryte ut av loop.
I ovennevnte kode, i funksjonen bubbleSort, hvis for en enkelt komplett syklus med j iterasjon (indre for loop), ingen bytting finner sted, så flag vil forbli 0 og så vil vi bryte ut av for løkkene, fordi matrisen allerede er sortert.
Kompleksitetsanalyse av boblesortering
I boblesortering vil n-1 sammenligninger gjøres i første omgang, n-2 i 2. pass, n-3 i 3. pass og så videre. Så det totale antallet sammenligninger vil være,
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2i.e O (n2)
Derfor er tidskompleksiteten til Bubble Sort O (n2).
Den største fordelen med Bubble Sort er algoritmens enkelhet.
Plasskompleksiteten for boblesortering er O (1), fordi det bare kreves et ekstra minneområde, dvs. for temp -variabelen.
Dessuten vil tidskompleksiteten i beste fall være O (n), det er når listen allerede er sortert.
Følgende er tid og rom-kompleksitet for Bubble Sort-algoritmen.
Nå som vi har lært Bubble sorteringsalgoritme, kan du også sjekke ut disse sorteringsalgoritmene og deres applikasjoner:
- Innsettingssorter
- Valg
- Rask sortering
- flett Sorter
- Heap Sort
- Counting Sort
