Menu

Boblesortering i C ++ med eksempler

bubble sort c with examples

Prøv Vores Instrument Til At Fjerne Problemer

Boblesorteringsteknik i C ++.

Boblesortering er den enkleste af sorteringsteknikkerne.

I boblesorteringsteknikken sammenlignes hvert af elementerne på listen med dets tilstødende element. Hvis der således er n elementer i liste A, sammenlignes A (0) med A (1), A (1) sammenlignes med A (2) og så videre.

Efter sammenligning hvis det første element er større end det andet, byttes de to elementer derefter.

=> Besøg her for det komplette C ++ kursus fra eksperter.

BUBBEL SORT

Hvad du vil lære:

pl sql interview spørgsmål og svar til erfaren pdf

Boblesorteringsteknik

Ved hjælp af boblesorteringsteknikken udføres sorteringen i gennemløb eller iteration. Således i slutningen af ​​hver iteration placeres det tungeste element på det rette sted på listen. Med andre ord, det største element på listen bobler op.

Vi har givet en generel algoritme for boblesorteringsteknik nedenfor.

Generel algoritme

Trin 1 : For i = 0 til N-1 gentages trin 2
Trin 2 : For J = i + 1 til N - gentager jeg
Trin 3 : hvis A (J)> A (i)
Byt A (J) og A (i)
(End of Inner for loop)
(Afslut hvis ydre til løkke)
Trin 4 : Afslut

Her er en pseudokode til boble sorteringsalgoritme, hvor vi krydser listen ved hjælp af to iterative sløjfer.

I den første sløjfe starter vi fra 0thelement og i den næste sløjfe starter vi fra et tilstødende element. I den indre sløjfekrop sammenligner vi hvert af de tilstødende elementer og bytter dem, hvis de ikke er i orden. I slutningen af ​​hver iteration af den ydre sløjfe bobler det tungeste element op i slutningen.

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

Ovenstående er pseudokoden til boble-sorteringsteknik. Lad os nu illustrere denne teknik ved hjælp af en detaljeret illustration.

Illustration

Vi tager en matrix af størrelse 5 og illustrerer algoritmen for sortering af boble.

Illustration af boblesortering - Pass 1

Bubble Sort Illustration - Pass 2

Bobleillustration - Pass 3

Array helt sorteret.

Ovenstående illustration kan opsummeres i tabelform som vist nedenfor:

PassereUsorteret listesammenligningSorteret 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}SORTERET

Som vist i illustrationen, med hvert pas, bobler det største element op til det sidste og sorterer dermed listen med hvert pas. Som nævnt i indledningen sammenlignes hvert element med dets tilstødende element og byttes med hinanden, hvis de ikke er i orden.

Som vist i illustrationen ovenfor placeres det største element i slutningen af ​​den første gennemgang, hvis arrayet skal sorteres i stigende rækkefølge. For det andet pass placeres det næststørste element på den næstsidste position på listen og så videre.

Når vi når N-1 (hvor N er et samlet antal elementer på listen) passerer, får vi hele listen sorteret.

.net c # interviewspørgsmål

Bubblesorteringsteknik kan implementeres på ethvert programmeringssprog. Vi har implementeret boblesorteringsalgoritmen ved hjælp af C ++ og Java-sprog nedenfor.

C ++ Eksempel

Lad os se et programmeringseksempel for at 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 <

Produktion:

Indtastningsliste ...

10 2 0 14 43 25 18 1 5 45

Sorteret elementliste ...

0 1 2 5 10 14 18 25 43 45

Antal passeringer, der er taget for at 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)

Produktion:

bubble_sort Java-output

I begge programmer har vi brugt en matrix på 10 elementer, og vi sorterer det ved hjælp af boblesorteringsteknikken. I begge programmer har vi brugt to til sløjfer til at gentage gennem de tilstødende elementer i arrayet.

I slutningen af ​​hvert pass (den ydre sløjfe) bobles det største element i arrayet op til slutningen af ​​arrayet. Vi tæller også antallet af passeringer, der kræves for at sortere hele arrayet.

Kompleksitetsanalyse af boblesorteringsalgoritmen

Fra pseudokoden og illustrationen, som vi har set ovenfor, i boblesortering, laver vi N-1-sammenligninger i det første pass, N-2-sammenligninger i det andet pass og så videre.

Derfor er det samlede antal sammenligninger i boblesortering:

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

= N (N-1) / 2

= O (nto) => Tidskompleksitet af boblesorteringsteknik

Således er de forskellige kompleksiteter for boblesorteringsteknik angivet nedenfor:

Værst tilfælde tidskompleksitetO (n 2)
Kompleksitet i bedste tilfældePå)
Gennemsnitlig tidskompleksitetO (n 2)
RumkompleksitetO (1)

Boblesorteringsteknikken kræver kun et ekstra hukommelsesrum for tempvariablen for at lette swapping. Derfor er pladskompleksiteten for boblesorteringsalgoritme O (1).

konvertere tegn til streng c ++

Bemærk, at tidskompleksiteten i bedste tilfælde for boblesorteringsteknik er, når listen allerede er sorteret, og det vil være O (n).

Konklusion

Den største fordel ved Bubble Sort er algoritmens enkelhed. I boblesortering, med hvert pass, bobler det største element op til slutningen af ​​listen, hvis arrayet er sorteret i stigende rækkefølge.

Tilsvarende for at listen skal sorteres i faldende rækkefølge, vil det mindste element være på sit rette sted i slutningen af ​​hvert pass.

At være den enkleste og nemme at implementere sorteringsteknik, er boble sorter normalt taget for at introducere sortering til publikum. For det andet bruges boblesortering også til anvendelse som computergrafik, hvor udfyldning af polygonkanter osv. Kræver boblesortering for at sortere hjørnerne, der ligger på polygonen.

I vores kommende tutorial lærer vi mere om Selection Sort.

=> Besøg her for at lære C ++ fra bunden.

Anbefalet læsning

^