Inhalt

• Vergleichstabelle
• Definition von Bubble Sort
• Definition der Auswahlsortierung
• Fazit

Das Sortieren ist eine der Hauptaufgaben in Computerprogrammen, in denen die Elemente eines Arrays in einer bestimmten Reihenfolge angeordnet sind. Sortieren erleichtert die Suche. Blasensortierung und Auswahlsortierung sind die Sortieralgorithmen, die sich durch die Methoden unterscheiden lassen, die sie zum Sortieren verwenden. Die Blasensortierung tauscht im Wesentlichen die Elemente aus, während die Auswahlsortierung die Sortierung durch Auswahl des Elements durchführt.

Ein weiterer wesentlicher Unterschied zwischen den beiden besteht darin, dass die Blasensortierung ein stabiler Algorithmus ist, während die Auswahlsortierung ein instabiler Algorithmus ist. Ein Algorithmus gilt als stabil, wenn die Elemente mit demselben Schlüssel in derselben Reihenfolge wie vor dem Sortieren in der Liste oder dem Array vorkommen. Im Allgemeinen verwenden die meisten stabilen und schnellen Algorithmen zusätzlichen Speicher.

1. Vergleichstabelle
2. Definition
3. Hauptunterschiede
4. Fazit

Vergleichstabelle

Vergleichsbasis	Blase sortieren	Auswahl sortieren
Basic	Das benachbarte Element wird verglichen und ausgetauscht	Das größte Element wird ausgewählt und mit dem letzten Element ausgetauscht (bei aufsteigender Reihenfolge).
Beste Fallzeitkomplexität	Auf)	Auf2)
Effizienz	Ineffizient	Verbesserte Effizienz im Vergleich zur Blasensorte
Stabil	Ja	Nein
Methode	Austausch	Auswahl
Geschwindigkeit	Schleppend	Schnell im Vergleich zur Blasensorte

Definition von Bubble Sort

Blase sortieren ist der einfachste iterative Algorithmus, bei dem jedes Element mit dem daneben befindlichen Element verglichen und bei Bedarf ausgetauscht wird. Mit einfachen Worten, es vergleicht das erste und das zweite Element der Liste und tauscht es aus, sofern sie nicht in einer bestimmten Reihenfolge vorliegen. In ähnlicher Weise werden das zweite und das dritte Element verglichen und vertauscht, und das Vergleichen und Vertauschen wird bis zum Ende der Liste fortgesetzt. Die Anzahl der Vergleiche in der ersten Iteration beträgt n-1, wobei n die Anzahl der Elemente in einem Array ist. Das größte Element würde sich nach der ersten Iteration an der n-ten Position befinden. Und nach jeder Iteration nimmt die Anzahl der Vergleiche ab und bei der letzten Iteration findet nur ein Vergleich statt.

Dieser Algorithmus ist der langsamste Sortieralgorithmus. Die Best-Case-Komplexität (wenn die Liste in der Reihenfolge ist) der Bubble-Sortierung ist in der Reihenfolge n (Auf)), und die Komplexität im schlimmsten Fall ist Auf²). Im besten Fall ist es von der Ordnung n, weil es nur die Elemente vergleicht und sie nicht vertauscht. Diese Technik erfordert auch zusätzlichen Speicherplatz zum Speichern der temporären Variablen.

Definition der Auswahlsortierung

Auswahl sortieren hat eine etwas bessere Leistung erzielt und ist effizienter als der Blasensortierungsalgorithmus. Angenommen, wir möchten ein Array in aufsteigender Reihenfolge anordnen, dann funktioniert es, indem wir das größte Element suchen und mit dem letzten Element austauschen. Wiederholen Sie den folgenden Vorgang für die Unterarrays, bis die gesamte Liste sortiert ist.

Bei der Auswahlsortierung macht das sortierte und unsortierte Array keinen Unterschied und belegt eine Reihenfolge von n² (Auf²)) sowohl im besten als auch im schlimmsten Fall. Die Auswahlsortierung ist schneller als die Blasensortierung.

1. Bei der Bubble-Sortierung wird jedes Element und sein benachbartes Element verglichen und bei Bedarf ausgetauscht. Andererseits funktioniert die Auswahlsortierung, indem das Element ausgewählt und dieses bestimmte Element durch das letzte Element ersetzt wird. Das ausgewählte Element kann abhängig von der Reihenfolge, d. H. Aufsteigend oder absteigend, am größten oder am kleinsten sein.
2. Die Komplexität im ungünstigsten Fall ist bei beiden Algorithmen gleich, d. H. O (n²), aber die beste Komplexität ist anders. Die Blasensortierung benötigt eine Ordnung von n Zeit, während die Auswahlsortierung eine Ordnung von n benötigt² Zeit.
3. Die Blasensortierung ist ein stabiler Algorithmus, während die Auswahlsortierung instabil ist.
4. Der Auswahlsortierungsalgorithmus ist schnell und effizient im Vergleich zur Blasensortierung, die sehr langsam und ineffizient ist.

Fazit

Der Blasensortierungsalgorithmus wird als der einfachste und ineffizienteste Algorithmus angesehen, der Auswahlsortierungsalgorithmus ist jedoch im Vergleich zur Blasensortierung effizient. Die Blasensortierung verbraucht außerdem zusätzlichen Speicherplatz zum Speichern temporärer Variablen und benötigt mehr Auslagerungen.