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 An2), 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 An2).
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
| Fall | Zeitkomplexität |
|---|---|
| I'm besten fall | An) |
| Durchschnittlicher Fall | An2) |
| Schlimmsten Fall | An2) |
2. Raumkomplexität
| Weltraumkomplexität | O(1) |
| Stabil | JA |
- 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>'); 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 - ' + ' <br>'); 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>'; 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>'; printArray($a); ?> </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('Before sorting array elements are - ') for i in a: print(i, end = ' ') 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'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'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>'; 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>'; printArray($a); ?> </5;> Ausgabe
Programm: Schreiben Sie ein Programm, um die Blasensortierung in Python zu implementieren.
a = [35, 10, 31, 11, 26] print('Before sorting array elements are - ') for i in a: print(i, end = ' ') 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'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's complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:>