Bubble Sorteeralgoritme met Python met behulp van Lijstvoorbeeld

Wat is een Bubble Sorteren?

Bubble Sorteren Dit is een sorteeralgoritme dat wordt gebruikt om lijstitems in oplopende volgorde te sorteren door twee aangrenzende waarden te vergelijken. Als de eerste waarde groter is dan de tweede waarde, neemt de eerste waarde de positie van de tweede waarde in, terwijl de tweede waarde de positie van de eerste waarde inneemt. Als de eerste waarde kleiner is dan de tweede waarde, vindt er geen verwisseling plaats.ping is klaar.

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 welk probleem het oplost, de geoptimaliseerde vorm ervan, een stapsgewijze visuele uitleg en een werkend voorbeeld. Python programma en de bijbehorende prestatiekenmerken.

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 te schrijven voor elke programmeertaal.

Het probleem

Een lijst met items is in willekeurige volgorde gegeven en we willen deze items in een ordelijke volgorde plaatsen.

Beschouw de volgende lijst:

[21, 6, 9, 33, 3]

De oplossing

Doorloop de lijst, vergelijk twee aangrenzende elementen en verwissel ze.ping dat geldt als de eerste waarde hoger is dan de tweede waarde.

Het resultaat zou als volgt moeten zijn:

[3, 6, 9, 21, 33]

Algoritme

Het bubble sort-algoritme werkt als volgt:

Stap 1) Bepaal het totale aantal elementen. Bepaal het totale aantal items in de gegeven lijst.

Stap 2) Bepaal het aantal buitenste passes (n – 1) dat moet worden uitgevoerd. De lengte ervan is de lijst min één.

Stap 3) Voer de binnenste doorgang (n – 1) keer uit voor de eerste buitenste doorgang. Neem de waarde van het eerste element en vergelijk deze met de waarde van het tweede element. Als de tweede waarde kleiner is dan de eerste waarde, verwissel dan de posities.

Stap 4) Herhaal stap 3 totdat je de buitenste doorgang 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) Geef het resultaat terug zodra alle rondes zijn voltooid. Geef de resultaten van de gesorteerde lijst terug.

Stap 6) Optimaliseer het 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 vindt plaats aan de hand van de volgende stappen:

Stap 1) Maak een vlagvariabele aan die controleert of er sprake is van swap.ping is opgetreden in de binnenste lus.

Stap 2) Als de waarden van positie zijn verwisseld, ga dan verder naar de volgende iteratie.

Stap 3) Als de waarden niet van positie zijn verwisseld, 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 heen loopt tijdens het sorteren.

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 plaats in van 6 en 6 neemt de plaats in van 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 ziet er nu als volgt uit.

Stap 3)

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

De waarde 33 is groter dan 21, dus ruilen is niet mogelijk.ping plaatsvindt.

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 ziet eruit zoals hierboven.

Tweede Iteratie

De nieuwe lijst na de tweede iteratie ziet er als volgt uit:

Derde iteratie

De nieuwe lijst na de derde iteratie ziet er als volgt uit:

Vierde iteratie

De nieuwe lijst na de vierde iteratie ziet er als volgt uit:

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 Dit levert de volgende resultaten op:

[3, 6, 9, 21, 33]

Code Uitleg

De verklaring voor de Python BubblDe sorteerprogrammacode is als volgt:

HIER,

1. Definieert een functie bubbleSort die een parameter theSeq accepteert. De code levert niets op.
2. De code berekent de lengte van de array en kent de waarde toe aan een variabele n. De code geeft geen uitvoer.
3. Start een for-lus die het bubble sort-algoritme (n – 1) keer uitvoert. Dit is de buitenste lus. De code geeft geen uitvoer.
4. Definieert een vlagvariabele die gebruikt wordt om te bepalen of er een swap heeft plaatsgevonden. Dit is voor optimalisatiedoeleinden. De code geeft geen uitvoer.
5. Start de binnenste lus die alle waarden in de lijst vergelijkt van de eerste tot de laatste. De code geeft niets weer.
6. 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.
7. Kent de waarde van theSeq[j] toe aan een tijdelijke variabele tmp als de voorwaarde waar is. De code geeft geen uitvoer.
8. De waarde van theSeq[j + 1] wordt toegewezen aan de positie van theSeq[j]. De code geeft geen uitvoer.
9. De waarde van de variabele tmp wordt toegewezen aan positie theSeq[j + 1]. De code geeft geen uitvoer.
10. Aan de vlagvariabele wordt de waarde 1 toegekend om aan te geven dat er een ruil heeft plaatsgevonden. De code geeft geen uitvoer.
11. Er wordt een if-statement gebruikt om te controleren of de waarde van de variabele flag 0 is. De code geeft geen uitvoer.
12. Als de waarde 0 is, noemen we de break-instructie die uit de binnenste lus stapt.
13. Retourneert de waarde van theSeq nadat deze is gesorteerd. De code voert de gesorteerde lijst uit.
14. Definieert een variabele el die een lijst met willekeurige getallen bevat. De code geeft niets uit.
15. Wijst de waarde van de functie bubbleSort toe aan een variabel resultaat.
16. Drukt de waarde van het variabele resultaat af.

Bubble soort voordelen

Hieronder volgen enkele voordelen van het bubble sort-algoritme:

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

Bubble soort Nadelen

Hieronder volgen 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 voornamelijk gebruikt voor academische doeleinden en niet voor toepassingen in de praktijk.
• 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 sorteercomplexiteit geeft aan hoeveel uitvoeringstijd en geheugenruimte het kost om een ​​lijst te sorteren. De bubble sort voert (n – 1) iteraties uit 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 aangeleverde lijst al gesorteerd is. Het algoritme voert het minimale aantal uitvoeringen uit, 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 tijdelijke variabele die gebruikt wordt voor de swap.ping waarden. Daarom heeft het een ruimtecomplexiteit van O(1).

Veelgestelde vragen