Meny

Boblesortering i C ++ med eksempler

bubble sort c with examples

Prøv Instrumentet Vårt For Å Eliminere Problemer

Boblesorteringsteknikk i C ++.

Bubble Sort er den enkleste av sorteringsteknikkene.

I boblesorteringsteknikken sammenlignes hvert av elementene i listen med det tilstøtende elementet. Således hvis det er n elementer i liste A, blir A (0) sammenlignet med A (1), A (1) sammenlignes med A (2) og så videre.

Etter å ha sammenlignet om det første elementet er større enn det andre, byttes de to elementene da.

=> Besøk her for hele C ++ kurset fra eksperter.

BUBBEL SORT

Hva du vil lære:

oppsettformørkelse for c ++

Boblesorteringsteknikk

Ved hjelp av boblesorteringsteknikken gjøres sortering i passeringer eller iterasjon. Dermed plasseres det tyngste elementet på slutten av hver iterasjon på sitt rette sted i listen. Med andre ord, det største elementet i listen bobler opp.

Vi har gitt en generell algoritme for boblesorteringsteknikk nedenfor.

Generell algoritme

Trinn 1 : For i = 0 til N-1, gjenta trinn 2
Steg 2 : For J = i + 1 til N - gjentar jeg
Trinn 3 : hvis A (J)> A (i)
Bytt A (J) og A (i)
(End of Inner for loop)
(Slutt hvis ytre for løkke)
Trinn 4 : Exit

Her er en pseudo-kode for boblesorteringsalgoritme, der vi krysser listen ved hjelp av to iterative sløyfer.

I den første sløyfen starter vi fra 0thelement og i neste sløyfe starter vi fra et tilstøtende element. I den indre sløyfekroppen sammenligner vi hvert av de tilstøtende elementene og bytter dem hvis de ikke er i orden. På slutten av hver iterasjon av den ytre sløyfen, bobler det tyngste elementet opp på slutten.

Pseudokode

Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array(i-1) > array(i) then swap array(i-1) and array(i) swapped = true end if end for until not swapped end procedure

Ovennevnte er pseudokoden for boblesorteringsteknikk. La oss nå illustrere denne teknikken ved å bruke en detaljert illustrasjon.

Illustrasjon

Vi tar en rekke størrelser 5 og illustrerer algoritmen for sortering av bobler.

Illustrasjon av boblesortering - Pass 1

Bubble Sort Illustration - Pass 2

Bobleillustrasjon - Pass 3

Array helt sortert.

Illustrasjonen ovenfor kan oppsummeres i tabellform som vist nedenfor:

SendeUsortert listesammenligningSortert liste
{5,0,10,12,15}{10.12}{5,0,10,12,15}
1{10,5,15,0,12}{10.5}{5,10,15,0,12}
{5,10,15,0,12}{10.15}{5,10,15,0,12}
{5,10,15,0,12}{15.0}{5,10,0,15,12}
{5,10,0,15,12}{15.12}{5,10,0,12,15}
to{5,10,0,12,15}{5,10}{5,10,0,12,15}
{5,10,0,12,15}{10.0}{5,0,10,12,15}
3{5,0,10,12,15}{5,0}{0,5,10,12,15}
{5,0,10,12,15}{5,10}{5,0,10,12,15}
{5,0,10,12,15}SORTERT

Som vist i illustrasjonen, med hvert pass, bobler det største elementet opp til det siste og sorterer dermed listen med hvert pass. Som nevnt innledningsvis, sammenlignes hvert element med dets tilstøtende element og byttes med hverandre hvis de ikke er i orden.

Som vist i illustrasjonen ovenfor, hvis matrisen skal sorteres i stigende rekkefølge, på slutten av første passering, plasseres det største elementet på slutten av listen. For det andre passet plasseres det nest største elementet på nest siste plassering i listen og så videre.

Når vi når N-1 (hvor N er et totalt antall elementer i listen) passerer, vil vi få sortert hele listen.

gratis windows registry cleaner og reparasjon

Boblesorteringsteknikk kan implementeres på alle programmeringsspråk. Vi har implementert boblesorteringsalgoritmen ved hjelp av C ++ og Java-språk nedenfor.

C ++ Eksempel

La oss se et programmeringseksempel for å demonstrere boblesorteringen.

#include using namespace std; int main () { int i, j,temp,pass=0; int a(10) = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ... '; for(i = 0; i<10; i++) { cout <

Produksjon:

Inngangsliste ...

10 2 0 14 43 25 18 1 5 45

Sortert elementliste ...

0 1 2 5 10 14 18 25 43 45

Antall passeringer for å sortere listen: 10

Java-eksempel

class Main { public static void main(String() args) { int pass = 0; int() a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a(i)

Produksjon:

bubble_sort Java-utgang

I begge programmene har vi brukt en rekke med 10 elementer, og vi sorterer det ved hjelp av boblesorteringsteknikken. I begge programmene har vi brukt to for løkker til å gjenta gjennom tilstøtende elementer i matrisen.

På slutten av hvert pass (den ytre sløyfen) bobles det største elementet i matrisen opp til slutten av matrisen. Vi teller også antall passeringer som kreves for å sortere hele matrisen.

programvareutvikling livssyklus foss metode

Kompleksitetsanalyse av boblesorteringsalgoritmen

Fra pseudokoden og illustrasjonen som vi har sett ovenfor, i boblesortering, lager vi N-1-sammenligninger i første omgang, N-2-sammenligninger i andre omgang og så videre.

Derfor er det totale antallet sammenligninger i boblesortering:

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

= N (N-1) / 2

= O (nto) => Tidskompleksitet for boblesorteringsteknikk

Dermed er de forskjellige kompleksitetene for boblesorteringsteknikk gitt nedenfor:

Kompleksitet i verste fallO (n 2)
Kompleksitet i beste fallPå)
Gjennomsnittlig tidskompleksitetO (n 2)
RomkompleksitetO (1)

Boblesorteringsteknikken krever bare ett ekstra minne for tempvariabelen for å gjøre det lettere å bytte. Derfor er romkompleksiteten for boblesorteringsalgoritme O (1).

Merk at tidskompleksiteten i beste tilfelle for boblesorteringsteknikk vil være når listen allerede er sortert, og det vil være O (n).

Konklusjon

Den største fordelen med Bubble Sort er algoritmens enkelhet. I boblesortering, med hvert pass, bobler det største elementet opp til slutten av listen hvis matrisen er sortert i stigende rekkefølge.

På samme måte for at listen skal sorteres i synkende rekkefølge, vil det minste elementet være på sin rette plass på slutten av hvert pass.

Å være den enkleste og letteste å implementere sorteringsteknikk, blir boblesortering vanligvis tatt for å introdusere sortering for publikum. For det andre blir boblesortering også brukt i applikasjoner som datagrafikk hvor fylling av polygonkanter, etc. krever boblesortering for å sortere toppunktene langs polygonet.

I vår kommende opplæring vil vi lære om Selection Sort i detalj.

=> Besøk her for å lære C ++ fra grunnen.

Anbefalt lesing

^