Blasensortierung wird als einer der einfachsten Sortieralgorithmen angesehen, bei dem die benachbarten Elemente wiederholt ausgetauscht werden, wenn sie in der falschen Reihenfolge vorliegen. Mit einem Blasensortierungsalgorithmus können Sie sehen, dass das größte Element (vorausgesetzt, wir sortieren vom kleinsten zum größten) bis zum Anfang der Liste oder des Arrays „sprudelt“.

Beispiel:
Angenommen, wir möchten eine Liste oder ein Array von Elementen in aufsteigender Reihenfolge (vom kleinsten zum größten) sortieren: List = (3,1,2)

Da kein Austausch stattgefunden hat, bedeutet dies, dass es sich um ein Array handelt bereits in aufsteigender Reihenfolge sortiert!

Bester Fall

Versuchen wir nun denselben Algorithmus erneut, diesmal jedoch mit dem Best-Case-Szenario, bei dem die Elemente bereits in der Reihenfolge sortiert sind ( aufsteigend) möchten wir.

Da kein Austausch stattgefunden hat, sind wir fertig und der Algorithmus hat nur 2 Vergleiche und die Anzahl der Elemente im Array durchgeführt, die wir n = 3 nennen. Also können wir das für n sehen Elemente, für die dieser Algorithmus im besten Fall nur n-1 Vergleiche durchführt, n-1 = O (n)

Die von uns verwendete Prozedur oder der Algorithmus ist unten aufgeführt:

Dieser Algorithmus verwendet ein Flag um festzustellen, ob die Elemente ausgetauscht wurden oder nicht Dies ermöglicht, dass der beste Fall des Blasensortierungsalgorithmus O (n) anstelle von O (n²) ist, wie bei einer anderen Implementierung der Blasensortierung.

Der obige Algorithmus
Worst Case = O (n²)
Best Case = O (n)

Schauen wir uns eine andere Implementierung des Blasensortierungsalgorithmus an:

BUBBLESORT(A)
1 for i = 1 to A.length - 1
2 for j = A.length downto i + 1
3 if A < A
4 exchange A with A

Der obige Algorithmus
Worst Case = O (n²)
Best Case = O (n²)

Worst Case

Sortieren wir ein Array oder eine Liste = (3,2,1). Dies wäre der schlimmste Fall, wenn die Liste mit dem obigen Algorithmus in der völlig entgegengesetzten Reihenfolge als gewünscht (in aufsteigender Reihenfolge) vorliegt.

Erster Durchgang:
(3,2,1) – > Vergleichen Sie die Elemente 3 & 2
(2,3) , 1) – > Tauschen Sie 3 & 2 seit 2 < 3
( 2,3,1) – > Vergleichen Sie die Elemente 3 & 1
(2,1,3) – > Tauschen Sie 1 & 3 seit 1 < 3

Zweiter Durchgang:
(2,1,3) – > Vergleichen Sie die Elemente 2 & 1
(1,2,3) – > Tauschen Sie 2 & 1 seit 1 < 2
(1,2,3) – > Vergleichen Sie die Elemente 2 & 3
(1,2,3) – > Kein Umtausch erforderlich seit 2 < 3

Wir haben jetzt beide Schleifen durchlaufen, sodass das Array in aufsteigender Reihenfolge sortiert werden muss.

Beachten Sie, dass wir im obigen zweiten Beispiel 4 Vergleiche durchgeführt haben, und Die Anzahl der Elemente im Array wird ’n‘ = 3 genannt, daher beträgt die Anzahl der durchgeführten Vergleiche (n-1) ² und (n-1) ² = O (n²)

Ein großartiges Buch, das Sie auf das Codieren / Programmieren von Interviews vorbereitet, heißt auch, das Coding-Interview zu knacken. Es wird Ihnen helfen, sich mit Sortieralgorithmen und Problemlösungen vertraut zu machen. Probieren Sie es also unbedingt aus!

Vielen Dank, dass Sie diesen Artikel gelesen haben. Ich hoffe, er ist für Sie alle hilfreich! Machen Sie weiter so und wenn Sie weitere Videos zur Algorithmusanalyse wünschen, besuchen Sie bitte meine YouTube-Kanäle und abonnieren Sie sie (randerson112358 & compsci112358)

Weitere Inhalte / Videos zur Algorithmusanalyse und -programmierung:

YouTube-Kanal:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:

Website:

Video-Tutorials zur Wiederholungsbeziehung:

Video-Tutorial zur Algorithmusanalyse:

Twitter: