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, indtager den første værdi den anden værdiposition, mens den anden værdi indtager den første værdiposition. Hvis den første værdi er lavere end den anden værdi, foretages der ingen ombytning.

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:

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 varer er givet i tilfældig rækkefølge, og vi vil gerne arrangere varerne på en ordentlig måde

Overvej følgende liste:

[21,6,9,33,3]

løsningen

Gentag gennem listen, og sammenlign to tilstødende elementer og skift 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) Få det samlede antal elementer. Få det samlede antal varer på den givne liste

Trin 2) Bestem antallet af ydre gennemløb (n – 1), der skal udføres. Dens længde er liste minus en

Trin 3) Udfør indre gennemløb (n – 1) gange for ydre gennemløb 1. Få 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, så skift positionerne

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

Trin 5) Returner resultatet, når alle afleveringer er udfø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 sket ombytning i den indre sløjfe

Trin 2) Hvis værdierne har byttet position, skal du fortsætte til næste iteration

Trin 3) Hvis fordelene ikke har byttet positioner, skal du afslutte den indre løkke og fortsætte 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

Med en liste med fem elementer illustrerer de følgende billeder, hvordan boblens sortering itererer gennem værdierne, når de sorteres

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 stillingen besat af 6, mens 6 indtager stillingen, der blev 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 positionerne 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å der finder ingen ombytning 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 den 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 giver følgende resultater

[6, 9, 21, 3, 33]

Kode Forklaring

Forklaringen på Python Bubble Sorteringsprogramkoden er som følger

HER,

Definerer en funktion bubbleSort, der accepterer en parameter theSeq. Koden udsender ikke noget.
Henter længden af arrayet og tildeler værdien til en variabel n. Koden udsender ikke noget
Starter en for-løkke, der kører boblesorteringsalgoritmen (n – 1) gange. Dette er den ydre løkke. Koden udsender ikke noget
Definerer en flagvariabel, der vil blive brugt til at bestemme, om en swap har fundet sted eller ej. Dette er med henblik på optimering. Koden udsender ikke noget
Starter den indre sløjfe, der sammenligner alle værdierne på listen fra den første til den sidste. Koden udsender ikke noget.
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.
Tildeler værdien af Seq[j] til en tidsvariabel tmp, hvis betingelsen evalueres til sand. Koden udsender ikke noget
Værdien af Seq[j + 1] er tildelt positionen af Seq[j]. Koden udsender ikke noget
Værdien af variablen tmp tildeles positionen Seq[j + 1]. Koden udsender ikke noget
Flagvariablen tildeles værdien 1 for at indikere, at en swap har fundet sted. Koden udsender ikke noget
Bruger en if-sætning til at kontrollere, om værdien af variabelflaget er 0. Koden udsender ikke noget
Hvis værdien er 0, kalder vi break-sætningen, der træder ud af den indre løkke.
Returnerer værdien af theSeq, efter at den er blevet sorteret. Koden udsender den sorterede liste.
Definerer en variabel el, der indeholder en liste over tilfældige tal. Koden udsender ikke noget.
Tildeler værdien af funktionen bubbleSort til et variabelt resultat.
Udskriver værdien af variabelresultatet.

Bubble sortere fordele

Det følgende er nogle af fordelene ved boblesorteringsalgoritmen

Det er let at forstå
Det fungerer meget 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

Det 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 kompleksitet:

1) Sorter kompleksitet

Sorteringskompleksiteten bruges til at udtrykke mængden af eksekveringstider og plads, som det tager at sortere listen. Boblesorteringen foretager (n – 1) iterationer for at sortere listen, hvor n er det samlede antal elementer på 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 mindste antal henrettelser, som er udtrykt 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 mængden af ekstra plads, der er nødvendig for at sortere listen. Boblesorteringen kræver kun én (1) ekstra plads til den tidsvariable, der bruges til at bytte værdier. Derfor har det en rumkompleksitet på O (1).

Resumé

Boblesorteringsalgoritmen fungerer ved at sammenligne to tilstødende værdier og bytte dem, hvis værdien til venstre er mindre end værdien til højre.
Implementering af en boblesorteringsalgoritme er relativt ligetil med Python. Alt du skal bruge er til loops og if-sætninger.
Problemet, som boblesorteringsalgoritmen løser, er at tage en tilfældig liste over elementer og omdanne den til en ordnet liste.
Boblesorteringsalgoritmen i datastrukturen fungerer bedst, når listen allerede er sorteret, da den udfører et minimalt antal iterationer.
Boblesorteringsalgoritmen fungerer ikke godt, når listen er i omvendt rækkefølge.
Boblesorteringen har en tidskompleksitet på O (n²) og en rumkompleksitet på O (1)
Boblesorteringsalgoritmen er bedst egnet til akademiske formål og ikke til virkelige applikationer.
Den optimerede boblesortering gør algoritmen mere effektiv ved at springe unødvendige iterationer over, når du tjekker værdier, der allerede er sorteret.

Du kan lide: