Bubblesorteringsalgoritm med Python med hjälp av listexempel

Innehållsförteckning:

Anonim

Vad är en bubbelsortering?

Bubblesortering är en sorteringsalgoritm som används för att sortera listobjekt i stigande ordning genom att jämföra två intilliggande värden. Om det första värdet är högre än det andra värdet, tar det första värdet den andra värdepositionen, medan det andra värdet tar den första värdepositionen. Om det första värdet är lägre än det andra värdet görs ingen byte.

Denna process upprepas tills alla värden i en lista har jämförts och byts vid behov. Varje iteration kallas vanligtvis ett pass. Antalet passeringar i en bubblasortering är lika med antalet element i en lista minus en.

I denna Bubble Sorting in Python-handledning lär du dig:

  • Vad är en bubbelsortering?
  • Implementering av bubblasorteringsalgoritmen
  • Optimerad algoritm för bubblasortering
  • Visuell representation
  • Python-exempel
  • Kodförklaring
  • Fördelar med bubblasortering
  • Bubblesortering Nackdelar
  • Komplexitetsanalys av bubblasortering

Implementering av bubblasorteringsalgoritmen

Vi delar upp implementeringen i tre (3) steg, nämligen problemet, lösningen och algoritmen som vi kan använda för att skriva kod för vilket språk som helst.

Problemet

En lista med artiklar ges i slumpmässig ordning, och vi vill ordna artiklarna på ett ordnat sätt

Tänk på följande lista:

[21,6,9,33,3]

Lösningen

Iterera genom listan där du jämför två angränsande element och byter dem om det första värdet är högre än det andra värdet.

Resultatet bör vara som följer:

[3,6,9,21,33]

Algoritm

Bubblasorteringsalgoritmen fungerar enligt följande

Steg 1) Få det totala antalet element. Få det totala antalet artiklar i listan

Steg 2) Bestäm antalet yttre passager (n - 1) som ska göras. Dess längd är lista minus en

Steg 3) Utför innerpass (n - 1) gånger för yttre pass 1. Få det första elementvärdet och jämför det med det andra värdet. Om det andra värdet är mindre än det första värdet, byt sedan positionerna

Steg 4) Upprepa steg 3 passerar tills du når det yttre passet (n - 1). Skaffa nästa element i listan och upprepa sedan processen som utfördes i steg 3 tills alla värden har placerats i rätt stigande ordning.

Steg 5) Returnera resultatet när alla pass har gjorts. Returnera resultaten från den sorterade listan

Steg 6) Optimera algoritmen

Undvik onödiga inre passeringar om listan eller intilliggande värden redan är sorterade. Till exempel, om den angivna listan redan innehåller element som har sorterats i stigande ordning, kan vi bryta slingan tidigt.

Optimerad algoritm för bubblasortering

Som standard jämför algoritmen för bubblasortering i Python alla objekt i listan oavsett om listan redan är sorterad eller inte. Om den angivna listan redan är sorterad är det ett slöseri med tid och resurser att jämföra alla värden.

Optimering av bubblasorteringen hjälper oss att undvika onödiga iterationer och spara tid och resurser.

Till exempel, om de första och andra objekten redan är sorterade, finns det inget behov av att itera igenom resten av värdena. Iterationen avslutas och nästa initieras tills processen är klar som visas i nedanstående Bubble Sort-exempel.

Optimering görs med följande steg

Steg 1) Skapa en flaggvariabel som övervakar om någon byte har inträffat i den inre slingan

Steg 2) Om värdena har bytt position fortsätter du till nästa iteration

Steg 3) Om fördelarna inte har bytt position, avsluta den inre slingan och fortsätt med den yttre slingan.

En optimerad bubblasortering är effektivare eftersom den bara utför nödvändiga steg och hoppar över de som inte behövs.

Visuell representation

Med en lista med fem element illustrerar följande bilder hur bubblasorteringen går igenom värdena när de sorteras

Följande bild visar den osorterade listan

Första Iterationen

Steg 1)

Värdena 21 och 6 jämförs för att kontrollera vilken som är större än den andra.

21 är större än 6, så 21 tar positionen ockuperad av 6 medan 6 tar positionen som ockuperades av 21

Vår modifierade lista ser nu ut som den ovan.

Steg 2)

Värdena 21 och 9 jämförs.

21 är större än 9, så vi byter positionerna 21 och 9

Den nya listan är nu som ovan

Steg 3)

Värdena 21 och 33 jämförs för att hitta det större.

Värdet 33 är större än 21, så ingen byte sker.

Steg 4)

Värdena 33 och 3 jämförs för att hitta det större.

Värdet 33 är större än 3, så vi byter ut deras positioner.

Den sorterade listan i slutet av den första iterationen är som den ovan

Andra iterationen

Den nya listan efter den andra iterationen är som följer

Tredje Iterationen

Den nya listan efter den tredje iterationen är som följer

Fjärde itterationen

Den nya listan efter den fjärde iterationen är som följer

Python-exempel

Följande kod visar hur du implementerar 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)

Att utföra ovanstående bubblasorteringsprogram i Python ger följande resultat

[6, 9, 21, 3, 33]

Kodförklaring

Förklaringen till programkoden för Python Bubble Sort är följande

HÄR,

  1. Definierar en funktionsbubbelsort som accepterar en parameter theSeq. Koden matar inte ut något.
  2. Får längden på arrayen och tilldelar värdet till en variabel n. Koden matar inte ut något
  3. Startar en for-loop som kör bubblasorteringsalgoritmen (n - 1) gånger. Detta är den yttre slingan. Koden matar inte ut något
  4. Definierar en flaggvariabel som ska användas för att avgöra om ett byte har inträffat eller inte. Detta är för optimeringsändamål. Koden matar inte ut något
  5. Startar den inre slingan som jämför alla värden i listan från den första till den sista. Koden matar inte ut något.
  6. Använder if-uttalandet för att kontrollera om värdet på vänster sida är större än värdet på den omedelbara högra sidan. Koden matar inte ut något.
  7. Tilldelar värdet av SeS [j] till en tidsvariabel tmp om villkoret utvärderas till sant. Koden matar inte ut något
  8. Värdet på Seq [j + 1] tilldelas positionen för Seq [j]. Koden matar inte ut något
  9. Värdet på variabeln tmp tilldelas positionenSeq [j + 1]. Koden matar inte ut något
  10. Flaggvariabeln tilldelas värdet 1 för att indikera att ett byte har ägt rum. Koden matar inte ut något
  11. Använder ett if-uttalande för att kontrollera om värdet på variabelflaggan är 0. Koden matar inte ut något
  12. Om värdet är 0 kallar vi brytuttrycket som går ut ur den inre slingan.
  13. Returnerar värdet på theSeq efter att det har sorterats. Koden matar ut den sorterade listan.
  14. Definierar en variabel el som innehåller en lista med slumptal. Koden matar inte ut något.
  15. Tilldelar värdet på funktionsbubblan till ett variabelt resultat.
  16. Skriver ut värdet på det variabla resultatet.

Fördelar med bubblasortering

Följande är några av fördelarna med bubblasorteringsalgoritmen

  • Det är lätt att förstå
  • Det fungerar mycket bra när listan redan är eller nästan sorterad
  • Det kräver inte omfattande minne.
  • Det är enkelt att skriva koden för algoritmen
  • Utrymmeskraven är minimala jämfört med andra sorteringsalgoritmer.

Bubblesortering Nackdelar

Följande är några av nackdelarna med bubblasorteringsalgoritmen

  • Det fungerar inte bra när du sorterar stora listor. Det tar för mycket tid och resurser.
  • Det används mest för akademiska ändamål och inte för den verkliga applikationen.
  • Antalet steg som krävs för att sortera listan är av ordningen n 2

Komplexitetsanalys av bubblasortering

Det finns tre typer av komplexitet:

1) Sortera komplexitet

Sorteringskomplexiteten används för att uttrycka mängden exekveringstider och det utrymme som krävs för att sortera listan. Bubbelsorteringen gör (n - 1) iterationer för att sortera listan där n är det totala antalet element i listan.

2) Tidskomplexitet

Tidskomplexiteten för bubblasorteringen är O (n 2 )

Tidskomplexiteten kan kategoriseras som:

  • Värsta fall - det är här listan i fallande ordning. Algoritmen utför det maximala antalet körningar som uttrycks som [Big-O] O (n 2 )
  • I bästa fall - detta inträffar när den angivna listan redan är sorterad. Algoritmen utför det minsta antalet körningar som uttrycks som [Big-Omega] Ω (n)
  • Genomsnittligt fall - detta inträffar när listan är i slumpmässig ordning. Den genomsnittliga komplexiteten representeras som [Big-theta] ⊝ (n 2 )

3) Rymdkomplexitet

Utrymmets komplexitet mäter mängden extra utrymme som behövs för att sortera listan. Bubblasorteringen kräver endast ett (1) extra utrymme för den tidsmässiga variabeln som används för att byta värden. Därför har den en rymdkomplexitet av O (1).

Sammanfattning

  • Bubblasorteringsalgoritmen fungerar genom att jämföra två intilliggande värden och byta dem om värdet till vänster är mindre än värdet till höger.
  • Implementering av en bubblasorteringsalgoritm är relativt rakt fram med Python. Allt du behöver använda är för loopar och if-uttalanden.
  • Problemet som bubblasorteringsalgoritmen löser är att ta en slumpmässig lista med artiklar och göra den till en ordnad lista.
  • Bubbelsorteringsalgoritmen i datastrukturen fungerar bäst när listan redan är sorterad eftersom den utför ett minimalt antal iterationer.
  • Bubblasorteringsalgoritmen fungerar inte bra när listan är i omvänd ordning.
  • Bubblersorten har en tidskomplexitet av O (n 2 ) och en rymdkomplexitet av O (1)
  • Bubblersorteringsalgoritmen passar bäst för akademiska ändamål och inte för verkliga applikationer.
  • Den optimerade bubblasorteringen gör algoritmen effektivare genom att hoppa över onödiga iterationer vid kontroll av värden som redan har sorterats.