In diesem Artikel besprechen wir den Blasensortierungsalgorithmus. Der Arbeitsablauf beim Blasensortieren ist am einfachsten. Dieser Artikel wird für Studierende sehr hilfreich und interessant sein, da sie in ihren Prüfungen möglicherweise mit der Frage „Blasensortierung“ konfrontiert werden. Daher ist es wichtig, das Thema zu diskutieren.

Zeichen in eine Zeichenfolge in Java umwandeln

Bei der Blasensortierung werden benachbarte Elemente wiederholt ausgetauscht, bis sie nicht mehr in der vorgesehenen Reihenfolge sind. Es wird Blasensortierung genannt, weil die Bewegung von Array-Elementen genau wie die Bewegung von Luftblasen im Wasser ist. Blasen im Wasser steigen an die Oberfläche; Ebenso werden die Array-Elemente bei der Blasensortierung in jeder Iteration an das Ende verschoben.

Obwohl es einfach zu verwenden ist, wird es hauptsächlich als Lehrmittel verwendet, da die Leistung der Blasensortierung in der realen Welt schlecht ist. Es ist nicht für große Datenmengen geeignet. Die durchschnittliche und Worst-Case-Komplexität der Blasensortierung beträgt An²), Wo N ist eine Reihe von Elementen.

Bubble Short wird hauptsächlich dort eingesetzt, wo -

• Komplexität spielt keine Rolle
• Einfach und Shortcode wird bevorzugt

Algorithmus

Angenommen, im unten angegebenen Algorithmus arr ist ein Array von N Elemente. Das vorausgesetzt tauschen Die Funktion im Algorithmus tauscht die Werte bestimmter Array-Elemente aus.

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

Funktionsweise des Blasensortierungsalgorithmus

Sehen wir uns nun die Funktionsweise des Blasensortierungsalgorithmus an.

Um die Funktionsweise des Blasensortierungsalgorithmus zu verstehen, nehmen wir ein unsortiertes Array. Wir verwenden ein kurzes und genaues Array, da wir wissen, wie komplex die Blasensortierung ist An²).

Die Elemente des Arrays seien -

Erster Pass

Die Sortierung beginnt mit den ersten beiden Elementen. Vergleichen Sie sie, um zu prüfen, welches größer ist.

Hier ist 32 größer als 13 (32 > 13), also ist es bereits sortiert. Vergleichen Sie nun 32 mit 26.

Hier ist 26 kleiner als 36. Daher ist ein Austausch erforderlich. Nach dem Austausch sieht das neue Array so aus:

Vergleichen Sie nun 32 und 35.

Hier ist 35 größer als 32. Es ist also kein Austausch erforderlich, da sie bereits sortiert sind.

Jetzt wird der Vergleich zwischen 35 und 10 liegen.

Maurerformel

Hier ist 10 kleiner als 35, die nicht sortiert sind. Daher ist ein Austausch erforderlich. Jetzt sind wir am Ende des Arrays angelangt. Nach dem ersten Durchgang wird das Array wie folgt aussehen:

Fahren Sie nun mit der zweiten Iteration fort.

Zweiter Durchgang

Der gleiche Prozess wird für die zweite Iteration befolgt.

Hier ist 10 kleiner als 32. Daher ist ein Austausch erforderlich. Nach dem Austausch ist das Array wie folgt:

Fahren Sie nun mit der dritten Iteration fort.

Dritter Durchgang

Der gleiche Prozess wird für die dritte Iteration befolgt.

Hier ist 10 kleiner als 26. Daher ist ein Austausch erforderlich. Nach dem Austausch ist das Array wie folgt:

Fahren Sie nun mit der vierten Iteration fort.

Vierter Durchgang

In ähnlicher Weise wird das Array nach der vierten Iteration wie folgt aussehen:

Daher ist kein Austausch erforderlich, sodass das Array vollständig sortiert ist.

Komplexität der Blasensortierung

Sehen wir uns nun die zeitliche Komplexität der Blasensortierung im besten, durchschnittlichen und schlechtesten Fall an. Wir werden auch die räumliche Komplexität der Blasensortierung sehen.

1. Zeitkomplexität

Beste Fallkomplexität -Dies geschieht, wenn keine Sortierung erforderlich ist, d. h. das Array bereits sortiert ist. Die Zeitkomplexität der Blasensortierung beträgt im besten Fall An). Durchschnittliche Fallkomplexität -Es tritt auf, wenn die Array-Elemente in einer durcheinandergebrachten Reihenfolge vorliegen, die nicht richtig aufsteigend und nicht richtig absteigend ist. Die durchschnittliche Fallzeitkomplexität der Blasensortierung beträgt An²). Worst-Case-Komplexität -Es tritt auf, wenn die Array-Elemente in umgekehrter Reihenfolge sortiert werden müssen. Angenommen, Sie müssen die Array-Elemente in aufsteigender Reihenfolge sortieren, die Elemente jedoch in absteigender Reihenfolge. Die zeitliche Komplexität der Blasensortierung im schlimmsten Fall beträgt An²).

2. Raumkomplexität

• Die räumliche Komplexität der Blasensortierung beträgt O(1). Dies liegt daran, dass bei der Blasensortierung eine zusätzliche Variable zum Austauschen erforderlich ist.
• Die räumliche Komplexität der optimierten Blasensortierung beträgt O(2). Dies liegt daran, dass bei der optimierten Blasensortierung zwei zusätzliche Variablen erforderlich sind.

Lassen Sie uns nun den optimierten Blasensortierungsalgorithmus diskutieren.

Optimierter Blasensortierungsalgorithmus

Im Blasensortierungsalgorithmus werden Vergleiche auch dann durchgeführt, wenn das Array bereits sortiert ist. Dadurch erhöht sich die Ausführungszeit.

Um es zu lösen, können wir eine zusätzliche Variable verwenden getauscht. Es ist eingestellt WAHR wenn ein Austausch erforderlich ist; andernfalls wird es auf gesetzt FALSCH.

Es wird hilfreich sein, beispielsweise nach einer Iteration den Wert der Variablen zu ändern, wenn kein Austausch erforderlich ist getauscht wird sein FALSCH. Dies bedeutet, dass die Elemente bereits sortiert sind und keine weiteren Iterationen erforderlich sind.

Diese Methode verkürzt die Ausführungszeit und optimiert außerdem die Blasensortierung.

Algorithmus zur optimierten Blasensortierung

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

Implementierung der Blasensortierung

Sehen wir uns nun die Programme von Bubble Sort in verschiedenen Programmiersprachen an.

Python sortiert Tupel

Programm: Schreiben Sie ein Programm zur Implementierung der Blasensortierung in der Sprache C.

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

Ausgabe

Programm: Schreiben Sie ein Programm zur Implementierung der Blasensortierung in 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;>

Ausgabe

Programm: Schreiben Sie ein Programm, um die Blasensortierung in Python zu implementieren.

 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]:>