Blasensortierung ist das einfachste Sortieralgorithmus Das funktioniert, indem die benachbarten Elemente wiederholt ausgetauscht werden, wenn sie in der falschen Reihenfolge sind. Dieser Algorithmus eignet sich nicht für große Datensätze, da seine durchschnittliche und ungünstigste Zeitkomplexität recht hoch ist.
Blasensortierungsalgorithmus
Empfohlene Übung zum Blasensortieren Probieren Sie es aus!Im Bubble-Sort-Algorithmus
- Durchqueren Sie von links und vergleichen Sie benachbarte Elemente. Das höhere wird auf der rechten Seite platziert.
- Auf diese Weise wird das größte Element zunächst ganz nach rechts verschoben.
- Dieser Vorgang wird dann fortgesetzt, um den zweitgrößten Wert zu finden und ihn zu platzieren usw., bis die Daten sortiert sind.
Wie funktioniert die Blasensortierung?
Lassen Sie uns die Funktionsweise der Blasensortierung anhand der folgenden Abbildung verstehen:
Eingang: arr[] = {6, 0, 3, 5}
Alphabet als ZahlenErster Pass:
Das größte Element wird an der richtigen Position platziert, d. h. am Ende des Arrays.
Blasensortieralgorithmus: Platzieren des größten Elements an der richtigen Position
Zweiter Durchgang:
Java-Wert der EnumerationPlatzieren Sie das zweitgrößte Element an der richtigen Position
Blasensortieralgorithmus: Platzieren des zweitgrößten Elements an der richtigen Position
Dritter Durchgang:
Platzieren Sie die verbleibenden zwei Elemente an den richtigen Positionen.
Blasensortieralgorithmus: Platzieren der verbleibenden Elemente an ihren richtigen Positionen
- Gesamtnr. Anzahl Pässe: n-1
- Gesamtnr. von Vergleichen: n*(n-1)/2
Implementierung von Bubble Sort
Nachfolgend finden Sie die Implementierung der Blasensortierung. Es kann optimiert werden, indem der Algorithmus gestoppt wird, wenn die innere Schleife keinen Austausch verursacht hat.
Zeichenfolge in Datum umwandelnC++
// Optimized implementation of Bubble sort #include using namespace std; // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) { int i, j; bool swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { swap(arr[j], arr[j + 1]); getauscht = wahr; } } // Wenn keine zwei Elemente // durch die innere Schleife vertauscht wurden, dann break if (swapped == false) break; } } // Funktion zum Drucken eines Arrays void printArray(int arr[], int size) { int i; für (i = 0; i< size; i++) cout << ' ' << arr[i]; } // Driver program to test above functions int main() { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int N = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, N); cout << 'Sorted array:
'; printArray(arr, N); return 0; } // This code is contributed by shivanisinghss2110> C // Optimized implementation of Bubble sort #include #include void swap(int* xp, int* yp) { int temp = *xp; *xp = *yp; *yp = temp; } // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) { int i, j; bool swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { swap(&arr[j], &arr[j + 1]); vertauscht = wahr; } } // Wenn keine zwei Elemente durch die innere Schleife vertauscht wurden, // dann break if (swapped == false) break; } } // Funktion zum Drucken eines Arrays void printArray(int arr[], int size) { int i; für (i = 0; i< size; i++) printf('%d ', arr[i]); } // Driver program to test above functions int main() { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int n = sizeof(arr) / sizeof(arr[0]); bubbleSort(arr, n); printf('Sorted array:
'); printArray(arr, n); return 0; }> Java // Optimized java implementation of Bubble sort import java.io.*; class GFG { // An optimized version of Bubble Sort static void bubbleSort(int arr[], int n) { int i, j, temp; boolean swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { // arr[j] und arr[j+1] vertauschen temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; vertauscht = wahr; } } // Wenn keine zwei Elemente // durch die innere Schleife vertauscht wurden, dann break if (swapped == false) break; } } // Funktion zum Drucken eines Arrays static void printArray(int arr[], int size) { int i; für (i = 0; i< size; i++) System.out.print(arr[i] + ' '); System.out.println(); } // Driver program public static void main(String args[]) { int arr[] = { 64, 34, 25, 12, 22, 11, 90 }; int n = arr.length; bubbleSort(arr, n); System.out.println('Sorted array: '); printArray(arr, n); } } // This code is contributed // by Nikita Tiwari.> Python3 # Optimized Python program for implementation of Bubble Sort def bubbleSort(arr): n = len(arr) # Traverse through all array elements for i in range(n): swapped = False # Last i elements are already in place for j in range(0, n-i-1): # Traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j]>arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = True if (swapped == False): break # Treibercode zum Testen oben if __name__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('Sorted array:') for i in range(len(arr)): print('%d' % arr[i], end=' ') # Dieser Code wurde von Suraj krushna Yadav>'> geändertC# Javascript // Optimized javaScript implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(arr, n) { var i, j, temp; var swapped; for (i = 0; i < n - 1; i++) { swapped = false; for (j = 0; j < n - i - 1; j++) { if (arr[j]>arr[j + 1]) { // arr[j] und arr[j+1] vertauschen temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; vertauscht = wahr; } } // WENN keine zwei Elemente // durch die innere Schleife vertauscht wurden, dann break if (swapped == false) break; } } // Funktion zum Drucken eines Arrays function printArray(arr, size) { var i; für (i = 0; i< size; i++) console.log(arr[i] + ' '); } // Driver program var arr = [ 64, 34, 25, 12, 22, 11, 90 ]; var n = arr.length; bubbleSort(arr, n); console.log('Sorted array: '); printArray(arr, n); // This code is contributed shivanisinghss2110> PHP // PHP Optimized implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(&$arr) { $n = sizeof($arr); // Traverse through all array elements for($i = 0; $i < $n; $i++) { $swapped = False; // Last i elements are already // in place for ($j = 0; $j < $n - $i - 1; $j++) { // Traverse the array from 0 to // n-i-1. Swap if the element // found is greater than the // next element if ($arr[$j]>$arr[$j+1]) { $t = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $t; $swapped = True; } } // Wenn keine zwei Elemente // durch die innere Schleife vertauscht wurden, dann break if ($swapped == False) break; } } // Treibercode $arr = array(64, 34, 25, 12, 22, 11, 90); $len = sizeof($arr); bubbleSort($arr); echo 'Sortiertes Array:
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>> Ausgabe
Sorted array: 11 12 22 25 34 64 90>
Komplexitätsanalyse der Blasensortierung :
Zeitkomplexität: AN2)
Hilfsraum: O(1)
Vorteile der Blasensortierung:
- Die Blasensortierung ist leicht zu verstehen und umzusetzen.
- Es wird kein zusätzlicher Speicherplatz benötigt.
- Es handelt sich um einen stabilen Sortieralgorithmus, was bedeutet, dass Elemente mit demselben Schlüsselwert ihre relative Reihenfolge in der sortierten Ausgabe beibehalten.
Nachteile der Blasensortierung:
- Die Blasensortierung hat eine zeitliche Komplexität von O(N2), was es bei großen Datenmengen sehr langsam macht.
- Bubble Sort ist ein vergleichsbasierter Sortieralgorithmus, was bedeutet, dass ein Vergleichsoperator erforderlich ist, um die relative Reihenfolge der Elemente im Eingabedatensatz zu bestimmen. Dies kann in bestimmten Fällen die Effizienz des Algorithmus einschränken.
Einige FAQs zum Thema Blasensortierung:
Was ist der Grenzfall für die Blasensortierung?
Die Blasensortierung benötigt die minimale Zeit (Reihenfolge von n), wenn die Elemente bereits sortiert sind. Daher ist es am besten, vorher zu prüfen, ob das Array bereits sortiert ist oder nicht, um O(N) zu vermeiden2) Zeitkomplexität.
Erfolgt die Sortierung direkt in der Blasensortierung?
Ja, die Blasensortierung führt den Austausch benachbarter Paare durch, ohne dass eine größere Datenstruktur verwendet wird. Daher ist der Blasensortierungsalgorithmus ein In-Place-Algorithmus.
Ist der Bubble-Sort-Algorithmus stabil?
Ja, der Blasensortierungsalgorithmus ist stabil.
Java xor
Wo wird der Bubble-Sort-Algorithmus verwendet?
Aufgrund seiner Einfachheit wird die Blasensortierung häufig zur Einführung des Konzepts eines Sortieralgorithmus verwendet. In der Computergrafik ist es wegen seiner Fähigkeit beliebt, einen winzigen Fehler (z. B. eine Vertauschung von nur zwei Elementen) in nahezu sortierten Arrays zu erkennen und ihn mit nur linearer Komplexität (2n) zu beheben.
Beispiel: Es wird in einem Polygonfüllalgorithmus verwendet, bei dem Begrenzungslinien nach ihrer x-Koordinate an einer bestimmten Scanlinie (einer Linie parallel zur x-Achse) sortiert werden und sich beim Inkrementieren von y nur ihre Reihenfolge ändert (zwei Elemente werden vertauscht). an Schnittpunkten zweier Geraden.
In Verbindung stehende Artikel:
- Rekursive Blasensortierung
- Codierungspraxis zum Sortieren
- Quiz zum Thema Blasensortierung
- Komplexitätsanalyse der Blasensortierung