Bubble Sorteringsalgoritm med Python med hjälp av listexempel

Vad är en Bubble sortera?

Bubble Sortera ä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 inget byte.

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

I detta Bubble Sortera in Python handledning du kommer att lära dig:

Genomförande av Bubble Sorteringsalgoritm

Vi kommer att dela 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 föremål ges i slumpmässig ordning, och vi skulle vilja ordna föremålen på ett ordnat sätt

Tänk på följande lista:

[21,6,9,33,3]

Lösningen

Iterera genom listan och jämför två intilliggande element och byt ut dem om det första värdet är högre än det andra värdet.

Resultatet ska bli som följer:

[3,6,9,21,33]

Algoritm

Bubbelsorteringsalgoritmen fungerar enligt följande

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

Steg 2) Bestäm antalet yttre pass (n – 1) som ska göras. Dess längd är lista minus ett

Steg 3) Utför inre pass (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 byter du positionerna

Steg 4) Upprepa steg 3 omgångar tills du når det yttre passet (n – 1). Hämta nästa element i listan och upprepa sedan processen som utfördes i steg 3 tills alla värden har placerats i korrekt stigande ordning.

Steg 5) Returnera resultatet när alla pass är gjorda. Returnera resultatet av den sorterade listan

Steg 6) Optimera algoritm

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

optimerad Bubble Sorteringsalgoritm

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

Att optimera bubbelsorteringen 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 ingen anledning att iterera genom resten av värdena. Iterationen avslutas och nästa initieras tills processen är slutförd som visas i nedan Bubble Sorteringsexempel.

Optimering görs med hjälp av följande steg

Steg 1) Skapa en flaggvariabel som övervakar om något utbyte har skett i den inre slingan

Steg 2) Om värdena har bytt positioner, fortsätt 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 bubbelsortering är mer effektiv eftersom den bara utför de nödvändiga stegen och hoppar över de som inte krävs.

Visuell representation

Med en lista med fem element illustrerar följande bilder hur bubblans sortering itererar genom 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 som upptas av 6 medan 6 tar positionen som upptas 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 ut 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å inget 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 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 iterationen

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

Python Exempel

Följande kod visar hur man implementerar Bubble Sortera algoritm i 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)

Kör ovanstående bubblesorteringsprogram i Python ger följande resultat

[6, 9, 21, 3, 33]

Kodförklaring

Förklaringen till Python Bubble Sorteringsprogramkoden är som följer

HÄR,

Definierar en funktion bubbleSort som accepterar en parameter theSeq. Koden matar inte ut någonting.
Hämtar längden på matrisen och tilldelar värdet till en variabel n. Koden matar inte ut någonting
Startar en for-loop som kör bubbelsorteringsalgoritmen (n – 1) gånger. Detta är den yttre slingan. Koden matar inte ut någonting
Definierar en flaggvariabel som kommer att användas för att avgöra om ett byte har skett eller inte. Detta är i optimeringssyfte. Koden matar inte ut någonting
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ågonting.
Använder if-satsen för att kontrollera om värdet på vänster sida är större än det på omedelbart högra sidan. Koden matar inte ut någonting.
Tilldelar värdet för theSeq[j] till en tidsvariabel tmp om villkoret utvärderas till sant. Koden matar inte ut någonting
Värdet på Seq[j + 1] tilldelas positionen för Seq[j]. Koden matar inte ut någonting
Värdet på variabeln tmp tilldelas positionen Seq[j + 1]. Koden matar inte ut någonting
Flaggvariabeln tilldelas värdet 1 för att indikera att ett byte har skett. Koden matar inte ut någonting
Använder en if-sats för att kontrollera om värdet på variabelflaggan är 0. Koden matar inte ut någonting
Om värdet är 0, anropar vi break-satsen som kliver ut ur den inre slingan.
Returnerar värdet för theSeq efter att det har sorterats. Koden matar ut den sorterade listan.
Definierar en variabel el som innehåller en lista med slumptal. Koden matar inte ut någonting.
Tilldelar värdet för funktionen bubbleSort till ett variabelt resultat.
Skriver ut värdet på variabelresultatet.

Bubble sorts fördelar

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

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

Bubble sort Nackdelar

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

Det fungerar inte bra när man 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²

Komplexitetsanalys av Bubble Sortera

Det finns tre typer av komplexitet:

1) Sortera komplexitet

Sorteringskomplexiteten används för att uttrycka mängden körningstider och utrymme som det tar 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 bubbelsorteringen är O(n²)

Tidskomplexiteten kan kategoriseras som:

Värsta fall – det är här listan som tillhandahålls är i fallande ordning. Algoritmen utför det maximala antalet exekveringar som uttrycks som [Big-O] O(n)²)
Bästa fall – detta inträffar när den tillhandahållna listan redan är sorterad. Algoritmen utför det minsta antalet exekveringar 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²)

3) Rymdens komplexitet

Utrymmeskomplexiteten mäter mängden extra utrymme som behövs för att sortera listan. Bubbelsorteringen kräver bara ett (1) extra utrymme för den tidsvariabel som används för att byta värden. Därför har den en rymdkomplexitet av O (1).

Sammanfattning

Bubbelsorteringsalgoritmen fungerar genom att jämföra två intilliggande värden och byta ut dem om värdet till vänster är mindre än värdet till höger.
Att implementera en bubbelsorteringsalgoritm är relativt okomplicerat med Python. Allt du behöver använda är för loopar och if-satser.
Problemet som bubbelsorteringsalgoritmen löser är att ta en slumpmässig lista med objekt och förvandla 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.
Bubbelsorteringsalgoritmen fungerar inte bra när listan är i omvänd ordning.
Bubblarsorteringen har en tidskomplexitet på O (n²) och en rymdkomplexitet av O (1)
Bubbelsorteringsalgoritmen är bäst lämpad för akademiska ändamål och inte verkliga tillämpningar.
Den optimerade bubbelsorteringen gör algoritmen mer effektiv genom att hoppa över onödiga iterationer när man kontrollerar värden som redan har sorterats.

Du kanske gillar: