Bubble Sortér Algoritme med Python ved hjælp af listeeksempel

Hvad er en Bubble sortere?

Bubble Sortere er en sorteringsalgoritme, der bruges til at sortere listeelementer i stigende rækkefølge ved at sammenligne to tilstødende værdier. Hvis den første værdi er højere end den anden værdi, tager den første værdi den anden værdis position, mens den anden værdi tager den første værdis position. Hvis den første værdi er lavere end den anden værdi, er der ingen ombytning.ping Er gjort.

Denne proces gentages, indtil alle værdierne i en liste er blevet sammenlignet og byttet om nødvendigt. Hver iteration kaldes normalt et pass. Antallet af gennemløb i en boblesortering er lig med antallet af elementer i en liste minus én.

I denne Bubble Indsortering Python tutorial Du vil lære det problem, den løser, dens optimerede form, en trinvis visuel gennemgang, en fungerende Python programmet og dets ydeevnekarakteristika.

Gennemførelse af Bubble Sorteringsalgoritme

Vi vil opdele implementeringen i tre (3) trin, nemlig problemet, løsningen og algoritmen, som vi kan bruge til at skrive kode til ethvert sprog.

Problemet

En liste over elementer er givet i tilfældig rækkefølge, og vi vil gerne arrangere elementerne på en ordentlig måde.

Overvej følgende liste:

[21, 6, 9, 33, 3]

løsningen

Iterer gennem listen, sammenligner to tilstødende elementer og bytterping dem, hvis den første værdi er højere end den anden værdi.

Resultatet skal være som følger:

[3, 6, 9, 21, 33]

Algoritme

Boblesorteringsalgoritmen fungerer som følger:

Trin 1) Hent det samlede antal elementer. Hent det samlede antal elementer i den givne liste.

Trin 2) Bestem antallet af ydre passager (n – 1), der skal udføres. Længden er liste minus én.

Trin 3) Udfør indre gennemløb (n – 1) gange for ydre gennemløb 1. Find den første elementværdi og sammenlign den med den anden værdi. Hvis den anden værdi er mindre end den første værdi, skal du bytte om på positionerne.

Trin 4) Gentag trin 3 i alle gennemløb, indtil du når det ydre gennemløb (n – 1). Hent det næste element på listen, og gentag derefter processen fra trin 3, indtil alle værdierne er placeret i den korrekte stigende rækkefølge.

Trin 5) Returner resultatet, når alle gennemløb er gennemført. Returner resultaterne af den sorterede liste.

Trin 6) Optimer algoritme.

Undgå unødvendige indre gennemløb, hvis listen eller tilstødende værdier allerede er sorteret. For eksempel, hvis den angivne liste allerede indeholder elementer, der er blevet sorteret i stigende rækkefølge, så kan vi bryde løkken tidligt.

Optimeret Bubble Sorteringsalgoritme

Som standard sorterer algoritmen for boble ind Python sammenligner alle elementer på listen, uanset om listen allerede er sorteret eller ej. Hvis den givne liste allerede er sorteret, er det spild af tid og ressourcer at sammenligne alle værdier.

Optimering af boblesorteringen hjælper os med at undgå unødvendige gentagelser og spare tid og ressourcer.

For eksempel, hvis det første og det andet element allerede er sorteret, er der ingen grund til at gentage resten af ​​værdierne. Iterationen afsluttes, og den næste startes, indtil processen er afsluttet som vist i nedenstående Bubble Sorteringseksempel.

Optimering udføres ved hjælp af følgende trin:

Trin 1) Opret en flagvariabel, der overvåger, om der er nogen swapping er sket i det indre loop.

Trin 2) Hvis værdierne har byttet plads, fortsæt til næste iteration.

Trin 3) Hvis værdierne ikke har byttet plads, afslut den indre løkke og fortsæt med den ydre løkke.

En optimeret boblesortering er mere effektiv, da den kun udfører de nødvendige trin og springer dem over, der ikke er nødvendige.

Visuel repræsentation

Givet en liste med fem elementer illustrerer følgende billeder, hvordan boblesorteringen itererer gennem værdierne, når den sorterer dem.

Følgende billede viser den usorterede liste:

Første iteration

Trin 1)

Værdierne 21 og 6 sammenlignes for at kontrollere, hvilken der er større end den anden.

21 er større end 6, så 21 indtager den position, der var besat af 6, mens 6 indtager den position, der var besat af 21.

Vores ændrede liste ser nu ud som ovenstående.

Trin 2)

Værdierne 21 og 9 sammenlignes.

21 er større end 9, så vi bytter om på pladserne for 21 og 9.

Den nye liste er nu som ovenfor.

Trin 3)

Værdierne 21 og 33 sammenlignes for at finde den største.

Værdien 33 er større end 21, så ingen ombytningping finder sted.

Trin 4)

Værdierne 33 og 3 sammenlignes for at finde den største.

Værdien 33 er større end 3, så vi bytter deres positioner.

Den sorterede liste i slutningen af ​​den første iteration er som den ovenfor.

Anden iteration

Den nye liste efter anden iteration er som følger:

Tredje iteration

Den nye liste efter den tredje iteration er som følger:

Fjerde iteration

Den nye liste efter den fjerde iteration er som følger:

Python Eksempler

Følgende kode viser, hvordan man implementerer Bubble Sorter algoritme ind 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)

Udførelse af ovenstående boblesorteringsprogram i Python producerer følgende resultater:

[3, 6, 9, 21, 33]

Code Forklaring

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

HER,

1. Definerer en funktion bubbleSort, der accepterer en parameter theSeq. Koden udsender ikke noget.
2. Henter længden af ​​arrayet og tildeler værdien til en variabel n. Koden udskriver ikke noget.
3. Starter en for-løkke, der kører boblesorteringsalgoritmen (n – 1) gange. Dette er den ydre løkke. Koden udsender ikke noget.
4. Definerer en flagvariabel, der bruges til at bestemme, om der er sket en swap eller ej. Dette er til optimeringsformål. Koden udskriver ikke noget.
5. Starter den indre sløjfe, der sammenligner alle værdierne på listen fra den første til den sidste. Koden udsender ikke noget.
6. Bruger if-sætningen til at kontrollere, om værdien på venstre side er større end værdien på den umiddelbare højre side. Koden udsender ikke noget.
7. Tildeler værdien af ​​theSeq[j] til en temporal variabel tmp, hvis betingelsen evalueres til sand. Koden udsender ikke noget.
8. Værdien af ​​theSeq[j + 1] tildeles positionen af ​​theSeq[j]. Koden udskriver ikke noget.
9. Værdien af ​​variablen tmp tildeles positionen theSeq[j + 1]. Koden udskriver ikke noget.
10. Flagvariablen tildeles værdien 1 for at indikere, at der har fundet en swap sted. Koden udsender ikke noget.
11. Bruger en if-sætning til at kontrollere, om værdien af ​​variablen flag er 0. Koden udsender ikke noget.
12. Hvis værdien er 0, kalder vi break-sætningen, der træder ud af den indre løkke.
13. Returnerer værdien af ​​theSeq, efter at den er blevet sorteret. Koden udsender den sorterede liste.
14. Definerer en variabel el, der indeholder en liste over tilfældige tal. Koden udsender ikke noget.
15. Tildeler værdien af ​​funktionen bubbleSort til et variabelt resultat.
16. Udskriver værdien af ​​variabelresultatet.

Bubble sortere fordele

Følgende er nogle af fordelene ved boblesorteringsalgoritmen:

• Det er let at forstå.
• Den fungerer rigtig godt, når listen allerede er eller næsten er sorteret.
• Det kræver ikke omfattende hukommelse.
• Det er nemt at skrive koden til algoritmen.
• Pladskravene er minimale sammenlignet med andre sorteringsalgoritmer.

Bubble sort Ulemper

Følgende er nogle af ulemperne ved boblesorteringsalgoritmen:

• Det fungerer ikke godt, når man sorterer store lister. Det tager for meget tid og ressourcer.
• Det bruges mest til akademiske formål og ikke til den virkelige verden.
• Antallet af nødvendige trin for at sortere listen er af størrelsesordenen n².

Kompleksitetsanalyse af Bubble Sortere

Der er tre typer af kompleksitet:

1) Sorter kompleksitet

Sorteringskompleksiteten bruges til at udtrykke den mængde udførelsestid og plads, det tager at sortere listen. Boblesorteringen udfører (n – 1) iterationer for at sortere listen, hvor n er det samlede antal elementer i listen.

2) Tidskompleksitet

Tidskompleksiteten af ​​boblesorteringen er O(n²).

Tidskompleksiteterne kan kategoriseres som:

• Værste tilfælde – det er her den angivne liste er i faldende rækkefølge. Algoritmen udfører det maksimale antal eksekveringer, som er udtrykt som [Big-O] O(n)²).
• Bedste sag – dette sker, når den angivne liste allerede er sorteret. Algoritmen udfører det minimale antal udførelser, hvilket udtrykkes som [Big-Omega] Ω(n).
• Gennemsnitligt tilfælde – dette sker, når listen er i tilfældig rækkefølge. Den gennemsnitlige kompleksitet er repræsenteret som [Big-theta] ⊝(n²).

3) Rumkompleksitet

Pladskompleksiteten måler den mængde ekstra plads, der er nødvendig for at sortere listen. Boblesorteringen kræver kun ét (1) ekstra mellemrum til den tidsmæssige variabel, der bruges til swap.ping værdier. Derfor har den en rumkompleksitet på O(1).

Ofte Stillede Spørgsmål