Die Hauptunterschied zwischen Bubble Sort und Insertion Sort ist das Bubble-Sort führt eine Sortierung durch, indem sie die benachbarten Datenelemente überprüft und sie vertauscht, wenn sie in falscher Reihenfolge sind, während Insertion-Sort die Sortierung durchführt, indem jeweils ein Element in ein teilweise sortiertes Array übertragen wird.

Ein Algorithmus ist eine Abfolge von Schritten zur Lösung eines Problems. Das Sortieren ist ein üblicher Vorgang, der für einen Datensatz ausgeführt wird. Es gibt verschiedene Algorithmen, um einen Datensatz zu sortieren. Zwei davon sind Bubble-Sort und Insertion-Sort. Darüber hinaus werden diese beiden Algorithmen als einfache Sortieralgorithmen betrachtet.

Algorithmus, Blasensortierung, Einfügungssortierung

Was ist Bubble-Sort?

Bubble-Sort ist der einfachste Sortieralgorithmus. Der Algorithmus sortiert die Elemente, indem er die benachbarten Paare gleichzeitig vergleicht.

Betrachten Sie das folgende Beispiel:

40 30 10 70 50 20 60

Bei der Blasensortierung vergleichen wir benachbarte Elemente.

Zuerst betrachten wir 40 und 30. 30 ist kleiner als 40. Also können wir diese beiden Zahlen vertauschen.

30 40 10 70 50 20 60

Jetzt können wir 40 und 10 betrachten. 10 ist kleiner als 40. Also können wir diese beiden Zahlen vertauschen.

30 10 40 70 50 20 60

Jetzt können wir 40 und 70 betrachten. Da 70 größer als 40 ist, müssen die Zahlen nicht vertauscht werden.

Als nächstes betrachten wir 70 und 50. 50 ist kleiner als 70. Also können wir diese beiden Zahlen vertauschen.

30 10 40 50 70 20 60

Dann können wir 70 und 20 betrachten. Da 20 kleiner als 70 ist, können wir diese beiden Elemente austauschen.

30 10 40 50 20 70 60

Jetzt können wir 70 und 60 betrachten. 60 ist kleiner als 70. Daher müssen wir diese beiden Zahlen vertauschen.

30 10 40 50 20 60 70

Nun sehen Sie, dass sich das größte Element im Datensatz jetzt am Ende befindet. Mit anderen Worten, am Ende des ersten Durchgangs ist das größte Element bereits sortiert. Daher müssen wir beim nächsten Mal nicht die 70 berücksichtigen, da sie bereits sortiert sind. Wir müssen nur die anderen sechs Elemente überprüfen.

10 30 40 50 20 60 70

Nun betrachten wir 30 und 40. 40 ist größer als 30. Es besteht keine Notwendigkeit, die Zahlen zu vertauschen. Dann können wir 40 und 50 in Betracht ziehen. Da 50 größer als 40 ist, ist kein Austausch erforderlich.

Betrachten wir nun 50 und 20. 20 ist kleiner als 50. Also tauschen wir diese beiden Zahlen aus.

10 30 40 20 50 60 70

Betrachten Sie nun 50 und 60. Es besteht keine Notwendigkeit zum Vertauschen. Am Ende des zweiten Durchgangs wird das zweitgrößte Element sortiert. Mit anderen Worten, 60 und 70 sind jetzt sortiert. Der Vorgang wird fortgesetzt, bis alle Elemente sortiert sind.

Was ist Einfügungssortierung?

Der Einfügungssortieralgorithmus sortiert den Datensatz, indem er jeweils ein Element in das teilweise sortierte Array überträgt. Somit hat dieser Sortieralgorithmus einen geringen Overhead.

Betrachten Sie das folgende Beispiel:

40 30 10 70 50 20 60

Wir betrachten 40 als das teilweise sortierte Array. Wenn wir 30 betrachten, sind es weniger als 40. Also tauschen wir sie aus. Dann betrachten wir 30 und 40 im teilweise sortierten Array.

30 40 10 70 50 20 60

Nun betrachten wir 10. 10 ist kleiner als 30. Also platzieren wir die Elemente wie unten. 10, 30 und 40 befinden sich im teilweise sortierten Array.

10 30 40 70 50 20 60

Nun betrachten wir 70. Es ist größer als 40, also ist keine Bewegung erforderlich. 10, 30, 40, 70 befinden sich in der teilweise sortierten Anordnung.

Betrachten wir nun 50. Es ist kleiner als 70, aber größer als 40. Wir können sie in die richtige Position bringen. 10, 30, 40, 50, 70 befinden sich nun im teilweise sortierten Array.

10 30 40 50 70 20 60

Betrachten Sie nun 20. Es ist größer als 10, aber kleiner als 20. Wir können es an der richtigen Position platzieren. 10, 20, 30, 40, 50, 70 befinden sich in der teilweise sortierten Anordnung.

10 20 30 40 50 70 60

Betrachten Sie 60. Es ist kleiner als 70, aber größer als 50. Wir können es in die richtige Position bringen.

10 20 30 40 50 60 70

Jetzt können wir sehen, dass alle Elemente sortiert sind. Hier wird die Anzahl der Swaps bei der Einfügungssortierung minimiert, aber die Anzahl der Vergleiche ist immer noch hoch.

Unterschied zwischen Blasensortierung und Einfügungssortierung

Definition

Bubble-Sort ist ein einfacher Sortieralgorithmus, der wiederholt eine Liste durchläuft, benachbarte Paare vergleicht und sie vertauscht, wenn sie in der falschen Reihenfolge sind. Insertion Sort hingegen ist ein einfacher Sortieralgorithmus, der die endgültige sortierte Liste erstellt, indem jeweils ein Element übertragen wird. Dies ist also der Hauptunterschied zwischen Bubble-Sort und Insertion-Sort.

Funktionalität

Während Bubble-Sort die benachbarten Elemente überprüft und entsprechend vertauscht, überträgt Insertion-Sort ein Element nach dem anderen in das teilweise sortierte Array.

Anzahl der Swaps

Auch die Anzahl der Swaps ist ein wichtiger Unterschied zwischen Bubble-Sort und Insertion-Sort. Insertion-Sort hat weniger Swaps als Bubble-Sort.

Geschwindigkeit

Komplexität

Ein weiterer Unterschied zwischen Bubble-Sort und Insertion-Sort besteht darin, dass die Insertion-Sortierung komplexer ist als die Bubble-Sortierung.

Abschluss

Bubble-Sort und Insertion-Sort eignen sich zum Sortieren eines kleinen Datensatzes. Beide haben eine geringere Effizienz im Vergleich zu anderen fortschrittlichen Sortieralgorithmen wie Quicksort und Merge Sort. Der Hauptunterschied zwischen Bubble-Sort und Insertion-Sort besteht darin, dass Bubble-Sort eine Sortierung durchführt, indem sie die benachbarten Datenelemente überprüft und sie vertauscht, wenn sie in falscher Reihenfolge sind, während Insertion-Sort die Sortierung durchführt, indem jeweils ein Element in das teilweise sortierte Array übertragen wird.

Verweise:

1."Blasensortierung." Wikipedia, Wikimedia Foundation, 15. April 2019, hier verfügbar. 2. "Einfügungssortierung". Wikipedia, Wikimedia Foundation, 3. Februar 2019, hier verfügbar. 3.„Was ist eine Einfügungssortierung? – Definition von Techopedia.“ Techopedia.com, hier verfügbar.

Bild mit freundlicher Genehmigung:

1.1.”2816806″ (CC0) über Pixabay