Bubble Sort is een eenvoudig algoritme dat wordt gebruikt om een bepaalde set elementen geleverd in de vorm van een array met n aantal elementen. Bubble Sort vergelijkt alle elementen een voor een en sorteert ze op basis van hun waarden.

Als de gegeven array in oplopende volgorde moet worden gesorteerd, begint het sorteren van bellen met het vergelijken van het eerste element van de array met het tweede element, als het eerste element groter is dan het tweede element, zal het beide elementen verwisselen en vervolgens het tweede en het derde element vergelijken, enzovoort.

Als we totaal hebben n elementen, dan moeten we dit proces n-1 keer herhalen.

Het staat bekend als bellen sorteren, omdat bij elke volledige iteratie het grootste element in de gegeven array omhoog borrelt naar de laatste plaats of de hoogste index, net zoals een waterbel naar het wateroppervlak stijgt.

Het sorteren vindt plaats door alle de elementen een voor een en vergelijken met het aangrenzende element en ze indien nodig verwisselen.

OPMERKING: Als u niet bekend bent met Sorteren in datastructuur, moet u fi Leer eerst wat sorteren is om te weten over de basisprincipes van sorteren.

Implementatie van het Bubble Sort-algoritme

Hieronder volgen de stappen die betrokken zijn bij het sorteren van bellen (voor het sorteren van een gegeven array in oplopende volgorde):

1. Begin met het eerste element (index = 0) en vergelijk het huidige element met het volgende element van de array.
2. Als het huidige element groter is dan het volgende element van de array, verwissel ze.
3. Als het huidige element kleiner is dan het volgende element, ga dan naar het volgende element. Herhaal stap 1.

Laten we eens kijken naar een array met waarden {5, 1, 6, 2, 4, 3}

Hieronder hebben we een picturale weergave van hoe bellen sorteren de gegeven array zal sorteren.

Zoals we kunnen zien in de bovenstaande weergave, na de eerste iteratie, 6 wordt bij de laatste index geplaatst, wat de juiste positie ervoor is.

Evenzo na de tweede iteratie, 5 staat op de voorlaatste index, enzovoort.

Tijd om de code te schrijven voor bellen sorteren:

Hoewel de bovenstaande logica een ongesorteerde array zal sorteren, is het bovenstaande algoritme nog steeds niet efficiënt omdat volgens de bovenstaande logica de buitenste for -lus blijft 6 iteraties uitvoeren, zelfs als de array na de tweede iteratie wordt gesorteerd.

We kunnen dus duidelijk ons algoritme optimaliseren.

Geoptimaliseerd Bubble Sort Algorithm

Om onze bubb Bij het sorteeralgoritme kunnen we een flag introduceren om te controleren of elementen worden verwisseld binnen de binnenste for -lus.

Daarom controleren we in de binnenste for -lus elke keer of het wisselen van elementen plaatsvindt of niet.

Als er voor een bepaalde iteratie geen uitwisseling nodig was place, betekent dit dat de array is gesorteerd en dat we uit de for -lus kunnen springen in plaats van alle iteraties uit te voeren.

Laten we eens kijken naar een array met waarden {11, 17, 18, 26, 23}

Hieronder hebben we een grafische weergave van hoe de geoptimaliseerde belsortering de gegeven array zal sorteren.

Zoals we kunnen zien, vond er in de eerste iteratie swapping plaats, daarom hebben we onze flag waarde geüpdatet naar 1, als resultaat komt de uitvoering opnieuw in de for -lus. Maar in de tweede iteratie zal er geen swapping plaatsvinden, vandaar dat de waarde van flag 0 blijft, en de uitvoering zal uit de lus breken.

In de bovenstaande code, in de functie bubbleSort, indien voor een enkele volledige cyclus van j iteratie (binnenste for lus), er vindt geen omwisseling plaats, daarna flag blijft 0 en dan breken we uit de for loops, omdat de array al gesorteerd is.

Complexiteitsanalyse van bellen sorteren

In bellen sorteren worden n-1 vergelijkingen uitgevoerd in de eerste doorgang, n-2 in 2e doorgang, n-3 in 3e doorgang enzovoort. Het totale aantal vergelijkingen is dus:

(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2i.e O (n2)

Vandaar dat de tijdcomplexiteit van Bubble Sort is O (n2).

Het belangrijkste voordeel van Bubble Sort is de eenvoud van het algoritme.

De ruimtecomplexiteit voor Bubble Sort is O (1), omdat er slechts één extra geheugenruimte nodig is, dwz voor temp variabele.

Ook is de beste tijdcomplexiteit O (n), dit is wanneer de lijst al is gesorteerd.

Hieronder volgen de complexiteit van tijd en ruimte voor het Bubble Sort-algoritme.

Nu we het Bubble-sorteeralgoritme hebben geleerd, kunt u deze sorteeralgoritmen en hun toepassingen ook bekijken:

• Invoegsortering
• Selectie sorteren
• Snel sorteren
• Sorteren samenvoegen
• Heap sorteren
• Tellen sorteren