BELLEN SORTEREN - DS-ZELFSTUDIE

In dit artikel bespreken we het Bubble sort-algoritme. De werkwijze bij het sorteren van bellen is het eenvoudigst. Dit artikel zal zeer nuttig en interessant zijn voor studenten, omdat ze tijdens hun examens te maken kunnen krijgen met het soort bellen. Het is dus belangrijk om het onderwerp te bespreken.

xvideoservicedief ubuntu 14.04 downloaden

Bubble sort werkt op het herhaaldelijk verwisselen van aangrenzende elementen totdat ze niet in de bedoelde volgorde staan. Het wordt bellensortering genoemd omdat de beweging van array-elementen net als de beweging van luchtbellen in het water is. Bellen in water stijgen naar de oppervlakte; op dezelfde manier bewegen de array-elementen in de bellensoort in elke iteratie naar het einde.

Hoewel het eenvoudig te gebruiken is, wordt het vooral gebruikt als educatief hulpmiddel, omdat de prestaties van het bellensorteren in de echte wereld slecht zijn. Het is niet geschikt voor grote datasets. De gemiddelde en slechtste complexiteit van Bubble-soort is Op²), waar N bestaat uit een aantal artikelen.

Bubble short wordt voornamelijk gebruikt waar -

complexiteit doet er niet toe
eenvoudig en shortcode heeft de voorkeur

Algoritme

Stel dat in het onderstaande algoritme arr is een array van N elementen. De veronderstelde ruil functie in het algoritme zal de waarden van bepaalde array-elementen omwisselen.

 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

Werking van het Bubble Sort-algoritme

Laten we nu eens kijken naar de werking van het Bubble sort-algoritme.

Om de werking van het bellensorteeralgoritme te begrijpen, nemen we een ongesorteerde array. We nemen een korte en nauwkeurige reeks, omdat we weten dat de complexiteit van het sorteren van bellen is Op²).

Laat de elementen van array zijn -

Eerste Paas

Het sorteren begint vanaf de eerste twee elementen. Laten we ze vergelijken om te zien welke groter is.

Hier is 32 groter dan 13 (32 > 13), dus het is al gesorteerd. Vergelijk nu 32 met 26.

Hier is 26 kleiner dan 36. Omwisselen is dus vereist. Na het verwisselen zal de nieuwe array er als volgt uitzien:

Vergelijk nu 32 en 35.

Hier is 35 groter dan 32. Er is dus geen omwisseling nodig omdat ze al gesorteerd zijn.

Nu ligt de vergelijking tussen 35 en 10.

Hier is 10 kleiner dan 35 die niet zijn gesorteerd. Wisselen is dus noodzakelijk. Nu bereiken we het einde van de array. Na de eerste doorgang zal de array -

Ga nu naar de tweede iteratie.

Tweede pas

Hetzelfde proces zal worden gevolgd voor de tweede iteratie.

CSS-tekst uitlijnen

Hier is 10 kleiner dan 32. Omwisselen is dus vereist. Na het omwisselen zal de array -

Ga nu naar de derde iteratie.

Derde pas

Hetzelfde proces zal worden gevolgd voor de derde iteratie.

Hier is 10 kleiner dan 26. Omwisselen is dus vereist. Na het omwisselen zal de array -

Ga nu naar de vierde iteratie.

Vierde pas

Op dezelfde manier zal de array na de vierde iteratie zijn:

Er is dus geen swap nodig, dus de array is volledig gesorteerd.

Complexiteit van het sorteren van bellen

Laten we nu eens kijken naar de tijdscomplexiteit van het sorteren van bellen in het beste geval, het gemiddelde geval en het slechtste geval. We zullen ook de ruimtelijke complexiteit van het sorteren van bellen zien.

1. Tijdcomplexiteit

Geval	Tijdcomplexiteit
Beste geval	Op)
Gemiddeld geval	Op²)
Het slechtste geval	Op²)

Op).

Op²).

2. Ruimtecomplexiteit

Ruimtecomplexiteit	O(1)
Stal	JA

De ruimtecomplexiteit van het sorteren van bellen is O(1). De reden hiervoor is dat bij het sorteren van bellen een extra variabele nodig is voor het wisselen.
De ruimtecomplexiteit van een geoptimaliseerde bellensortering is O(2). Dit komt omdat er twee extra variabelen nodig zijn bij een geoptimaliseerde bellensortering.

Laten we nu het geoptimaliseerde algoritme voor het sorteren van bellen bespreken.

Geoptimaliseerd algoritme voor het sorteren van bellen

In het bellensorteeralgoritme worden vergelijkingen gemaakt, zelfs als de array al is gesorteerd. Hierdoor neemt de uitvoeringstijd toe.

Om het op te lossen kunnen we een extra variabele gebruiken verwisseld. Het is ingesteld op WAAR als ruilen dit vereist; anders is het ingesteld op vals.

Het zal nuttig zijn, bijvoorbeeld na een iteratie, als er geen omwisseling nodig is, de waarde van de variabele verwisseld zal zijn vals. Het betekent dat de elementen al zijn gesorteerd en dat er geen verdere iteraties nodig zijn.

Deze methode verkort de uitvoeringstijd en optimaliseert ook het sorteren van de bellen.

Algoritme voor geoptimaliseerde bellensortering

 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

Implementatie van Bubble-sortering

Laten we nu eens kijken naar de programma's van Bubble in verschillende programmeertalen.

voorbeeld van gebruikersnaam

Programma: Schrijf een programma om bellensortering in C-taal te implementeren.

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

Uitvoer

Programma: Schrijf een programma om bubble sortering in PHP te implementeren.

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