BOBLESORTERING - DS VEILEDNING

I denne artikkelen vil vi diskutere boblesorteringsalgoritmen. Arbeidsprosedyren for boblesortering er enklest. Denne artikkelen vil være veldig nyttig og interessant for studenter, da de kan møte boblesortering som et spørsmål i eksamenene deres. Så det er viktig å diskutere temaet.

strsep c

Boblesortering fungerer ved gjentatte bytte av tilstøtende elementer til de ikke er i den tiltenkte rekkefølgen. Det kalles boblesortering fordi bevegelsen av array-elementer er akkurat som bevegelsen av luftbobler i vannet. Bobler i vann stiger opp til overflaten; på samme måte flyttes matriseelementene i boblesortering til slutten i hver iterasjon.

Selv om det er enkelt å bruke, brukes det først og fremst som et pedagogisk verktøy fordi ytelsen til boblesortering er dårlig i den virkelige verden. Den er ikke egnet for store datasett. Den gjennomsnittlige og verste tilfellet av Bubble-sort er På²), hvor n er en rekke elementer.

Boblekort brukes hovedsakelig der -

kompleksitet spiller ingen rolle
enkel og kortkode foretrekkes

Algoritme

Anta i algoritmen gitt nedenfor arr er en rekke av n elementer. Den antatte bytte funksjonen i algoritmen vil bytte ut verdiene til gitte matriseelementer.

 begin BubbleSort(arr) for all array elements if arr[i] &gt; arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort

Arbeid med boblesorteringsalgoritme

La oss nå se hvordan boblesorteringsalgoritmen fungerer.

For å forstå hvordan boblesorteringsalgoritmen fungerer, la oss ta en usortert matrise. Vi tar en kort og nøyaktig rekke, som vi vet at kompleksiteten til boblesortering er På²).

La elementene i array være -

Første pass

Sorteringen starter fra de to første elementene. La oss sammenligne dem for å sjekke hvilken som er størst.

Her er 32 større enn 13 (32 > 13), så det er allerede sortert. Sammenlign nå 32 med 26.

Her er 26 mindre enn 36. Så det kreves bytte. Etter å ha byttet ny matrise vil se slik ut -

Sammenlign nå 32 og 35.

Her er 35 større enn 32. Så det er ikke nødvendig å bytte ettersom de allerede er sortert.

Nå vil sammenligningen være mellom 35 og 10.

Her er 10 mindre enn 35 som ikke er sortert. Så det er nødvendig å bytte. Nå kommer vi til enden av matrisen. Etter første passering vil matrisen være -

Gå nå til den andre iterasjonen.

Andre pass

Den samme prosessen vil bli fulgt for andre iterasjon.

streng inn i array java

Her er 10 mindre enn 32. Så det er nødvendig å bytte. Etter bytte vil matrisen være -

Gå nå til den tredje iterasjonen.

Tredje pass

Den samme prosessen vil bli fulgt for tredje iterasjon.

Her er 10 mindre enn 26. Så det kreves bytte. Etter bytte vil matrisen være -

Gå nå til den fjerde iterasjonen.

Fjerde pass

På samme måte, etter den fjerde iterasjonen, vil matrisen være -

Derfor er det ikke nødvendig å bytte, så matrisen er fullstendig sortert.

Boblesorteringskompleksitet

La oss nå se tidskompleksiteten til boblesortering i beste tilfelle, gjennomsnittlig tilfelle og verste tilfelle. Vi vil også se romkompleksiteten til boblesortering.

1. Tidskompleksitet

Sak	Tidskompleksitet
Beste sak	På)
Gjennomsnittlig sak	På²)
Worst Case	På²)

På).

På²).

2. Romkompleksitet

Plass kompleksitet	O(1)
Stabil	JA

Romkompleksiteten til boblesortering er O(1). Det er fordi det i boblesortering kreves en ekstra variabel for å bytte.
Romkompleksiteten til optimalisert boblesortering er O(2). Det er fordi det kreves to ekstra variabler i optimalisert boblesortering.

La oss nå diskutere den optimaliserte boblesorteringsalgoritmen.

Optimalisert boblesorteringsalgoritme

I boblesorteringsalgoritmen gjøres sammenligninger selv når matrisen allerede er sortert. På grunn av det øker gjennomføringstiden.

For å løse det kan vi bruke en ekstra variabel byttet. Den er satt til ekte hvis bytte krever; ellers er den satt til falsk.

Det vil være nyttig, som anta etter en iterasjon, hvis det ikke er nødvendig å bytte, verdien av variabelen byttet vil være falsk. Det betyr at elementene allerede er sortert, og det er ikke nødvendig med flere iterasjoner.

Denne metoden vil redusere utførelsestiden og optimerer også boblesorteringen.

Algoritme for optimalisert boblesortering

 bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] &gt; array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort

Implementering av Bubble sort

La oss nå se programmene til Bubble sortere på forskjellige programmeringsspråk.

hvordan endre streng til int

Program: Skriv et program for å implementere boblesortering i C-språk.

 #include void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { printf('%d ',a[i]); } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main () j,temp; a[5]="{" 10, 35, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" printf('before sorting array elements are - 
'); print(a, n); bubble(a, printf('
after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-13.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C++ language.</p> <pre> #include using namespace std; void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { cout< <a[i]<<' '; } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main() j,temp; a[5]="{45," 1, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting array elements are - 
'; print(a, n); bubble(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-14.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C# language.</p> <pre> using System; public class Bubble { static void print (int[]a) //function to print array elements { int n = a.Length; int i; for (i = 0; i <n; 26 i++) { console.write (' ' + a[i]); } static void bubble (int[]a) function to implement sort int n="a.Length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main () int[] a="{" 45, 1, 32, 13, }; ('
 before sorting array elements are - 
'); print (a); console.writeline (); after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-15.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in Java.</p> <pre> public class Bubble { static void print (int a[]) //function to print array elements { int n = a.length; int i; for (i = 0; i <n; i++) { system.out.print(a[i] + ' '); } static void bubblesort (int a[]) function to implement bubble sort int n="a.length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main(string[] args) a[]="{35," 10, 31, 11, 26}; b1="new" bubble(); system.out.println('before sorting array elements are - b1.print(a); b1.bubblesort(a); system.out.println(); system.out.println('after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-16.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in JavaScript.</p> <pre> var a = [35, 10, 31, 11, 26]; function print() //function to print array elements { for(i = 0; i <5; i++) { document.writeln(a[i]); } document.write('before sorting array elements are - ' + <br>&apos;); print(); for(i = 0; i <5; i++) { for (j="0;" j < 5; j++) if(a[i] a[j]) temp="a[i];" a[i]="a[j];" a[j]="temp;" } document.write(' <br> After sorting array elements are - &apos; + &apos; <br>&apos;); print(); </5;></5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-17.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in PHP.</p> <pre> <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo ' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-18.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in python.</p> <pre> a = [35, 10, 31, 11, 26] print(&apos;Before sorting array elements are - &apos;) for i in a: print(i, end = &apos; &apos;) for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print('
after sorting array elements are - ') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm&apos;s complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:></pre></n;></pre></n;></pre></n;></pre></n;>

Produksjon

Program: Skriv et program for å implementere boblesortering i PHP.

 <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo \' \'; } } echo \'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo \' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;>