Datenstruktur - Blasensortierungsalgorithmus

Die Blasensortierung ist ein einfacher Sortieralgorithmus. Dieser Sortieralgorithmus ist ein vergleichsbasierter Algorithmus, bei dem jedes Paar benachbarter Elemente verglichen wird und die Elemente ausgetauscht werden, wenn sie nicht in Ordnung sind. Dieser Algorithmus ist nicht für große Datenmengen geeignet, da seine durchschnittliche und Worst-Case-Komplexität Ο (n ² ) beträgt, wobein ist die Anzahl der Elemente.

Wie funktioniert die Blasensortierung?

Wir nehmen ein unsortiertes Array für unser Beispiel. Die Blasensortierung dauert Ο (n ² ), daher halten wir sie kurz und präzise.

Die Blasensortierung beginnt mit den ersten beiden Elementen und vergleicht sie, um zu überprüfen, welches größer ist.

In diesem Fall ist der Wert 33 größer als 14, sodass er sich bereits an sortierten Stellen befindet. Als nächstes vergleichen wir 33 mit 27.

Wir stellen fest, dass 27 kleiner als 33 ist und diese beiden Werte ausgetauscht werden müssen.

Das neue Array sollte so aussehen -

Als nächstes vergleichen wir 33 und 35. Wir stellen fest, dass sich beide in bereits sortierten Positionen befinden.

Dann gehen wir zu den nächsten beiden Werten, 35 und 10.

Wir wissen dann, dass 10 kleiner ist 35. Daher sind sie nicht sortiert.

Wir tauschen diese Werte aus. Wir stellen fest, dass wir das Ende des Arrays erreicht haben. Nach einer Iteration sollte das Array folgendermaßen aussehen:

Um genau zu sein, zeigen wir jetzt, wie ein Array nach jeder Iteration aussehen sollte. Nach der zweiten Iteration sollte es so aussehen -

Beachten Sie, dass sich nach jeder Iteration am Ende mindestens ein Wert bewegt.

Und wenn kein Tausch erforderlich ist, erfährt die Blasensortierung, dass ein Array vollständig sortiert ist.

Nun sollten wir uns einige praktische Aspekte der Blasensortierung ansehen.

Algorithmus

Wir nehmen an list ist ein Array von nElemente. Wir gehen weiter davon ausswap Funktion tauscht die Werte der angegebenen Array-Elemente aus.

begin BubbleSort(list)

   for all elements of list
      if list[i] > list[i+1]
         swap(list[i], list[i+1])
      end if
   end for
   
   return list
   
end BubbleSort

Pseudocode

Wir beobachten im Algorithmus, dass Bubble Sort jedes Paar von Array-Elementen vergleicht, es sei denn, das gesamte Array ist vollständig in aufsteigender Reihenfolge sortiert. Dies kann zu einigen Komplexitätsproblemen führen, z. B. wenn das Array nicht mehr ausgetauscht werden muss, da alle Elemente bereits aufsteigend sind.

Um das Problem zu beheben, verwenden wir eine Flag-Variable swappedDies hilft uns zu sehen, ob ein Tausch stattgefunden hat oder nicht. Wenn kein Austausch stattgefunden hat, dh das Array keine weitere Verarbeitung zum Sortieren erfordert, wird es aus der Schleife herauskommen.

Der Pseudocode des BubbleSort-Algorithmus kann wie folgt geschrieben werden:

procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

Implementierung

Ein weiteres Problem, das wir in unserem ursprünglichen Algorithmus und seinem improvisierten Pseudocode nicht angesprochen haben, ist, dass sich nach jeder Iteration die höchsten Werte am Ende des Arrays einstellen. Daher muss die nächste Iteration keine bereits sortierten Elemente enthalten. Zu diesem Zweck beschränken wir in unserer Implementierung die innere Schleife, um bereits sortierte Werte zu vermeiden.

Klicken Sie hier , um mehr über die Implementierung der Blasensortierung in der Programmiersprache C zu erfahren .