Ein weiterer erheblicher Unterschied zwischen den beiden ist, dass die Blasensortierung ein stabiler Algorithmus ist, während die Selektionssortierung ein instabiler Algorithmus ist. Ein Algorithmus gilt als stabil, wobei die Elemente mit demselben Schlüssel in derselben Reihenfolge vorkommen, in der sie vor dem Sortieren in der Liste oder im Array vorkamen. Im Allgemeinen verwenden die meisten stabilen und schnellen Algorithmen zusätzlichen Speicher.
Vergleichstabelle
| Basis zum Vergleich | Blase sortieren | Auswahl sortieren |
|---|---|---|
| Basic | Angrenzendes Element wird verglichen und ausgetauscht | Das größte Element wird ausgewählt und mit dem letzten Element ausgetauscht (bei aufsteigender Reihenfolge). |
| Zeitkomplexität im besten Fall | Auf) | O (n 2 ) |
| Effizienz | Ineffizient | Verbesserte Effizienz im Vergleich zur Blasensortierung |
| Stabil | Ja | Nein |
| Methode | Austauschen | Auswahl |
| Geschwindigkeit | Schleppend | Schnell im Vergleich zur Blasensorte |
Definition von Bubble Sort
Die Blasensortierung ist der einfachste iterative Algorithmus, bei dem jedes Element oder Element mit dem daneben liegenden Element verglichen und bei Bedarf ausgetauscht wird. In einfachen Worten vergleicht es das erste und das zweite Element der Liste und tauscht es aus, sofern sie nicht in einer bestimmten Reihenfolge liegen. In ähnlicher Weise werden das zweite und das dritte Element verglichen und ausgetauscht, und das Vergleichen und Austauschen geht bis zum Ende der Liste. 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äre nach der ersten Iteration an der n-ten Position. 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 Reihenfolge ist) der Bubble-Sortierung liegt in der Reihenfolge n ( O (n) ) und die Worst-Case-Komplexität ist O (n2) . 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 Auswahl Sort
Auswahlsortierung hat eine etwas bessere Leistung erzielt und ist effizienter als ein Blasensortieralgorithmus. Angenommen, wir möchten ein Array in aufsteigender Reihenfolge anordnen, dann funktioniert es, indem es das größte Element findet und es mit dem letzten Element austauscht, und den folgenden Vorgang auf den Unterarrays wiederholen, bis die gesamte Liste sortiert ist.
Hauptunterschiede zwischen Blasensortierung und Auswahlsortierung
- Bei der Blasensortierung wird jedes Element und sein benachbartes Element verglichen und bei Bedarf ausgetauscht. Auf der anderen Seite funktioniert die Auswahlsortierung, indem das Element ausgewählt und das betreffende Element durch das letzte Element ersetzt wird. Das ausgewählte Element kann je nach Reihenfolge am größten oder am kleinsten sein, dh aufsteigend oder absteigend.
- Die Worst-Case-Komplexität ist in beiden Algorithmen gleich, dh O (n2), aber die beste Komplexität ist unterschiedlich. Die Blasensortierung dauert n Zeit, während die Auswahlsortierung n2 Zeit beansprucht.
- Die Blasensortierung ist ein stabiler Algorithmus, die Auswahlsortierung hingegen ist instabil.
- Der Auswahlsortieralgorithmus ist schnell und effizient im Vergleich zur Blasensortierung, die sehr langsam und ineffizient ist.
Fazit
Der Blasensortieralgorithmus wird als der einfachste und ineffizienteste Algorithmus betrachtet, der Auswahlsortieralgorithmus ist jedoch im Vergleich zur Blasensortierung effizient. Die Bubble-Sortierung beansprucht außerdem zusätzlichen Speicherplatz für temporäre Variablen und erfordert weitere Auslagerungen.
