Bubbelsorteeralgoritme met Python met behulp van een lijstvoorbeeld

Wat is een bubbelsortering?

Bubble Sort 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 omgewisseld.

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 in een belsortering is gelijk aan het aantal elementen in een lijst min één.

In deze zelfstudie over het sorteren van bellen in Python leert u:

• Wat is een bubbelsortering?
• Implementatie van het Bubble Sort-algoritme
• Geoptimaliseerd Bubble Sort-algoritme
• Visuele representatie
• Python-voorbeelden
• Code Verklaring
• Bubble sort voordelen
• Bubble sort Nadelen
• Complexiteitsanalyse van bellen sorteren

Implementatie van het Bubble Sort-algoritme

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 items wordt in willekeurige volgorde gegeven en we willen de items op een ordelijke manier rangschikken

Beschouw de volgende lijst:

[21,6,9,33,3]

De oplossing

Herhaal de lijst door twee aangrenzende elementen te vergelijken en ze te verwisselen als de eerste waarde hoger is dan de tweede waarde.

Het resultaat zou als volgt moeten zijn:

[3,6,9,21,33]

Algoritme

Het algoritme voor het sorteren van bellen werkt als volgt

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

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

Stap 3) Voer binnenste passages (n - 1) keer uit voor buitenste pass 1. Verkrijg de eerste elementwaarde 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 passen totdat u de buitenste pas bereikt (n - 1). Haal het volgende element in de lijst op en herhaal het proces dat werd uitgevoerd in stap 3 totdat alle waarden in de juiste oplopende volgorde zijn geplaatst.

Stap 5) Retourneer het resultaat als alle passen zijn voltooid. Retourneer de resultaten van de gesorteerde lijst

Stap 6) Optimaliseer het algoritme

Vermijd onnodige binnenste doorgangen 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.

Geoptimaliseerd Bubble Sort-algoritme

Standaard vergelijkt het algoritme voor het sorteren van bellen in Python 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 de bubbelsoort te optimaliseren, kunnen we onnodige herhalingen vermijden en tijd en middelen besparen.

Als de eerste en tweede items bijvoorbeeld al zijn gesorteerd, is het niet nodig om de rest van de waarden te herhalen. De iteratie wordt beëindigd en de volgende wordt gestart totdat het proces is voltooid, zoals weergegeven in het onderstaande Bubble Sort-voorbeeld.

Optimalisatie gebeurt 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 verwisseld, gaat u verder met de volgende iteratie

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

Een geoptimaliseerde belsortering is efficiënter omdat het alleen de noodzakelijke stappen uitvoert en de stappen overslaat die niet nodig zijn.

Visuele representatie

Gegeven een lijst van vijf elementen, illustreren de volgende afbeeldingen hoe de belsortering de waarden doorloopt bij het sorteren ervan

De volgende afbeelding toont de ongesorteerde lijst

Eerste herhaling

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 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 wisselen we de posities van 21 en 9

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, dus er vindt geen swapping plaats.

Stap 4)

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

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

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

Tweede herhaling

De nieuwe lijst na de tweede iteratie is als volgt

Derde herhaling

De nieuwe lijst na de derde iteratie is als volgt

Vierde herhaling

De nieuwe lijst na de vierde iteratie is als volgt

Python-voorbeelden

De volgende code laat zien hoe je het Bubble Sort-algoritme in Python implementeert.

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)

Het uitvoeren van het bovenstaande bubbelsorteerprogramma in Python levert de volgende resultaten op

[6, 9, 21, 3, 33]

Code Verklaring

De verklaring voor de programmacode van Python Bubble Sort is als volgt

HIER,

1. Definieert een functie bubbleSort die een parameter theSeq accepteert. De code voert niets uit.
2. Haalt de lengte van de array op en wijst de waarde toe aan een variabele n. De code geeft niets weer
3. Start een for-lus die het bubbelsorteeralgoritme (n - 1) keer uitvoert. Dit is de buitenste lus. De code geeft niets weer
4. Definieert een vlagvariabele die zal worden gebruikt om te bepalen of een swap heeft plaatsgevonden of niet. Dit is voor optimalisatiedoeleinden. De code geeft niets weer
5. Start de binnenste lus die alle waarden in de lijst vergelijkt van de eerste naar 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 rechterkant. De code geeft niets weer.
7. Wijst de waarde van theSeq [j] toe aan een tijdelijke variabele tmp als de voorwaarde evalueert naar true. De code geeft niets weer
8. De waarde van theSeq [j + 1] wordt toegewezen aan de positie van theSeq [j]. De code geeft niets weer
9. De waarde van de variabele tmp wordt toegewezen aan positie theSeq [j + 1]. De code geeft niets weer
10. De vlagvariabele krijgt de waarde 1 toegewezen om aan te geven dat er een swap heeft plaatsgevonden. De code geeft niets weer
11. Gebruikt een if-instructie om te controleren of de waarde van de variabele vlag 0 is. De code voert niets uit
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 voert 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 sort voordelen

Hieronder volgen enkele van de voordelen van het algoritme voor het sorteren van bellen

• Het is gemakkelijk te begrijpen
• Het presteert erg goed als de lijst al of bijna is gesorteerd
• Het vereist geen uitgebreid geheugen.
• Het is gemakkelijk om de code voor het algoritme te schrijven
• De benodigde ruimte is minimaal in vergelijking met andere sorteeralgoritmen.

Bubble sort Nadelen

Hieronder volgen enkele van de nadelen van het algoritme voor het sorteren van bellen

• 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 de praktijktoepassing.
• Het aantal stappen dat nodig is om de lijst te sorteren, is van de orde n ²

Complexiteitsanalyse van bellen sorteren

Er zijn drie soorten complexiteit:

1) Sorteer complexiteit

De sorteercomplexiteit wordt gebruikt om het aantal uitvoeringstijden en ruimte uit te drukken dat nodig is om de lijst te sorteren. De belsortering maakt (n - 1) iteraties om de lijst te sorteren waarbij n het totale aantal elementen in de lijst is.

2) Tijdscomplexiteit

De tijdcomplexiteit van de belsoort is O (n ² )

De tijdcomplexiteit kan worden gecategoriseerd als:

• In het ergste geval - dit is waar de verstrekte lijst in aflopende volgorde staat. Het algoritme voert het maximale aantal uitvoeringen uit dat wordt uitgedrukt als [Big-O] O (n ² )
• In het beste geval - dit gebeurt wanneer de verstrekte lijst al is gesorteerd. Het algoritme voert het minimum aantal uitvoeringen uit dat 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) Ruimtecomplexiteit

De ruimtecomplexiteit meet de hoeveelheid extra ruimte die nodig is voor het sorteren van de lijst. De belsortering vereist slechts één (1) extra ruimte voor de tijdelijke variabele die wordt gebruikt voor het omwisselen van waarden. Daarom heeft het een ruimtecomplexiteit van O (1).

Overzicht

• Het algoritme voor het sorteren van bellen werkt door twee aangrenzende waarden te vergelijken en ze om te wisselen als de waarde aan de linkerkant kleiner is dan de waarde aan de rechterkant.
• Het implementeren van een bubbelsorteeralgoritme is relatief eenvoudig met Python. Het enige dat u hoeft te gebruiken, zijn for loops en if-statements.
• Het probleem dat het bubbelsorteeralgoritme oplost, is het nemen van een willekeurige lijst met items en deze omzetten in een geordende lijst.
• Het bubbelsorteeralgoritme in de gegevensstructuur presteert het beste wanneer de lijst al is gesorteerd, aangezien het een minimaal aantal iteraties uitvoert.
• Het algoritme voor het sorteren van bellen werkt niet goed als de lijst in omgekeerde volgorde staat.
• De bubbler-soort 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 belsortering maakt het algoritme efficiënter door onnodige iteraties over te slaan bij het controleren van waarden die al zijn gesorteerd.