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

Visuell representasjon

Første iterasjon

Trinn 1)

Visuell representasjon

Verdiene 21 og 6 sammenlignes for å sjekke hvilken som er større enn den andre.

Visuell representasjon

21 er større enn 6, så 21 tar posisjonen som er besatt av 6 mens 6 tar posisjonen som ble besatt av 21

Visuell representasjon

Vår modifiserte liste ser nå ut som den ovenfor.

Trinn 2)

Visuell representasjon

Verdiene 21 og 9 sammenlignes.

Visuell representasjon

21 er større enn 9, så vi bytter posisjonene 21 og 9

Visuell representasjon

Den nye listen er nå som ovenfor

Trinn 3)

Visuell representasjon

Verdiene 21 og 33 sammenlignes for å finne den største.

Visuell representasjon

Verdien 33 er større enn 21, så ingen bytting finner sted.

Trinn 4)

Visuell representasjon

Verdiene 33 og 3 sammenlignes for å finne den største.

Visuell representasjon

Verdien 33 er større enn 3, så vi bytter posisjonene deres.

Visuell representasjon

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

Visuell representasjon

Tredje iterasjon

Den nye listen etter den tredje iterasjonen er som følger

Visuell representasjon

Fjerde iterasjon

Den nye listen etter den fjerde iterasjonen er som følger

Visuell representasjon

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

Kode Forklaring

HER,

  1. Definerer en funksjon bubbleSort som godtar en parameter theSeq. Koden sender ikke ut noe.
  2. Henter lengden på matrisen og tildeler verdien til en variabel n. Koden sender ikke ut noe
  3. Starter en for-løkke som kjører boblesorteringsalgoritmen (n – 1) ganger. Dette er den ytre løkken. Koden sender ikke ut noe
  4. 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
  5. Starter den indre sløyfen som sammenligner alle verdiene i listen fra den første til den siste. Koden sender ikke ut noe.
  6. Bruker if-setningen for å sjekke om verdien på venstre side er større enn den på høyre side. Koden sender ikke ut noe.
  7. Tildeler verdien av theSeq[j] til en tidsvariabel tmp hvis betingelsen evalueres til sann. Koden sender ikke ut noe
  8. Verdien av Seq[j + 1] er tilordnet posisjonen til Seq[j]. Koden sender ikke ut noe
  9. Verdien av variabelen tmp er tilordnet posisjonen Seq[j + 1]. Koden sender ikke ut noe
  10. Flaggvariabelen tildeles verdien 1 for å indikere at et bytte har funnet sted. Koden sender ikke ut noe
  11. Bruker en if-setning for å sjekke om verdien til variabelflagget er 0. Koden gir ikke ut noe
  12. Hvis verdien er 0, kaller vi break-setningen som går ut av den indre sløyfen.
  13. Returnerer verdien til theSeq etter at den har blitt sortert. Koden gir ut den sorterte listen.
  14. Definerer en variabel el som inneholder en liste over tilfeldige tall. Koden sender ikke ut noe.
  15. Tildeler verdien til funksjonen bubbleSort til et variabelt resultat.
  16. 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.