BUBBLESORTERING - HANDLEDNING FÖR DS

I den här artikeln kommer vi att diskutera bubbelsorteringsalgoritmen. Arbetsproceduren för bubbelsortering är enklast. Den här artikeln kommer att vara mycket användbar och intressant för studenter eftersom de kan möta bubbelsortering som en fråga i sina undersökningar. Så det är viktigt att diskutera ämnet.

rihannas ålder

Bubblesortering fungerar på att upprepade gånger byta intilliggande element tills de inte är i avsedd ordning. Det kallas bubblesort eftersom rörelsen av arrayelement är precis som rörelsen av luftbubblor i vattnet. Bubblor i vatten stiger upp till ytan; på samma sätt flyttas arrayelementen i bubblesort till slutet i varje iteration.

Även om det är enkelt att använda, används det främst som ett pedagogiskt verktyg eftersom prestandan för bubbelsortering är dålig i den verkliga världen. Den är inte lämplig för stora datamängder. Den genomsnittliga och värsta komplexiteten för Bubblesort är På²), var n är ett antal föremål.

Bubbelshort används främst där -

komplexitet spelar ingen roll
enkel och kortkod är att föredra

Algoritm

Antag i algoritmen nedan arr är en samling av n element. Den antagna byta funktion i algoritmen kommer att byta värden för givna arrayelement.

 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

Fungerar av Bubblesortsalgoritm

Låt oss nu se hur bubbelsorteringsalgoritmen fungerar.

För att förstå hur bubbelsorteringsalgoritmen fungerar, låt oss ta en osorterad array. Vi tar en kort och exakt array, som vi vet är komplexiteten i bubbelsortering På²).

Låt elementen i arrayen vara -

Första passet

Sorteringen börjar från de två första elementen. Låt jämföra dem för att se vilken som är störst.

Här är 32 större än 13 (32 > 13), så det är redan sorterat. Jämför nu 32 med 26.

Här är 26 mindre än 36. Så byte krävs. Efter att ha bytt kommer ny array att se ut så här -

Jämför nu 32 och 35.

Här är 35 större än 32. Så det krävs inget byte eftersom de redan är sorterade.

Nu kommer jämförelsen att ligga mellan 35 och 10.

Här är 10 mindre än 35 som inte är sorterade. Så byte krävs. Nu når vi slutet av arrayen. Efter första pass kommer arrayen att vara -

Gå nu till den andra iterationen.

Andra passet

Samma process kommer att följas för andra iterationen.

c++ konvertera int till sträng

Här är 10 mindre än 32. Så byte krävs. Efter byte kommer arrayen att vara -

Gå nu till den tredje iterationen.

Tredje passet

Samma process kommer att följas för tredje iterationen.

Här är 10 mindre än 26. Så byte krävs. Efter byte kommer arrayen att vara -

Gå nu till den fjärde iterationen.

Fjärde passet

På liknande sätt, efter den fjärde iterationen, kommer arrayen att vara -

Därför krävs inget byte, så arrayen är helt sorterad.

Bubblesorts komplexitet

Låt oss nu se tidskomplexiteten för bubbelsortering i bästa fall, genomsnittligt fall och värsta fall. Vi kommer också att se utrymmeskomplexiteten av bubbelsortering.

1. Tidskomplexitet

Fall	Tidskomplexitet
Bästa fall	På)
Genomsnittligt fall	På²)
Värsta fall	På²)

På).

På²).

2. Rymdkomplexitet

Rymdkomplexitet	O(1)
Stabil	JA

Rumskomplexiteten för bubbelsortering är O(1). Det beror på att en extra variabel krävs för att byta.
Rymdkomplexiteten för optimerad bubbelsortering är O(2). Det beror på att två extra variabler krävs i optimerad bubbelsortering.

Låt oss nu diskutera den optimerade bubbelsorteringsalgoritmen.

Optimerad bubbelsorteringsalgoritm

I bubbelsorteringsalgoritmen görs jämförelser även när matrisen redan är sorterad. På grund av det ökar utförandetiden.

För att lösa det kan vi använda en extra variabel bytt. Den är inställd på Sann om byte kräver; annars är den inställd på falsk.

Det kommer att vara till hjälp, som efter en iteration, om det inte krävs något utbyte, värdet på variabeln bytt kommer vara falsk. Det betyder att elementen redan är sorterade och inga ytterligare iterationer krävs.

Denna metod kommer att minska exekveringstiden och optimerar även bubbelsorteringen.

Algoritm för optimerad bubbelsortering

 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 Bubblesort

Låt oss nu se hur Bubbles program sorteras på olika programmeringsspråk.

python sortering tuplar

Program: Skriv ett program för att implementera bubblesort 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;>

Produktion

Program: Skriv ett program för att implementera bubblesort 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;>