Hvad er en boblesortering?
Boblesortering 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ærdi, mens den anden værdi tager den første værdi. Hvis den første værdi er lavere end den anden værdi, foretages der ingen bytte.
Denne proces gentages, indtil alle værdierne i en liste er blevet sammenlignet og om nødvendigt byttet. Hver iteration kaldes normalt et pas. Antallet af passeringer i en boblesortering er lig med antallet af elementer i en liste minus en.
I denne Bubble Sorting in Python-tutorial lærer du:
- Hvad er en boblesortering?
- Implementering af boblesorteringsalgoritmen
- Optimeret boblesorteringsalgoritme
- Visuel repræsentation
- Python eksempler
- Kode Forklaring
- Fordele ved boblesortering
- Boblesortering Ulemper
- Kompleksitetsanalyse af boblesortering
Implementering af boblesorteringsalgoritmen
Vi opdeler 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 ordentligt
Overvej følgende liste:
[21,6,9,33,3]
Løsningen
Iterer gennem listen, hvor du sammenligner to tilstødende elementer og bytter 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 passager (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 gennemgang 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, skal du bytte positionerne
Trin 4) Gentag trin 3 passerer, indtil du når det ydre pass (n - 1). Få det næste element på listen, gentag derefter processen, der blev udført i trin 3, indtil alle værdierne er 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 gennemgange, hvis listen eller tilstødende værdier allerede er sorteret. For eksempel, hvis den medfølgende liste allerede indeholder elementer, der er sorteret i stigende rækkefølge, kan vi bryde sløjfen tidligt.
Optimeret boblesorteringsalgoritme
Som standard sammenligner algoritmen for boblesortering i Python 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 iterationer 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 initieres, indtil processen er afsluttet som vist i nedenstående eksempel på boblesortering.
Optimering udføres ved hjælp af følgende trin
Trin 1) Opret en flagvariabel, der overvåger, om der er sket en swapping 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 position, skal du afslutte den indre sløjfe og fortsætte med den ydre sløjfe.
En optimeret boblesortering er mere effektiv, da den kun udfører de nødvendige trin og springer dem over, der ikke er påkrævet.
Visuel repræsentation
Med en liste over fem elementer illustrerer følgende billeder, hvordan boblesorteringen gentager sig gennem værdierne, når de sorteres
Det følgende billede viser den usorterede liste
Første gentagelse
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 positionen besat af 6, mens 6 indtager den position, der var besat af 21
Vores ændrede liste ser nu ud som den ovenfor.
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 foretages ingen bytte.
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 gentagelse
Den nye liste efter den anden iteration er som følger
Tredje gentagelse
Den nye liste efter den tredje iteration er som følger
Fjerde gentagelse
Den nye liste efter den fjerde iteration er som følger
Python eksempler
Den 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)
Udførelse af ovenstående boblesorteringsprogram i Python giver følgende resultater
[6, 9, 21, 3, 33]
Kode Forklaring
Forklaringen på Python Bubble Sort-programkoden er som følger
HER,
- Definerer en funktionsbobleSort, der accepterer en parameter theSeq. Koden udsender ikke noget.
- Får længden af arrayet og tildeler værdien til en variabel n. Koden udsender ikke noget
- Starter en for loop, der kører boble sorteringsalgoritmen (n - 1) gange. Dette er den ydre løkke. Koden udsender ikke noget
- Definerer en flagvariabel, der skal bruges til at bestemme, om en swap er sket eller ej. Dette er til optimeringsformål. 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 højre højre side. Koden udsender ikke noget.
- Tildeler værdien af theSeq [j] til en tidsmæssig variabel tmp, hvis betingelsen evalueres til sand. Koden udsender ikke noget
- Værdien af Seq [j + 1] tildeles positionen for Seq [j]. Koden udsender ikke noget
- Værdien af variablen tmp tildeles positionenSeq [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 det variable flag er 0. Koden udsender ikke noget
- Hvis værdien er 0, kalder vi break-sætningen, der træder ud af den indre sløjfe.
- Returnerer værdien af Seq efter at den er 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 funktionsboblen Sorter til et variabelt resultat.
- Udskriver værdien af det variable resultat.
Fordele ved boblesortering
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 sorteret
- Det kræver ikke omfattende hukommelse.
- Det er let at skrive koden til algoritmen
- Pladsbehovet er minimalt sammenlignet med andre sorteringsalgoritmer.
Boblesortering 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 applikation.
- Antallet af trin, der kræves for at sortere listen, er af rækkefølgen n 2
Kompleksitetsanalyse af boblesortering
Der er tre typer af kompleksitet er:
1) Sorter kompleksitet
Sorteringskompleksiteten bruges til at udtrykke mængden af udførelsestider og plads, det tager at sortere listen. Boblesorteringen gør (n - 1) iterationer for at sortere listen, hvor n er det samlede antal elementer på listen.
2) Tidskompleksitet
Tidskompleksiteten af boblesorteringen er O (n 2 )
Tidskompleksiteterne kan kategoriseres som:
- Værste tilfælde - det er her listen er i faldende rækkefølge. Algoritmen udfører det maksimale antal udførelser, der udtrykkes som [Big-O] O (n 2 )
- Bedste tilfælde - dette sker, når den angivne liste allerede er sorteret. Algoritmen udfører det mindste antal udførelser, der udtrykkes som [Big-Omega] Ω (n)
- Gennemsnitlig sag - dette sker, når listen er i tilfældig rækkefølge. Den gennemsnitlige kompleksitet er repræsenteret som [Big-theta] ⊝ (n 2 )
3) Rumkompleksitet
Rumkompleksiteten måler mængden af ekstra plads, der er nødvendig for at sortere listen. Boblesorteringen kræver kun en (1) ekstra plads til den tidsmæssige variabel, der bruges til at bytte værdier. Derfor har den 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 hvad du skal bruge er til sløjfer og hvis udsagn.
- Problemet, som boblesorteringsalgoritmen løser, er at tage en tilfældig liste over varer og gøre den til en ordnet liste.
- Boblesorteringsalgoritmen i datastruktur fungerer bedst, når listen allerede er sorteret, da den udfører et minimalt antal gentagelser.
- Boblesorteringsalgoritmen fungerer ikke godt, når listen er i omvendt rækkefølge.
- Boblersorteringen har en tidskompleksitet på O (n 2 ) og en rumkompleksitet på O (1)
- Bubbler-sorteringsalgoritmen er bedst egnet til akademiske formål og ikke til virkelige applikationer.
- Den optimerede boblesortering gør algoritmen mere effektiv ved at springe over unødvendige iterationer, når der kontrolleres værdier, der allerede er sorteret.