DAA - Blasensortierung

Die Blasensortierung ist ein elementarer Sortieralgorithmus, bei dem bei Bedarf wiederholt benachbarte Elemente ausgetauscht werden. Wenn kein Austausch erforderlich ist, wird die Datei sortiert.

Dies ist die einfachste Technik unter allen Sortieralgorithmen.

Algorithm: Sequential-Bubble-Sort (A) 
fori← 1 to length [A] do 
for j ← length [A] down-to i +1 do 
   if A[A] < A[j - 1] then 
      Exchange A[j] ↔ A[j-1]

Implementierung

voidbubbleSort(int numbers[], intarray_size) { 
   inti, j, temp; 
   for (i = (array_size - 1); i >= 0; i--) 
   for (j = 1; j <= i; j++) 
      if (numbers[j - 1] > numbers[j]) { 
         temp = numbers[j-1]; 
         numbers[j - 1] = numbers[j]; 
         numbers[j] = temp; 
      } 
}

Analyse

Hier ist die Anzahl der Vergleiche

1 + 2 + 3 +...+ (n - 1) = n(n - 1)/2 = O(n²)

Die Grafik zeigt deutlich die n² Art der Blasensorte.

Bei diesem Algorithmus ist die Anzahl der Vergleiche unabhängig vom Datensatz, dh ob die bereitgestellten Eingabeelemente in sortierter Reihenfolge oder in umgekehrter Reihenfolge oder zufällig sind.

Speicherbedarf

Aus dem oben angegebenen Algorithmus geht hervor, dass die Blasensortierung keinen zusätzlichen Speicher benötigt.

Beispiel

Unsorted list:

5 2 1 4 3 7 6

1 ^st Iteration:

5 > 2 swap	2 5 1 4 3 7 6
5 > 1 swap	2 1 5 4 3 7 6
5 > 4 swap	2 1 4 5 3 7 6
5 > 3 swap	2 1 4 3 5 7 6
5 < 7 no swap	2 1 4 3 5 7 6
7 > 6 swap	2 1 4 3 5 6 7

2 ^nd Iteration:

2 > 1 swap	1 2 4 3 5 6 7
2 < 4 no swap	1 2 4 3 5 6 7
4 > 3 swap	1 2 3 4 5 6 7
4 < 5 no swap	1 2 3 4 5 6 7
5 < 6 no swap	1 2 3 4 5 6 7

Es gibt keine Änderung in 3 ^rd , 4 ^th , 5 ^th und 6 - ^ten Iteration.

Schließlich,

the sorted list is

1 2 3 4 5 6 7