Bellen sorteren wordt beschouwd als een van de eenvoudigste sorteeralgoritmen die werken door de aangrenzende elementen herhaaldelijk om te wisselen als ze in de verkeerde volgorde staan. Met een bubbelsorteeralgoritme kun je zien dat het grootste element (ervan uitgaande dat we sorteren van klein naar groot) naar de bovenkant van de lijst of array zal “borrelen”.

Voorbeeld:
Stel dat we een lijst of array met elementen in oplopende volgorde willen sorteren (van kleinste naar grootste): List = (3,1,2)

Aangezien er geen swapping heeft plaatsgevonden, vertelt dit ons dat de array is al in oplopende volgorde gesorteerd!

Beste geval

Laten we nu hetzelfde algoritme opnieuw proberen, maar deze keer met het beste scenario, namelijk wanneer de elementen al in de volgorde zijn gesorteerd ( oplopend) zouden we graag willen.

Aangezien er geen swapping heeft plaatsgevonden, zijn we klaar, en het algoritme heeft slechts 2 vergelijkingen gemaakt en het aantal elementen in de array zullen we n = 3 noemen. Dus we kunnen zien dat voor n elementen die deze algoritmen in het beste geval alleen n-1-vergelijkingen accepteren, n-1 = O (n)

De procedure of het algoritme dat we hebben gebruikt is hieronder:

Dit algoritme gebruikt een vlag om te zien of de elementen zijn verwisseld of niet , waardoor het algoritme voor het sorteren van bellen in het beste geval O (n) in plaats van O (n²) kan zijn, zoals een andere implementatie van het sorteren van bellen.

Het bovenstaande algoritme
Worst Case = O (n²)
Best Case = O (n)

Laten we eens kijken naar een andere implementatie van het bubbelsorteeralgoritme:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

Het bovenstaande algoritme
Worst Case = O (n²)
Best Case = O (n²)

Worst Case

Laten we een array of lijst sorteren = (3,2,1). Dit zou het ergste geval zijn als de lijst in de volledig tegenovergestelde volgorde staat dan we willen (in oplopende volgorde) met behulp van het bovenstaande algoritme.

Eerste doorgang:
(3,2,1) – > Vergelijk de elementen 3 & 2
(2,3 , 1) – > Wissel 3 & 2 sinds 2 < 3
( 2,3,1) – > Vergelijk de elementen 3 & 1
(2,1,3) – > Wissel 1 & 3 sinds 1 < 3

Tweede doorgang:
(2,1,3) – > Vergelijk de elementen 2 & 1
(1,2,3) – > Wissel 2 & 1 sinds 1 < 2
(1,2,3) – > Vergelijk de elementen 2 & 3
(1,2,3) – > Geen SWAPPING nodig sinds 2 < 3

We zijn nu klaar met het doorlopen van beide lussen, dus de array moet in oplopende volgorde worden gesorteerd.

Merk op dat we 4 vergelijkingen hebben gemaakt in het bovenstaande tweede voorbeeld, en het aantal elementen in de array zullen we ‘n’ = 3 noemen, dus het aantal gemaakte vergelijkingen is (n-1) ², en (n-1) ² = O (n²)

Ook een geweldig boek om je voor te bereiden op codeer- / programmeerinterviews heet het kraken van het coderingsinterview. Het zal je helpen vertrouwd te raken met sorteeralgoritmen en probleemoplossing, dus zorg ervoor dat je het bekijkt!

Bedankt voor het lezen van dit artikel. Ik hoop dat het jullie allemaal helpt! Blijf leren, en als je meer algoritmeanalyse-video’s wilt, bezoek dan en abonneer je op mijn YouTube-kanalen (randerson112358 & compsci112358)

Bekijk het volgende voor meer inhoud / video’s over algoritme-analyse en programmering:

YouTube-kanaal:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Website:

Video-tutorials over herhalingsrelatie:

Video-tutorial over algoritme-analyse:

Twitter: