Bubble Sorteeralgoritme met Python met behulp van Lijstvoorbeeld

Wat is een Bubble Sorteren?

Bubble Sorteren is een sorteeralgoritme dat wordt gebruikt om lijstitems in oplopende volgorde te sorteren door twee aangrenzende waarden te vergelijken. Als de eerste waarde hoger is dan de tweede waarde, neemt de eerste waarde de tweede waardepositie in, terwijl de tweede waarde de eerste waardepositie inneemt. Als de eerste waarde lager is dan de tweede waarde, wordt er niet geruild.

Dit proces wordt herhaald totdat alle waarden in een lijst zijn vergeleken en indien nodig zijn verwisseld. Elke iteratie wordt gewoonlijk een pass genoemd. Het aantal passages bij het sorteren van bellen is gelijk aan het aantal elementen in een lijst minus één.

In deze Bubble Sorteren Python zelfstudie je leert:

Implementatie van het Bubble Sorteeralgoritme

We zullen de implementatie opsplitsen in drie (3) stappen, namelijk het probleem, de oplossing en het algoritme dat we kunnen gebruiken om code voor elke taal te schrijven.

Het probleem

Een lijst met artikelen wordt in willekeurige volgorde gegeven en wij willen de artikelen graag overzichtelijk ordenen

Beschouw de volgende lijst:

[21,6,9,33,3]

De oplossing

Doorloop de lijst door twee aangrenzende elementen te vergelijken en ze om te wisselen als de eerste waarde hoger is dan de tweede waarde.

Het resultaat zou als volgt moeten zijn:

[3,6,9,21,33]

Algoritme

Het bellensorteeralgoritme werkt als volgt

Stap 1) Verkrijg het totale aantal elementen. Haal het totale aantal items in de gegeven lijst op

Stap 2) Bepaal het aantal uit te voeren buitenste passages (n – 1). De lengte is lijst minus één

Stap 3) Voer binnendoorgangen (n – 1) keer uit voor buitendoorgang 1. Haal de eerste elementwaarde op en vergelijk deze met de tweede waarde. Als de tweede waarde kleiner is dan de eerste waarde, wissel dan de posities om

Stap 4) Herhaal stap 3 tot u de buitenste pas bereikt (n – 1). Haal het volgende element uit de lijst en herhaal vervolgens het proces dat in stap 3 is uitgevoerd totdat alle waarden in de juiste oplopende volgorde zijn geplaatst.

Stap 5) Retourneer het resultaat wanneer alle passen zijn uitgevoerd. Retourneer de resultaten van de gesorteerde lijst

Stap 6) Optimaliseer algoritme

Vermijd onnodige interne passen als de lijst of aangrenzende waarden al zijn gesorteerd. Als de verstrekte lijst bijvoorbeeld al elementen bevat die in oplopende volgorde zijn gesorteerd, kunnen we de lus vroegtijdig doorbreken.

Geoptimaliseerde Bubble Sorteeralgoritme

Standaard is het algoritme voor het sorteren van bubbels in Python vergelijkt alle items in de lijst, ongeacht of de lijst al is gesorteerd of niet. Als de gegeven lijst al is gesorteerd, is het vergelijken van alle waarden een verspilling van tijd en middelen.

Door het sorteren van de bellen te optimaliseren, kunnen we onnodige iteraties voorkomen en tijd en middelen besparen.

Als de eerste en tweede items bijvoorbeeld al zijn gesorteerd, hoeft u de rest van de waarden niet te herhalen. De iteratie wordt beëindigd en de volgende wordt gestart totdat het proces is voltooid, zoals hieronder wordt weergegeven Bubble Sorteervoorbeeld.

Optimalisatie wordt uitgevoerd met behulp van de volgende stappen

Stap 1) Maak een vlagvariabele die controleert of er in de binnenste lus is gewisseld

Stap 2) Als de waarden van positie zijn gewisseld, gaat u verder met de volgende iteratie

Stap 3) Als de voordelen niet van positie zijn gewisseld, beëindig dan de binnenste lus en ga verder met de buitenste lus.

Een geoptimaliseerde bellensortering is efficiënter omdat alleen de noodzakelijke stappen worden uitgevoerd en de niet-verplichte stappen worden overgeslagen.

Visuele weergave

Gegeven een lijst met vijf elementen, illustreren de volgende afbeeldingen hoe de bubble sort door de waarden itereert bij het sorteren ervan

De volgende afbeelding toont de ongesorteerde lijst

Eerste iteratie

Stap 1)

De waarden 21 en 6 worden vergeleken om te controleren welke groter is dan de andere.

21 is groter dan 6, dus 21 neemt de positie in die wordt ingenomen door 6, terwijl 6 de positie inneemt die werd ingenomen door 21

Onze aangepaste lijst ziet er nu uit zoals hierboven.

Stap 2)

De waarden 21 en 9 worden vergeleken.

21 is groter dan 9, dus we wisselen de posities van 21 en 9 om

De nieuwe lijst is nu zoals hierboven

Stap 3)

De waarden 21 en 33 worden vergeleken om de grootste te vinden.

De waarde 33 is groter dan 21, er vindt dus geen verwisseling plaats.

Stap 4)

De waarden 33 en 3 worden vergeleken om de grootste te vinden.

De waarde 33 is groter dan 3, dus we wisselen hun posities.

De gesorteerde lijst aan het einde van de eerste iteratie is zoals hierboven

Tweede Iteratie

De nieuwe lijst na de tweede iteratie is als volgt

Derde iteratie

De nieuwe lijst na de derde iteratie is als volgt

Vierde iteratie

De nieuwe lijst na de vierde iteratie is als volgt

Python Voorbeelden

De volgende code laat zien hoe u het Bubble Sorteeralgoritme in 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)

Het bovenstaande bubble sort-programma uitvoeren in Python levert de volgende resultaten op

[6, 9, 21, 3, 33]

Code Uitleg

De verklaring voor de Python Bubble Sorteer programmacode is als volgt

HIER,

Definieert een functie bubbleSort die een parameter theSeq accepteert. De code levert niets op.
Haalt de lengte van de array op en wijst de waarde toe aan een variabele n. De code levert niets op
Start een for-lus die het bellensorteeralgoritme (n – 1) keer uitvoert. Dit is de buitenste lus. De code levert niets op
Definieert een vlagvariabele die wordt gebruikt om te bepalen of er al dan niet een swap heeft plaatsgevonden. Dit is voor optimalisatiedoeleinden. De code levert niets op
Start de binnenste lus die alle waarden in de lijst vergelijkt van de eerste tot de laatste. De code geeft niets weer.
Gebruikt de if-instructie om te controleren of de waarde aan de linkerkant groter is dan die aan de directe rechterkant. De code levert niets op.
Wijst de waarde van theSeq[j] toe aan een tijdelijke variabele tmp als de voorwaarde resulteert in waar. De code levert niets op
De waarde van theSeq[j + 1] wordt toegewezen aan de positie van theSeq[j]. De code levert niets op
De waarde van de variabele tmp wordt toegewezen aan positie theSeq[j + 1]. De code levert niets op
Aan de vlagvariabele wordt de waarde 1 toegekend om aan te geven dat er een ruil heeft plaatsgevonden. De code levert niets op
Gebruikt een if-instructie om te controleren of de waarde van de variabelevlag 0 is. De code levert niets op
Als de waarde 0 is, noemen we de break-instructie die uit de binnenste lus stapt.
Retourneert de waarde van theSeq nadat deze is gesorteerd. De code voert de gesorteerde lijst uit.
Definieert een variabele el die een lijst met willekeurige getallen bevat. De code geeft niets uit.
Wijst de waarde van de functie bubbleSort toe aan een variabel resultaat.
Drukt de waarde van het variabele resultaat af.

Bubble soort voordelen

Hieronder staan enkele voordelen van het bubble sort-algoritme

Het is gemakkelijk te begrijpen
Het presteert erg goed als de lijst al of bijna gesorteerd is
Er is geen uitgebreid geheugen voor nodig.
Het is gemakkelijk om de code voor het algoritme te schrijven
De ruimtevereisten zijn minimaal vergeleken met andere sorteeralgoritmen.

Bubble soort Nadelen

Hieronder staan enkele nadelen van het bubble sort-algoritme

Het presteert niet goed bij het sorteren van grote lijsten. Het kost te veel tijd en middelen.
Het wordt meestal gebruikt voor academische doeleinden en niet voor toepassingen in de echte wereld.
Het aantal stappen dat nodig is om de lijst te sorteren is van de orde n²

Complexiteitsanalyse van Bubble Sorteren

Er zijn drie soorten complexiteit:

1) Complexiteit sorteren

De sortcomplexiteit wordt gebruikt om de hoeveelheid uitvoeringstijden en ruimte uit te drukken die nodig is om de lijst te sorteren. De bubble sort maakt (n – 1) iteraties om de lijst te sorteren, waarbij n het totale aantal elementen in de lijst is.

2) Tijdcomplexiteit

De tijdcomplexiteit van de bubble sort is O(n²)

De tijdcomplexiteiten kunnen als volgt worden gecategoriseerd:

Het slechtste geval – hier staat de weergegeven lijst in aflopende volgorde. Het algoritme voert het maximale aantal uitvoeringen uit, uitgedrukt als [Big-O] O(n²)
Beste geval – dit gebeurt wanneer de opgegeven lijst al is gesorteerd. Het algoritme voert het minimale aantal uitvoeringen uit, wat wordt uitgedrukt als [Big-Omega] Ω(n)
gemiddeld geval – dit gebeurt wanneer de lijst in willekeurige volgorde staat. De gemiddelde complexiteit wordt weergegeven als [Big-theta] ⊝(n²)

3) Ruimtelijke complexiteit

De ruimtecomplexiteit meet de hoeveelheid extra ruimte die nodig is om de lijst te sorteren. De bubble sort vereist slechts één (1) extra ruimte voor de temporele variabele die wordt gebruikt voor het verwisselen van waarden. Daarom heeft het een ruimtecomplexiteit van O (1).

Samenvatting

Het algoritme voor het sorteren van bellen werkt door twee aangrenzende waarden te vergelijken en deze om te wisselen als de waarde aan de linkerkant kleiner is dan de waarde aan de rechterkant.
Het implementeren van een bubble sort-algoritme is relatief eenvoudig met Python. Het enige dat u hoeft te gebruiken zijn for-lussen en if-instructies.
Het probleem dat het algoritme voor het sorteren van bellen oplost, is het nemen van een willekeurige lijst met items en deze omzetten in een geordende lijst.
Het bellensorteeralgoritme in de gegevensstructuur presteert het beste wanneer de lijst al is gesorteerd, aangezien het een minimaal aantal iteraties uitvoert.
Het bellensorteeralgoritme werkt niet goed als de lijst in omgekeerde volgorde staat.
De bubbler-sortering heeft een tijdcomplexiteit van O (n²) en een ruimtecomplexiteit van O (1)
Het bubbler-sorteeralgoritme is het meest geschikt voor academische doeleinden en niet voor toepassingen in de echte wereld.
De geoptimaliseerde bellensortering maakt het algoritme efficiënter door onnodige iteraties over te slaan bij het controleren van waarden die al zijn gesorteerd.

Je houdt misschien van: