Bubble Sorter Algoritme med Python ved å bruke listeeksempel
Hva er en Bubble sortere?
Bubble Sorter er en sorteringsalgoritme som brukes til å sortere listeelementer i stigende rekkefølge ved å sammenligne to tilstøtende verdier. Hvis den første verdien er høyere enn den andre verdien, tar den første verdien den andre verdiposisjonen, mens den andre verdien tar den første verdiposisjonen. Hvis den første verdien er lavere enn den andre verdien, blir det ikke byttet.
Denne prosessen gjentas til alle verdiene i en liste er sammenlignet og byttet om nødvendig. Hver iterasjon kalles vanligvis et pass. Antall passeringer i en boblesortering er lik antall elementer i en liste minus én.
I dette Bubble Sortering inn Python tutorial du vil lære:
Implementering av Bubble Sorteringsalgoritme
Vi vil dele opp implementeringen i tre (3) trinn, nemlig problemet, løsningen og algoritmen som vi kan bruke til å skrive kode for et hvilket som helst språk.
Problemet
En liste over varene er gitt i tilfeldig rekkefølge, og vi ønsker å ordne varene på en ryddig måte
Tenk på følgende liste:
[21,6,9,33,3]
løsningen
Iterér gjennom listen og sammenligne to tilstøtende elementer og bytt dem hvis den første verdien er høyere enn den andre verdien.
Resultatet skal være som følger:
[3,6,9,21,33]
Algoritme
Algoritmen for boblesortering fungerer som følger
Trinn 1) Få det totale antallet elementer. Få det totale antallet elementer i den gitte listen
Trinn 2) Bestem antall ytre passeringer (n – 1) som skal gjøres. Lengden er liste minus én
Trinn 3) Utfør indre pass (n – 1) ganger for ytre pass 1. Få den første elementverdien og sammenlign den med den andre verdien. Hvis den andre verdien er mindre enn den første verdien, bytt posisjonene
Trinn 4) Gjenta trinn 3 passeringer til du kommer til den ytre passeringen (n – 1). Få det neste elementet i listen, og gjenta deretter prosessen som ble utført i trinn 3 til alle verdiene er plassert i riktig stigende rekkefølge.
Trinn 5) Returner resultatet når alle pasninger er utført. Returner resultatene av den sorterte listen
Trinn 6) Optimaliser algoritmen
Unngå unødvendige indre passeringer hvis listen eller tilstøtende verdier allerede er sortert. For eksempel, hvis den oppgitte listen allerede inneholder elementer som er sortert i stigende rekkefølge, kan vi bryte løkken tidlig.
Optimalisert Bubble Sorteringsalgoritme
Som standard sorteres algoritmen for boble inn Python sammenligner alle elementer i listen uavhengig av om listen allerede er sortert eller ikke. Hvis den gitte listen allerede er sortert, er det bortkastet tid og ressurser å sammenligne alle verdier.
Å optimalisere boblesorteringen hjelper oss å unngå unødvendige iterasjoner og spare tid og ressurser.
For eksempel, hvis det første og andre elementet allerede er sortert, er det ikke nødvendig å iterere gjennom resten av verdiene. Iterasjonen avsluttes, og den neste startes til prosessen er fullført som vist nedenfor Bubble Sorteringseksempel.
Optimalisering gjøres ved å bruke følgende trinn
Trinn 1) Lag en flaggvariabel som overvåker om noen bytte har skjedd i den indre sløyfen
Trinn 2) Hvis verdiene har byttet posisjoner, fortsett til neste iterasjon
Trinn 3) Hvis fordelene ikke har byttet posisjoner, avslutter du den indre sløyfen og fortsetter med den ytre sløyfen.
En optimalisert boblesortering er mer effektiv da den bare utfører de nødvendige trinnene og hopper over de som ikke er nødvendige.
Visuell representasjon
Gitt en liste med fem elementer, illustrerer de følgende bildene hvordan boblens sortering itererer gjennom verdiene når de sorteres
Følgende bilde viser den usorterte listen
Første iterasjon
Trinn 1)
Verdiene 21 og 6 sammenlignes for å sjekke hvilken som er større enn den andre.
21 er større enn 6, så 21 tar posisjonen som er besatt av 6 mens 6 tar posisjonen som ble besatt av 21
Vår modifiserte liste ser nå ut som den ovenfor.
Trinn 2)
Verdiene 21 og 9 sammenlignes.
21 er større enn 9, så vi bytter posisjonene 21 og 9
Den nye listen er nå som ovenfor
Trinn 3)
Verdiene 21 og 33 sammenlignes for å finne den største.
Verdien 33 er større enn 21, så ingen bytting finner sted.
Trinn 4)
Verdiene 33 og 3 sammenlignes for å finne den største.
Verdien 33 er større enn 3, så vi bytter posisjonene deres.
Den sorterte listen på slutten av den første iterasjonen er som den ovenfor
Andre iterasjon
Den nye listen etter den andre iterasjonen er som følger
Tredje iterasjon
Den nye listen etter den tredje iterasjonen er som følger
Fjerde iterasjon
Den nye listen etter den fjerde iterasjonen er som følger
Python Eksempler
Følgende kode viser hvordan du implementerer Bubble Sorter algoritmen inn Python.
def bubbleSort( theSeq ): n = len( theSeq ) for i in range( n - 1 ) : flag = 0 for j in range(n - 1) : if theSeq[j] > theSeq[j + 1] : tmp = theSeq[j] theSeq[j] = theSeq[j + 1] theSeq[j + 1] = tmp flag = 1 if flag == 0: break return theSeq el = [21,6,9,33,3] result = bubbleSort(el) print (result)
Utfører boblesorteringsprogrammet ovenfor i Python gir følgende resultater
[6, 9, 21, 3, 33]
Kode Forklaring
Forklaringen på Python Bubble Sorteringsprogramkoden er som følger
HER,
- Definerer en funksjon bubbleSort som godtar en parameter theSeq. Koden sender ikke ut noe.
- Henter lengden på matrisen og tildeler verdien til en variabel n. Koden sender ikke ut noe
- Starter en for-løkke som kjører boblesorteringsalgoritmen (n – 1) ganger. Dette er den ytre løkken. Koden sender ikke ut noe
- Definerer en flaggvariabel som skal brukes til å bestemme om en swap har skjedd eller ikke. Dette er for optimaliseringsformål. Koden sender ikke ut noe
- Starter den indre sløyfen som sammenligner alle verdiene i listen fra den første til den siste. Koden sender ikke ut noe.
- Bruker if-setningen for å sjekke om verdien på venstre side er større enn den på høyre side. Koden sender ikke ut noe.
- Tildeler verdien av theSeq[j] til en tidsvariabel tmp hvis betingelsen evalueres til sann. Koden sender ikke ut noe
- Verdien av Seq[j + 1] er tilordnet posisjonen til Seq[j]. Koden sender ikke ut noe
- Verdien av variabelen tmp er tilordnet posisjonen Seq[j + 1]. Koden sender ikke ut noe
- Flaggvariabelen tildeles verdien 1 for å indikere at et bytte har funnet sted. Koden sender ikke ut noe
- Bruker en if-setning for å sjekke om verdien til variabelflagget er 0. Koden gir ikke ut noe
- Hvis verdien er 0, kaller vi break-setningen som går ut av den indre sløyfen.
- Returnerer verdien til theSeq etter at den har blitt sortert. Koden gir ut den sorterte listen.
- Definerer en variabel el som inneholder en liste over tilfeldige tall. Koden sender ikke ut noe.
- Tildeler verdien til funksjonen bubbleSort til et variabelt resultat.
- Skriver ut verdien av variabelresultatet.
Bubble sortere fordeler
Følgende er noen av fordelene med boblesorteringsalgoritmen
- Det er lett å forstå
- Den fungerer veldig bra når listen allerede er eller nesten er sortert
- Det krever ikke mye minne.
- Det er enkelt å skrive koden for algoritmen
- Plassbehovet er minimalt sammenlignet med andre sorteringsalgoritmer.
Bubble sort Ulemper
Følgende er noen av ulempene med boblesorteringsalgoritmen
- Den fungerer dårlig når du sorterer store lister. Det tar for mye tid og ressurser.
- Den brukes for det meste til akademiske formål og ikke den virkelige applikasjonen.
- Antall trinn som kreves for å sortere listen er av rekkefølgen n2
Kompleksitetsanalyse av Bubble Sorter
Det er tre typer kompleksitet:
1) Sorter kompleksitet
Sorteringskompleksiteten brukes til å uttrykke mengden utførelsestider og plass som det tar å sortere listen. Boblesorteringen gjør (n – 1) iterasjoner for å sortere listen der n er det totale antallet elementer i listen.
2) Tidskompleksitet
Tidskompleksiteten til boblesorteringen er O(n2)
Tidskompleksitetene kan kategoriseres som:
- I verste fall – det er her den oppgitte listen er i synkende rekkefølge. Algoritmen utfører maksimalt antall henrettelser som er uttrykt som [Big-O] O(n)2)
- Beste sak – dette skjer når den angitte listen allerede er sortert. Algoritmen utfører minimum antall henrettelser som er uttrykt som [Big-Omega] Ω(n)
- Gjennomsnittlig tilfelle – dette skjer når listen er i tilfeldig rekkefølge. Den gjennomsnittlige kompleksiteten er representert som [Big-theta] ⊝(n2)
3) Romkompleksitet
Plasskompleksiteten måler hvor mye ekstra plass som trengs for å sortere listen. Boblesorteringen krever bare én (1) ekstra plass for den tidsvariablen som brukes til å bytte verdier. Derfor har den en romkompleksitet på O (1).
Oppsummering
- Boblesorteringsalgoritmen fungerer ved å sammenligne to tilstøtende verdier og bytte dem hvis verdien til venstre er mindre enn verdien til høyre.
- Implementering av en boblesorteringsalgoritme er relativt rett frem med Python. Alt du trenger å bruke er for loops og if-setninger.
- Problemet som boblesorteringsalgoritmen løser er å ta en tilfeldig liste over elementer og gjøre den om til en ordnet liste.
- Boblesorteringsalgoritmen i datastrukturen fungerer best når listen allerede er sortert ettersom den utfører et minimalt antall iterasjoner.
- Algoritmen for boblesortering fungerer ikke bra når listen er i omvendt rekkefølge.
- Boblesorteringen har en tidskompleksitet på O (n2) og en romkompleksitet på O (1)
- Boblesorteringsalgoritmen er best egnet for akademiske formål og ikke virkelige applikasjoner.
- Den optimaliserte boblesorteringen gjør algoritmen mer effektiv ved å hoppe over unødvendige iterasjoner når du sjekker verdier som allerede er sortert.