BOBLE SORTERING - DS TUTORIAL

I denne artikel vil vi diskutere boblesorteringsalgoritmen. Arbejdsproceduren for boblesortering er enklest. Denne artikel vil være meget nyttig og interessant for studerende, da de kan blive udsat for boblesortering som et spørgsmål i deres eksamener. Så det er vigtigt at diskutere emnet.

hvad er autowired i java

Boblesortering fungerer ved gentagne gange at udskifte tilstødende elementer, indtil de ikke er i den tilsigtede rækkefølge. Det kaldes boblesortering, fordi bevægelsen af array-elementer er ligesom bevægelsen af luftbobler i vandet. Bobler i vand stiger op til overfladen; på samme måde flytter array-elementerne i boblesortering til slutningen i hver iteration.

Selvom det er nemt at bruge, bruges det primært som et pædagogisk værktøj, fordi effektiviteten af boblesortering er dårlig i den virkelige verden. Det er ikke egnet til store datasæt. Den gennemsnitlige og worst-case kompleksitet af Bubble sort er På²), hvor n er en række genstande.

Bubble short bruges hovedsageligt hvor -

kompleksitet er ligegyldig
enkel og kortkode foretrækkes

Algoritme

Antag i algoritmen nedenfor arr er en række af n elementer. Den antagne bytte rundt funktion i algoritmen vil bytte værdierne af givne matrixelementer.

 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

Arbejde med boblesorteringsalgoritme

Lad os nu se, hvordan boblesorteringsalgoritmen fungerer.

For at forstå, hvordan boblesorteringsalgoritmen fungerer, lad os tage et usorteret array. Vi tager et kort og præcist array, som vi ved, at kompleksiteten af boblesortering er På²).

Lad elementerne i array være -

Første pas

Sortering starter fra de to indledende elementer. Lad dem sammenligne dem for at kontrollere, hvilken der er størst.

Her er 32 større end 13 (32 > 13), så det er allerede sorteret. Sammenlign nu 32 med 26.

Her er 26 mindre end 36. Så det er nødvendigt at bytte. Efter at have skiftet nyt array vil se sådan ud -

Sammenlign nu 32 og 35.

Her er 35 større end 32. Så der er ingen ombytning påkrævet, da de allerede er sorteret.

Nu vil sammenligningen være mellem 35 og 10.

Her er 10 mindre end 35, der ikke er sorteret. Så det er nødvendigt at bytte. Nu når vi til enden af arrayet. Efter første pass vil arrayet være -

Gå nu til den anden iteration.

Andet pas

Den samme proces vil blive fulgt for anden iteration.

c# datetime

Her er 10 mindre end 32. Så det er nødvendigt at bytte. Efter ombytning vil arrayet være -

Gå nu til den tredje iteration.

Tredje pas

Den samme proces vil blive fulgt for tredje iteration.

Her er 10 mindre end 26. Så det er nødvendigt at bytte. Efter ombytning vil arrayet være -

Gå nu til den fjerde iteration.

Fjerde pas

På samme måde vil arrayet efter den fjerde iteration være -

Derfor er der ingen ombytning påkrævet, så arrayet er helt sorteret.

Boblesorteringskompleksitet

Lad os nu se tidskompleksiteten af boblesortering i bedste tilfælde, gennemsnitligt tilfælde og værste tilfælde. Vi vil også se rumkompleksiteten af boblesortering.

1. Tidskompleksitet

Sag	Tidskompleksitet
Bedste sag	På)
Gennemsnitlig tilfælde	På²)
Worst Case	På²)

På).

På²).

2. Rumkompleksitet

Rumkompleksitet	O(1)
Stabil	JA

Rumkompleksiteten af boblesortering er O(1). Det skyldes, at der i boblesortering kræves en ekstra variabel for at bytte.
Rumkompleksiteten af optimeret boblesortering er O(2). Det skyldes, at der kræves to ekstra variabler i optimeret boblesortering.

Lad os nu diskutere den optimerede boblesorteringsalgoritme.

Optimeret boblesorteringsalgoritme

I boblesorteringsalgoritmen foretages sammenligninger, selv når arrayet allerede er sorteret. På grund af det øges udførelsestiden.

For at løse det kan vi bruge en ekstra variabel byttet rundt. Den er indstillet til rigtigt hvis bytte kræver; ellers er den indstillet til falsk.

Det vil være nyttigt, som antag efter en iteration, hvis der ikke er behov for ombytning, værdien af variabel byttet rundt vil være falsk. Det betyder, at elementerne allerede er sorteret, og at der ikke kræves yderligere iterationer.

Denne metode reducerer udførelsestiden og optimerer også boblesorteringen.

Algoritme til optimeret 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 af Bubble sort

Lad os nu se Bubbles programmer sortere på forskellige programmeringssprog.

hvordan man ændrer streng til int

Program: Skriv et program til at implementere boblesortering i C-sprog.

 #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;>

Produktion

Program: Skriv et program til at 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;>