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ärdets position, medan det andra värdet tar det första värdets position. Om det första värdet är lägre än det andra värdet sker ingen växling.ping är klart.

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 problemet den löser, dess optimerade form, en steg-för-steg visuell genomgång, en fungerande Python programmet och dess prestandaegenskaper.

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 artiklar ges i slumpmässig ordning, och vi vill gärna ordna dem på ett ordnat sätt.

Tänk på följande lista:

[21, 6, 9, 33, 3]

Lösningen

Iterera genom listan, jämför två intilliggande element och bytping 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) Hämta det totala antalet element. Hämta det totala antalet objekt i den givna listan.

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

Steg 3) Utför inre övergångar (n – 1) gånger för yttre övergång 1. Hämta 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 position.

Steg 4) Upprepa steg 3-passage 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 rätt stigande ordning.

Steg 5) Returnera resultatet när alla drag är avklarade. Returnera resultaten från den sorterade listan.

Steg 6) Optimera algoritmen.

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 det finns några swapsping har inträffat i den inre slingan.

Steg 2) Om värdena har bytt position, fortsätt till nästa iteration.

Steg 3) Om värdena inte har bytt plats, avsluta den inre loopen och fortsätt med den yttre loopen.

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 bubbelsorteringen itererar genom värdena vid sortering.

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 intar den position som upptogs av 6 medan 6 intar den position som upptogs 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 plats på 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 växlingping 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 följande:

Tredje iterationen

Den nya listan efter den tredje iterationen är följande:

Fjärde iterationen

Den nya listan efter den fjärde iterationen är följande:

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:

[3, 6, 9, 21, 33]

Code Förklaring

Förklaringen till Python Bubble Sorteringsprogrammets kod är som följer:

HÄR,

1. Definierar en funktion bubbleSort som accepterar en parameter theSeq. Koden matar inte ut någonting.
2. Hämtar längden på arrayen och tilldelar värdet till en variabel n. Koden matar inte ut någonting.
3. Startar en for-loop som kör bubbelsorteringsalgoritmen (n – 1) gånger. Detta är den yttre loopen. 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 i optimeringssyfte. 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ågonting.
6. 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.
7. Tilldelar värdet för theSeq[j] till en temporal variabel tmp om villkoret utvärderas till sant. Koden matar inte ut något.
8. Värdet för theSeq[j + 1] tilldelas positionen för theSeq[j]. Koden matar inte ut någonting.
9. Värdet på variabeln tmp tilldelas positionen theSeq[j + 1]. Koden matar inte ut någonting.
10. Flaggvariabeln tilldelas värdet 1 för att indikera att ett byte har ägt rum. Koden matar inte ut någonting.
11. Använder ett if-uttryck för att kontrollera om värdet på variabelflaggan är 0. Koden matar inte ut någonting.
12. Om värdet är 0, anropar vi break-satsen som kliver ut ur den inre slingan.
13. Returnerar värdet för 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ågonting.
15. Tilldelar värdet för funktionen bubbleSort till ett variabelt resultat.
16. 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å.
• Den fungerar mycket bra när listan redan är eller nästan är sorterad.
• Det kräver inte omfattande minne.
• Det är enkelt att skriva kod 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 mestadels för akademiska ändamål och inte för verkliga tillämpningar.
• 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 den mängd exekveringstid och 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 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 angivna listan redan är sorterad. Algoritmen utför det minsta antalet körningar vilket 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 mellanslag för den temporala variabel som används för swap.ping värden. Därför har den en rumskomplexitet på O(1).

Vanliga frågor