Bubbelsortering in C ++ met voorbeelden

bubble sort c with examples

Bubbelsorteertechniek in C ++.

Bubble Sort is de eenvoudigste sorteertechniek.

Bij de belsorteringstechniek wordt elk van de elementen in de lijst vergeleken met het aangrenzende element. Dus als er n elementen in lijst A staan, dan wordt A (0) vergeleken met A (1), A (1) wordt vergeleken met A (2) enzovoort.

Na het vergelijken of het eerste element groter is dan het tweede, worden de twee elementen verwisseld.

​ Bezoek hier voor de complete C ++ -cursus van experts.

Wat je leert:

beste bestandsherstelsoftware windows 10

• Bubble Sort-techniek
  • Algemeen algoritme
• Illustratie
• C ++ Voorbeeld
• Java-voorbeeld
• Complexiteitsanalyse van het bellen-sorteeralgoritme
• Gevolgtrekking
• Aanbevolen literatuur

Bubble Sort-techniek

Met behulp van de bubbelsorteertechniek gebeurt het sorteren in passages of iteraties. Aan het einde van elke iteratie wordt dus het zwaarste element op de juiste plaats in de lijst geplaatst. Met andere woorden, het grootste element in de lijst borrelt op.

We hebben hieronder een algemeen algoritme voor het sorteren van bellen gegeven.

Algemeen algoritme

Stap 1 : Voor i = 0 tot N-1 herhaal stap 2
Stap 2 : Voor J = i + 1 tot N - ik herhaal
Stap 3 : als A (J)> A (i)
Wissel A (J) en A (i) om
(Einde van Inner for loop)
(End if Outer for loop)
Stap 4 : Uitgang

Hier is een pseudo-code voor het algoritme voor het sorteren van bellen, waarbij we de lijst doorlopen met behulp van twee iteratieve lussen.

In de eerste lus beginnen we bij de 0^thelement en in de volgende lus gaan we uit van een aangrenzend element. In het lichaam van de binnenlus vergelijken we elk van de aangrenzende elementen en verwisselen ze als ze niet in orde zijn. Aan het einde van elke iteratie van de buitenste lus borrelt het zwaarste element aan het einde op.

Pseudocode

Het bovenstaande is de pseudo-code voor de techniek van het sorteren van bellen. Laten we deze techniek nu illustreren aan de hand van een gedetailleerde illustratie.

Illustratie

We nemen een array van maat 5 en illustreren het algoritme voor het sorteren van bellen.

Array volledig gesorteerd.

De bovenstaande illustratie kan in tabelvorm worden samengevat, zoals hieronder weergegeven:

Zoals te zien is in de afbeelding, borrelt bij elke doorgang het grootste element naar het laatste, waardoor de lijst bij elke doorgang wordt gesorteerd. Zoals vermeld in de inleiding, wordt elk element vergeleken met het aangrenzende element en met elkaar verwisseld als ze niet in orde zijn.

Zoals weergegeven in de bovenstaande afbeelding, wordt aan het einde van de eerste doorgang, als de array in oplopende volgorde moet worden gesorteerd, het grootste element aan het einde van de lijst geplaatst. Voor de tweede doorgang wordt het op een na grootste element op de voorlaatste positie in de lijst geplaatst, enzovoort.

Wanneer we N-1 bereiken (waarbij N een totaal aantal elementen in de lijst is) passeren, hebben we de hele lijst gesorteerd.

java j2ee interviewvragen en antwoorden voor ervaren

De techniek van het sorteren van bellen kan in elke programmeertaal worden geïmplementeerd. We hebben het bubbelsorteeralgoritme geïmplementeerd met behulp van C ++ en de onderstaande Java-taal.

C ++ Voorbeeld

Laten we een programmeervoorbeeld bekijken om het soort bellen te demonstreren.

Uitgang:

Invoerlijst ...

10 2 0 14 43 25 18 1 5 45

Lijst met gesorteerde elementen ...

0 1 2 5 10 14 18 25 43 45

Aantal passen dat is gemaakt om de lijst te sorteren: 10

Java-voorbeeld

Uitgang:

In beide programma's hebben we een reeks van 10 elementen gebruikt en we sorteren deze met behulp van de bubbelsorteertechniek. In beide programma's hebben we twee for-loops gebruikt om door de aangrenzende elementen van de array te lopen.

Aan het einde van elke doorgang (buitenste lus) wordt het grootste element in de array naar het einde van de array geborreld. We tellen ook het aantal passages dat nodig is om de hele array te sorteren.

Complexiteitsanalyse van het bellen-sorteeralgoritme

Uit de pseudocode en de illustratie die we hierboven hebben gezien, maken we in bellen-sortering N-1-vergelijkingen in de eerste doorgang, N-2-vergelijkingen in de tweede doorgang, enzovoort.

Daarom is het totale aantal vergelijkingen bij het sorteren van bellen:

Ik = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1

= N (N-1) / 2

= O (n^twee) => Tijdscomplexiteit van bellen-sorteertechniek

De verschillende complexiteiten van de techniek van het sorteren van bellen worden hieronder gegeven:

De belsorteertechniek vereist slechts één extra geheugenruimte voor de tijdelijke variabele om het wisselen te vergemakkelijken. Daarom is de ruimtecomplexiteit voor het algoritme voor het sorteren van bellen O (1).

qa vragen en antwoorden voor ingenieursinterviews

Merk op dat de beste tijdcomplexiteit voor de belsorteertechniek zal zijn wanneer de lijst al gesorteerd is en dat zal O (n) zijn.

Gevolgtrekking

Het belangrijkste voordeel van Bubble Sort is de eenvoud van het algoritme. Bij het sorteren van bellen borrelt bij elke doorgang het grootste element naar het einde van de lijst als de array in oplopende volgorde is gesorteerd.

Op dezelfde manier als de lijst in aflopende volgorde wordt gesorteerd, zal het kleinste element aan het einde van elke doorgang op de juiste plaats staan.

Omdat het de eenvoudigste en gemakkelijk te implementeren sorteertechniek is, wordt bellen sorteren meestal gebruikt om het sorteren bij het publiek te introduceren. Ten tweede wordt bellen-sorteren ook gebruikt in toepassingen zoals computergraphics waarbij het vullen van veelhoekige randen, enz. Bellen-sorteren vereist om de hoekpunten langs de veelhoek te sorteren.

In onze aanstaande tutorial zullen we in detail over Selectie sorteren leren.

​ Bezoek hier om C ++ vanaf het begin te leren.

Aanbevolen literatuur

• Shell-sortering in C ++ met voorbeelden
• Selectie sorteren in C ++ met voorbeelden
• MongoDB Sort () -methode met voorbeelden
• Unix-sorteeropdracht met syntaxis, opties en voorbeelden
• Invoegsortering in C ++ met voorbeelden
• Sorteer samenvoegen in C ++ met voorbeelden
• Heap-sortering in C ++ met voorbeelden
• Snel sorteren in C ++ met voorbeelden