Blasensortierungsalgorithmus

In diesem Tutorial erfahren Sie, wie das Sortieren von Blasen funktioniert. Außerdem finden Sie Arbeitsbeispiele für die Blasensortierung in C, C ++, Java und Python.

Die Blasensortierung ist ein Algorithmus, der die benachbarten Elemente vergleicht und ihre Positionen vertauscht, wenn sie nicht in der beabsichtigten Reihenfolge sind. Die Reihenfolge kann aufsteigend oder absteigend sein.

Wie funktioniert die Blasensortierung?

Vergleichen Sie ausgehend vom ersten Index das erste und das zweite Element. Wenn das erste Element größer als das zweite Element ist, werden sie ausgetauscht.
Vergleichen Sie nun das zweite und das dritte Element. Tauschen Sie sie aus, wenn sie nicht in Ordnung sind.
Der obige Vorgang wird bis zum letzten Element fortgesetzt. Vergleichen Sie die benachbarten Elemente
Der gleiche Vorgang wird für die verbleibenden Iterationen fortgesetzt. Nach jeder Iteration wird das größte Element unter den unsortierten Elementen am Ende platziert.
In jeder Iteration findet der Vergleich bis zum letzten unsortierten Element statt.
Das Array wird sortiert, wenn alle unsortierten Elemente an den richtigen Positionen platziert sind. Vergleichen Sie die benachbarten Elemente Vergleichen Sie die benachbarten Elemente Vergleichen Sie die benachbarten Elemente

Blasensortierungsalgorithmus

 bubleSort (Array) für i rightElement Swap leftElement und rightElement beenden bubbleSort

Beispiele für Python, Java und C / C ++

Python Java C C ++

 # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)

 // Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j  to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )

 // Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Optimierte Blasensortierung

Im obigen Code werden alle möglichen Vergleiche durchgeführt, auch wenn das Array bereits sortiert ist. Es erhöht die Ausführungszeit.

Der Code kann durch Einführung einer zusätzlichen ausgetauschten Variablen optimiert werden. Wenn nach jeder Iteration kein Austausch stattfindet, müssen keine weiteren Schleifen durchgeführt werden.

In einem solchen Fall wird die ausgetauschte Variable auf false gesetzt. So können wir weitere Iterationen verhindern.

Algorithmus zur optimierten Blasensortierung ist

 bubleSort (Array) getauscht <- false für i rightElement swap leftElement und rightElement getauscht <- true end bubbleSort

Beispiele für optimierte Blasensortierung

Python Java C C +

 # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

 // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j  to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )

 // Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (

  // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Komplexität

Bubble Sort is one of the simplest sorting algorithms. Two loops are implemented in the algorithm.

Cycle	Number of Comparisons
1st	(n-1)
2nd	(n-2)
3rd	(n-3)
… .	…
last	1

Number of comparisons: (n - 1) + (n - 2) + (n - 3) +… + 1 = n(n - 1) / 2 nearly equals to n²

Complexity: O(n²)

Also, we can analyze the complexity by simply observing the number of loops. There are 2 loops so the complexity is n*n = n²

Time Complexities:

Worst Case Complexity:O(n²)
If we want to sort in ascending order and the array is in descending order then, the worst case occurs.
Best Case Complexity:O(n)
If the array is already sorted, then there is no need for sorting.
Durchschnittliche Fallkomplexität: Sie tritt auf, wenn die Elemente des Arrays in einer durcheinandergebrachten Reihenfolge sind (weder aufsteigend noch absteigend).O(n²)