Eine Einführung in den Bubble-Sort-Algorithmus

Eskere Guru

Das Sortieren ist eine der grundlegendsten Operationen, die Sie auf Daten anwenden können. Sie können Elemente in verschiedenen Programmiersprachen mit verschiedenen Sortieralgorithmen wie Quick Sort, Bubble Sort, Merge Sort, Insertion Sort usw. sortieren. Bubble Sort ist der einfachste Algorithmus von allen.

In diesem Artikel erfahren Sie mehr über die Funktionsweise des Bubble-Sort-Algorithmus, den Pseudocode des Bubble-Sort-Algorithmus, seine zeitliche und räumliche Komplexität und seine Implementierung in verschiedenen Programmiersprachen wie C++, Python, C und JavaScript.

Wie funktioniert der Bubble-Sort-Algorithmus?

Bubble Sort ist der einfachste Sortieralgorithmus, der die Liste wiederholt durchläuft, benachbarte Elemente vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Dieses Konzept lässt sich anhand eines Beispiels effizienter erklären. Betrachten Sie ein unsortiertes Array mit den folgenden Elementen: {16, 12, 15, 13, 19}.

Beispiel:

Eine Einführung in den Bubble-Sort-Algorithmus - Bubble Sort

Hier werden die benachbarten Elemente verglichen und wenn sie nicht in aufsteigender Reihenfolge sind, werden sie vertauscht.

Pseudocode des Bubble-Sort-Algorithmus

In Pseudocode kann der Bubble-Sort-Algorithmus wie folgt ausgedrückt werden:

 bubbleSort(Arr[], size)
 // loop to access each array element
 for i=0 to size-1 do:
 // loop to compare array elements
 for j=0 to size-i-1 do:
 // compare the adjacent elements
 if Arr[j] > Arr[j+1] then
 // swap them
 swap(Arr[j], Arr[j+1])
 end if
 end for
 end for
 end

Der obige Algorithmus verarbeitet alle Vergleiche, auch wenn das Array bereits sortiert ist. Es kann weiter optimiert werden, indem der Algorithmus gestoppt wird, wenn die innere Schleife keinen Swap verursacht hat. Dadurch wird die Ausführungszeit des Algorithmus verkürzt.

Somit kann der Pseudocode des optimierten Bubble-Sort-Algorithmus ausgedrückt werden als:

 bubbleSort(Arr[], size)
 // loop to access each array element
 for i=0 to size-1 do:
 // check if swapping occurs
 swapped = false
 // loop to compare array elements
 for j=0 to size-i-1 do:
 // compare the adjacent elements
 if Arr[j] > Arr[j+1] then
 // swap them
 swap(Arr[j], Arr[j+1])
 swapped = true
 end if
 end for
 // if no elements were swapped that means the array is sorted now, then break the loop.
 if(not swapped) then
 break
 end if
 end for
 end

Zeitkomplexität und Hilfsraum des Bubble-Sort-Algorithmus

Die Worst-Case-Zeitkomplexität des Bubble-Sort-Algorithmus ist O(n^2). Es tritt auf, wenn das Array in absteigender Reihenfolge angeordnet ist und Sie es in aufsteigender Reihenfolge sortieren möchten oder umgekehrt.

Die Zeitkomplexität des Bubble-Sort-Algorithmus im besten Fall ist O(n). Es tritt auf, wenn das Array bereits sortiert ist.

Verwandte: Was ist Big-O-Notation?

Die durchschnittliche Zeitkomplexität des Bubble-Sort-Algorithmus beträgt O(n^2). Es tritt auf, wenn die Elemente des Arrays in einer durcheinandergebrachten Reihenfolge sind.

Der für den Bubble-Sort-Algorithmus benötigte Hilfsraum ist O(1).

C++-Implementierung des Bubble-Sort-Algorithmus

Unten ist die C++-Implementierung des Bubble-Sort-Algorithmus:

 // C++ implementation of the
 // optimised Bubble Sort algorithm
 #include <iostream>
 using namespace std;
 // Function to perform Bubble Sort
 void bubbleSort(int arr[], int size) {
 // Loop to access each element of the array
 for (int i=0; i<(size-1); i++) {
 // Variable to check if swapping occurs
 bool swapped = false;
 // loop to compare two adjacent elements of the array
 for (int j = 0; j < (size-i-1); j++) {
 // Comparing two adjacent array elements
 if (arr[j] > arr[j + 1]) {
 // Swap both elements if they're
 // not in correct order
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 swapped = true;
 }
 }
 // If no elements were swapped that means the array is sorted now,
 // then break the loop.
 if (swapped == false) {
 break;
 }
 }
 }
 // Prints the elements of the array
 void printArray(int arr[], int size) {
 for (int i = 0; i < size; i++) {
 cout << arr[i] << " ";
 }
 cout << endl;
 }
 int main() {
 int arr[] = {16, 12, 15, 13, 19};
 // Finding the length of the array
 int size = sizeof(arr) / sizeof(arr[0]);
 // Printing the given unsorted array
 cout << "Unsorted Array: " << endl;
 printArray(arr, size);
 // Calling bubbleSort() function
 bubbleSort(arr, size);
 // Printing the sorted array
 cout << "Sorted Array in Ascending Order:" << endl;
 printArray(arr, size);
 return 0;
 }

Ausgabe:

 Unsorted Array:
 16 12 15 13 19
 Sorted Array in Ascending Order:
 12 13 15 16 19

Python-Implementierung des Bubble-Sort-Algorithmus

Unten ist die Python-Implementierung des Bubble-Sort-Algorithmus:

 # Python implementation of the
 # optimised Bubble Sort algorithm

 # Function to perform Bubble Sort
 def bubbleSort(arr, size):
 # Loop to access each element of the list
 for i in range (size-1):
 # Variable to check if swapping occurs
 swapped = False
 # loop to compare two adjacent elements of the list
 for j in range(size-i-1):
 # Comparing two adjacent list elements
 if arr[j] > arr[j+1]:
 temp = arr[j]
 arr[j] = arr[j+1]
 arr[j+1] = temp
 swapped = True
 # If no elements were swapped that means the list is sorted now,
 # then break the loop.
 if swapped == False:
 break
 # Prints the elements of the list
 def printArray(arr):
 for element in arr:
 print(element, end=" ")
 print("")

 arr = [16, 12, 15, 13, 19]
 # Finding the length of the list
 size = len(arr)
 # Printing the given unsorted list
 print("Unsorted List:")
 printArray(arr)
 # Calling bubbleSort() function
 bubbleSort(arr, size)
 # Printing the sorted list
 print("Sorted List in Ascending Order:")
 printArray(arr)

Ausgabe:

 Unsorted List:
 16 12 15 13 19
 Sorted List in Ascending Order:
 12 13 15 16 19

Verwandte: So verwenden Sie For-Schleifen in Python

C Implementierung des Bubble-Sort-Algorithmus

Unten ist die C-Implementierung des Bubble-Sort-Algorithmus:

 // C implementation of the
 // optimised Bubble Sort algorithm
 #include <stdio.h>
 #include <stdbool.h>
 // Function to perform Bubble Sort
 void bubbleSort(int arr[], int size) {
 // Loop to access each element of the array
 for (int i=0; i<(size-1); i++) {
 // Variable to check if swapping occurs
 bool swapped = false;
 // loop to compare two adjacent elements of the array
 for (int j = 0; j < (size-i-1); j++) {
 // Comparing two adjacent array elements
 if (arr[j] > arr[j + 1]) {
 // Swap both elements if they're
 // not in correct order
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 swapped = true;
 }
 }
 // If no elements were swapped that means the array is sorted now,
 // then break the loop.
 if (swapped == false) {
 break;
 }
 }
 }
 // Prints the elements of the array
 void printArray(int arr[], int size) {
 for (int i = 0; i < size; i++) {
 printf("%d ", arr[i]);
 }
 printf(" ⁠n ");
 }
 int main() {
 int arr[] = {16, 12, 15, 13, 19};
 // Finding the length of the array
 int size = sizeof(arr) / sizeof(arr[0]);
 // Printing the given unsorted array
 printf("Unsorted Array: ⁠n");
 printArray(arr, size);
 // Calling bubbleSort() function
 bubbleSort(arr, size);
 // Printing the sorted array
 printf("Sorted Array in Ascending Order: ⁠n");
 printArray(arr, size);
 return 0;
 }

Ausgabe:

 Unsorted Array:
 16 12 15 13 19
 Sorted Array in Ascending Order:
 12 13 15 16 19

JavaScript-Implementierung des Bubble-Sort-Algorithmus

Unten sehen Sie die JavaScript-Implementierung des Bubble-Sort-Algorithmus:

 // JavaScript implementation of the
 // optimised Bubble Sort algorithm
 // Function to perform Bubble Sort
 function bubbleSort(arr, size) {
 // Loop to access each element of the array
 for(let i=0; i<size-1; i++) {
 // Variable to check if swapping occurs
 var swapped = false;
 // loop to compare two adjacent elements of the array
 for(let j=0; j<size-i-1; j++) {
 // Comparing two adjacent array elements
 if(arr[j] > arr[j+1]) {
 // Swap both elements if they're
 // not in correct order
 let temp = arr[j];
 arr[j] = arr[j+1];
 arr[j+1] = temp;
 swapped = true;
 }
 // If no elements were swapped that means the array is sorted now,
 // then break the loop.
 if (swapped == false) {
 break;
 }
 }
 }
 }
 // Prints the elements of the array
 function printArray(arr, size) {
 for (let i=0; i<size; i++) {
 document.write(arr[i] + " ");
 }
 document.write("<br>")
 }

 var arr = [16, 12, 15, 13, 19];
 // Finding the length of the array
 var size = arr.length;
 // Printing the given unsorted array
 document.write("Unsorted Array: <br>");
 printArray(arr, size);
 // Calling bubbleSort() function
 bubbleSort(arr, size);
 // Printing the sorted array
 document.write("Sorted Array in Ascending Order: <br>");
 printArray(arr, size);

Ausgabe:

 Unsorted Array:
 16 12 15 13 19
 Sorted Array in Ascending Order:
 12 15 13 16 19

Jetzt verstehen Sie die Funktionsweise des Bubble-Sort-Algorithmus

Bubble Sort ist der einfachste Sortieralgorithmus und wird hauptsächlich verwendet, um die Grundlagen des Sortierens zu verstehen. Bubble Sort kann auch rekursiv implementiert werden, bietet aber keine zusätzlichen Vorteile.

Mit Python können Sie den Bubble-Sort-Algorithmus ganz einfach implementieren. Wenn Sie mit Python nicht vertraut sind und Ihre Reise beginnen möchten, ist es eine gute Wahl, mit einem "Hello World"-Skript zu beginnen.