Boblesorteringsalgoritme med Python ved hjelp av listeeksempel

Innholdsfortegnelse:

Anonim

Hva er en boblesortering?

Bubble Sort 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 verdien, mens den andre verdien tar den første verdien. Hvis den første verdien er lavere enn den andre verdien, blir ingen bytte utført.

Denne prosessen gjentas til alle verdiene i en liste er blitt sammenlignet og byttet ut om nødvendig. Hver iterasjon kalles vanligvis et pass. Antall passeringer i en boblesortering er lik antall elementer i en liste minus en.

I denne boblesorteringen i Python-opplæringen lærer du:

  • Hva er en boblesortering?
  • Implementering av boblesorteringsalgoritmen
  • Optimalisert boblesorteringsalgoritme
  • Visuell representasjon
  • Python eksempler
  • Kode Forklaring
  • Fordeler med boblesortering
  • Boblesortering Ulemper
  • Kompleksitetsanalyse av boblesortering

Implementering av boblesorteringsalgoritmen

Vi vil dele opp implementeringen i tre (3) trinn, nemlig problemet, løsningen og algoritmen som vi kan bruke til å skrive kode for hvilket som helst språk.

Problemet

En liste over varene er gitt i tilfeldig rekkefølge, og vi vil ordne varene på en ordnet måte

Vurder følgende liste:

[21,6,9,33,3]

Løsningen

Iterer gjennom listen og sammenligner to tilstøtende elementer og bytter 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

Boblesorteringsalgoritmen fungerer som følger

Trinn 1) Få det totale antallet elementer. Få det totale antallet artikler i den gitte listen

Trinn 2) Bestem antall ytre passeringer (n - 1) som skal utføres. Lengden er liste minus en

Trinn 3) Utfør indre passeringer (n - 1) ganger for ytre passering 1. Få den første elementverdien og sammenlign den med den andre verdien. Hvis den andre verdien er mindre enn den første verdien, bytter du posisjonene

Trinn 4) Gjenta trinn 3 passerer til du kommer til det ytre passet (n - 1). Få neste element 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 gjort. 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 angitte listen allerede inneholder elementer som er sortert i stigende rekkefølge, så kan vi bryte sløyfen tidlig.

Optimalisert boblesorteringsalgoritme

Som standard sammenligner algoritmen for boblesortering i Python alle elementene 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.

Optimalisering av boblesorteringen hjelper oss med å unngå unødvendige iterasjoner og spare tid og ressurser.

For eksempel, hvis det første og det andre elementet allerede er sortert, er det ikke nødvendig å itere gjennom resten av verdiene. Iterasjonen avsluttes, og den neste initieres til prosessen er fullført som vist i nedenstående Bubble Sort-eksempel.

Optimalisering gjøres ved hjelp av følgende trinn

Trinn 1) Opprett en flaggvariabel som overvåker om det har skjedd noe bytte i den indre sløyfen

Trinn 2) Hvis verdiene har byttet posisjon, fortsett til neste iterasjon

Trinn 3) Hvis fordelene ikke har byttet posisjon, 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 følgende bilder hvordan boblesorteringen går gjennom verdiene når du sorterer dem

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 inntar posisjonen okkupert av 6 mens 6 inntar posisjonen som ble okkupert av 21

Den modifiserte listen vår ser nå ut som den ovenfor.

Steg 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 bytte foregår.

Trinn 4)

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

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

Den sorterte listen på slutten av den første iterasjonen er som den ovenfor

Andre itering

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

Tredje iterasjon

Den nye listen etter tredje iterasjon 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 Sort-algoritmen i Python.

def bubbleSort( theSeq ):n = len( theSeq )for i in range( n - 1 ) :flag = 0for j in range(n - 1) :if theSeq[j] > theSeq[j + 1] :tmp = theSeq[j]theSeq[j] = theSeq[j + 1]theSeq[j + 1] = tmpflag = 1if flag == 0:breakreturn theSeqel = [21,6,9,33,3]result = bubbleSort(el)print (result)

Å utføre det ovennevnte boblesorteringsprogrammet i Python gir følgende resultater

[6, 9, 21, 3, 33]

Kode Forklaring

Forklaringen på Python Bubble Sort-programkoden er som følger

HER,

  1. Definerer en funksjonsbobleSort som godtar en parameter theSeq. Koden sender ikke ut noe.
  2. Får lengden på matrisen og tilordner verdien til en variabel n. Koden sender ikke ut noe
  3. Starter en for loop som kjører boblesorteringsalgoritmen (n - 1) ganger. Dette er den ytre sløyfen. Koden sender ikke ut noe
  4. Definerer en flaggvariabel som skal brukes til å bestemme om et bytte 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. Tilordner verdien av theSeq [j] til en tidsvariabel tmp hvis tilstanden evalueres til sann. Koden sender ikke ut noe
  8. Verdien av Seq [j + 1] tildeles posisjonen til Seq [j]. Koden sender ikke ut noe
  9. Verdien til variabelen tmp tilordnes posisjonenSeq [j + 1]. Koden sender ikke ut noe
  10. Flaggvariabelen tildeles verdien 1 for å indikere at en bytte har funnet sted. Koden sender ikke ut noe
  11. Bruker en if-setning for å sjekke om verdien på variabelflagget er 0. Koden sender ikke ut noe
  12. Hvis verdien er 0, kaller vi brudduttalelsen som går ut av den indre sløyfen.
  13. Returnerer verdien av Seq etter at den er sortert. Koden sender ut den sorterte listen.
  14. Definerer en variabel el som inneholder en liste over tilfeldige tall. Koden sender ikke ut noe.
  15. Tilordner verdien av funksjonen bubbleSort til et variabelt resultat.
  16. Skriver ut verdien av det variable resultatet.

Fordeler med boblesortering

Følgende er noen av fordelene med boblesorteringsalgoritmen

  • Det er lett å forstå
  • Det fungerer veldig bra når listen allerede er eller nesten sortert
  • Det krever ikke omfattende minne.
  • Det er enkelt å skrive koden for algoritmen
  • Plasskravene er minimale sammenlignet med andre sorteringsalgoritmer.

Boblesortering Ulemper

Følgende er noen av ulempene med boblesorteringsalgoritmen

  • Det fungerer ikke bra når du sorterer store lister. Det tar for mye tid og ressurser.
  • Den brukes mest til akademiske formål og ikke for den virkelige applikasjonen.
  • Antall trinn som kreves for å sortere listen er av størrelsesorden n 2

Kompleksitetsanalyse av boblesortering

Det er tre typer kompleksitet er:

1) Sorter kompleksitet

Sorteringskompleksiteten brukes til å uttrykke mengden utførelsestider og plass som det tar å sortere listen. Boblesorteringen gir (n - 1) iterasjoner for å sortere listen der n er det totale antallet elementer i listen.

2) Tidskompleksitet

Tidskompleksiteten til boblesorteringen er O (n 2 )

Tidskompleksitetene kan kategoriseres som:

  • Verste tilfelle - det er her listen som er oppgitt er i synkende rekkefølge. Algoritmen utfører det maksimale antall utførelser som er uttrykt som [Big-O] O (n 2 )
  • I beste fall - dette skjer når den angitte listen allerede er sortert. Algoritmen utfører det minste antall henrettelser som er uttrykt som [Big-Omega] Ω (n)
  • Gjennomsnittlig tilfelle - dette skjer når listen er i tilfeldig rekkefølge. Gjennomsnittlig kompleksitet er representert som [Big-theta] ⊝ (n 2 )

3) Romkompleksitet

Plasskompleksiteten måler mengden ekstra plass som er nødvendig for å sortere listen. Boblesorteringen krever bare en (1) ekstra plass for den tidsmessige variabelen som brukes til å bytte verdier. Derfor har den en romkompleksitet på O (1).

Sammendrag

  • 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 løkker og hvis uttalelser.
  • Problemet som boblesorteringsalgoritmen løser er å ta en tilfeldig liste over varer og gjøre den om til en ordnet liste.
  • Boblesorteringsalgoritmen i datastrukturen fungerer best når listen allerede er sortert, da den utfører et minimalt antall iterasjoner.
  • Boblesorteringsalgoritmen fungerer ikke bra når listen er i omvendt rekkefølge.
  • Boblersorten har en tidskompleksitet på O (n 2 ) og en romkompleksitet på O (1)
  • Bubbler sorteringsalgoritmen er best egnet for akademiske formål og ikke for 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.