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 verdiens plassering, mens den andre verdien tar den første verdiens plassering. Hvis den første verdien er lavere enn den andre verdien, skjer det ingen bytte.ping er ferdig.

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 problemet den løser, den optimaliserte formen, en trinnvis visuell gjennomgang, en fungerende Python programmet og dets ytelsesegenskaper.

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 ethvert språk.

Problemet

En liste over elementer er gitt i tilfeldig rekkefølge, og vi ønsker å ordne elementene på en ordnet måte.

Tenk på følgende liste:

[21, 6, 9, 33, 3]

løsningen

Iterer gjennom listen, sammenligner to tilstøtende elementer og bytterping 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 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 passeringer (n – 1) ganger for ytre passering 1. Finn 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-omgangene til du kommer til den ytre omgangen (n – 1). Hent 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 passeringer er fullført. Returner resultatene fra 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 hjelp av følgende trinn:

Trinn 1) Opprett en flaggvariabel som overvåker om det finnes noen bytterping har skjedd i den indre sløyfen.

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

Trinn 3) Hvis verdiene ikke har byttet posisjon, avslutter du den indre løkken og fortsetter med den ytre løkken.

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 boblesorteringen itererer gjennom verdiene når den 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 tar posisjonen som var okkupert av 6, mens 6 tar posisjonen som var okkupert 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 om på posisjonene til 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 bytteping tar plass.

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:

[3, 6, 9, 21, 33]

Code Forklaring

Forklaringen på Python Bubble Sorteringsprogramkoden er som følger:

HER,

1. Definerer en funksjon bubbleSort som godtar en parameter theSeq. Koden sender ikke ut noe.
2. Henter lengden på arrayet og tilordner 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 å avgjøre om en 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 temporal variabel tmp hvis betingelsen evalueres til sann. Koden sender ikke ut noe.
8. Verdien til theSeq[j + 1] tilordnes posisjonen til theSeq[j]. Koden sender ikke ut noe.
9. Verdien til variabelen tmp er tilordnet posisjonen theSeq[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 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 mest til akademiske formål og ikke til praktiske formål.
• Antall trinn som kreves for å sortere listen er av rekkefølgen n².

Kompleksitetsanalyse av Bubble Sorter

Det finnes tre typer kompleksitet:

1) Sorter kompleksitet

Sorteringskompleksiteten brukes til å uttrykke hvor mye utførelsestid og plass det tar å sortere listen. Boblesorteringen utfører (n – 1) iterasjoner for å sortere listen, der n er det totale antallet elementer i listen.

2) Tidskompleksitet

Tidskompleksiteten til boblesorteringen er O(n²).

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)²).
• Beste sak – dette skjer når den oppgitte listen allerede er sortert. Algoritmen utfører minimum antall utførelser, som uttrykkes som [Big-Omega] Ω(n).
• Gjennomsnittlig tilfelle – dette skjer når listen er i tilfeldig rekkefølge. Den gjennomsnittlige kompleksiteten er representert som [Big-theta] ⊝(n²).

3) Romkompleksitet

Romkompleksiteten måler mengden ekstra plass som trengs for å sortere listen. Boblesorteringen krever bare ett (1) ekstra mellomrom for den tidsvariabelen som brukes til bytte.ping verdier. Derfor har den en romkompleksitet på O(1).

Spørsmål og svar