Hauptunterschied – Einfügesortierung vs. Auswahlsortierung
Einfügungssortierung und Auswahlsortierung sind zwei Sortieralgorithmen, die verwendet werden, um eine Sammlung von Daten zu sortieren. Manchmal ist es notwendig, Daten in einer bestimmten Reihenfolge anzuordnen. Sortieralgorithmen sind Mechanismen zum Sortieren einer Menge von Daten. Beim Sortieren werden die Daten nach einer numerischen oder einer lexikografischen Ordnung geordnet. Wenn die Daten richtig sortiert sind, ist es einfach, Daten schneller zu durchsuchen. Wenn die Telefonnummern in einem Telefonverzeichnis nicht sortiert sind, dann wäre es schwierig, eine bestimmte Telefonnummer zu finden. Wenn die Wörter im Wörterbuch nicht in alphabetischer Reihenfolge angeordnet sind, wäre es auf die gleiche Weise sehr schwierig, Wörter zu finden. Daher ist das Sortieren im täglichen Leben nützlich. In der Informatik gibt es Sortieralgorithmen, um eine Sammlung von Daten zu sortieren. Zwei solche Algorithmen sind Insertion Sort und Selection Sort. Die Einfügungssortierung ist der Sortieralgorithmus, der das Array sortiert, indem Elemente einzeln verschoben werden. Die Auswahlsortierung ist der Sortieralgorithmus, der das kleinste Element im Array findet und das Element mit der ersten Position austauscht, dann das zweitkleinste Element findet und es mit dem Element an der zweiten Position austauscht und den Prozess fortsetzt, bis das gesamte Array sortiert ist. Der Hauptunterschied zwischen der Einfügungssortierung und der Auswahlsortierung besteht darin, dass die Einfügungssortierung zwei Elemente gleichzeitig vergleicht, während die Auswahlsortierung das kleinste Element aus dem gesamten Array auswählt und sortiert.
Was ist Insertion Sort?
Insertion Sort ist ein vergleichsbasierter Sortieralgorithmus. Bei dieser Methode wird das Array Schritt für Schritt durchsucht. Die unsortierten Elemente werden verschoben und in die sortierte Unterliste des Arrays eingefügt. Der Insertion-Sort-Algorithmus lässt sich anhand des folgenden Beispiels erläutern.
Nehmen Sie zum Beispiel das anfängliche Array als 77, 33, 44, 11, 88. Bei diesem Sortieralgorithmus besteht der erste Schritt darin, das aktuelle Element auszuwählen.
Das aktuelle Element ist 77. Das aktuelle Element wird mit allen Elementen auf der linken Seite verglichen. Die 77 ist das erste Element und es gibt keine Elemente auf der linken Seite. Der Index der aktuellen Position ist 0.
Dann wird der Index der aktuellen Position um 1 erhöht. Jetzt ist der Index 1 und das aktuelle Element ist 33. Beim Vergleich mit dem Element links ist es kleiner als 77. Dann beide Werte sind vertauscht. Jetzt ist 33 in Index 0 und 77 in Index 1.
Jetzt ist das Array 33, 77, 44, 11, 88.
Erneut wird der Index inkrementiert. Der Index ist 2 und das aktuelle Element ist 44. Es wird mit den Elementen auf der linken Seite verglichen. 44 ist kleiner als 77. Diese beiden Werte werden also vertauscht. Jetzt ist das Array 33, 44, 77, 11, 88. Es ist notwendig, alle Elemente auf der linken Seite zu vergleichen. Die 44 wird also mit 33 verglichen. 33 ist kleiner als 44. Diese Elemente müssen also nicht ausgetauscht werden.
Jetzt ist das Array 33, 44, 77, 11, 88.
Erneut wird der Index inkrementiert. Der Index ist 3 und das aktuelle Element ist 11. Es wird mit allen Elementen auf der linken Seite verglichen. 11 ist weniger als 77, also werden diese beiden vertauscht. Jetzt ist das Array 33, 44, 11, 77, 88. Beim Vergleich von 11 und 44 ist 11 kleiner als 44. Diese beiden werden also vertauscht. Jetzt sind die Arrays 33, 11, 44, 77, 88. Wieder wird 11 mit 33 verglichen. 11 ist kleiner als 33, also werden diese beiden Werte vertauscht.
Jetzt ist das Array 11, 33, 44, 77, 88.
Durch das Erhöhen des Index wird der Index auf 4 gesetzt. Der Wert ist 88. Er ist höher als 77. Es besteht also keine Notwendigkeit zum Austauschen. Schließlich ist das sortierte Array 11, 33, 44, 77, 88.
Abbildung 01: Einfügungssortierbeispiel
Die Implementierung der Einfügungssortierung ist wie oben. Das anfängliche Array war 77, 33, 44, 11, 88. Nach dem Sortieren ergibt es die Ausgabe 11, 33, 44, 77, 88.
Was ist Selection Sort?
Selection Sort ist ein vergleichsbasierter Sortieralgorithmus. Die Arrays sind in Abschnitte unterteilt. Der sortierte Teil befindet sich am linken Ende. Der unsortierte Teil befindet sich am rechten Ende. Zuerst sollte der kleinste Wert gefunden werden. Dann wird es mit dem linken Element vertauscht. Jetzt befindet sich dieses Element im sortierten Array. Dieser Prozess setzt das Verschieben der unsortierten Array-Grenze von einem Element nach rechts fort. Der Selection-Sort-Algorithmus lässt sich anhand des folgenden Beispiels erläutern.
Nehmen Sie zum Beispiel das anfängliche Array als 77, 33, 44, 11, 88, 22. Bei diesem Sortieralgorithmus wird das kleinste im Array gefunden. Das kleinste Element ist 11. Es wird mit dem Element im Index 0 des Arrays vertauscht.
Jetzt ist das Array 11, 33, 44, 77, 88, 22.
Das kleinste Element steht im Index 0, also wird jetzt 11 sortiert. Von den restlichen Elementen ist das kleinste 22. Es wird mit dem Indexelement 1st vertauscht.
Jetzt ist das Array 11, 22, 44, 77, 88, 33.
Die Elemente 11 und 22 sind bereits sortiert. Von den übrigen ist der kleinste Wert 33. Er wird mit dem Indexelement 2nd vertauscht.
Jetzt ist das Array 11, 22, 33, 77, 88, 44.
Die Elemente 11, 22 und 33 sind bereits sortiert. Von den übrigen ist der kleinste Wert 44. Er wird mit dem Indexelement 3rd vertauscht.
Jetzt ist das Array 11, 22, 33, 44, 88, 66.
Die Elemente 11, 22, 33, 44 sind bereits sortiert. Die restlichen Elemente sind 88 und 66. Das Element 66 wird mit dem Indexelement 4th vertauscht.
Jetzt ist das Array 11, 22, 33, 44, 66, 88.
Es ist das sortierte Array, das den Auswahlsortieralgorithmus verwendet.
Abbildung 02: Auswahlsortierbeispiel
Die Implementierung der Einfügungssortierung ist wie oben. Das anfängliche Array war 77, 33, 44, 11, 88. Nach dem Sortieren ergibt es die Ausgabe 11, 33, 44, 77, 88.
Was ist die Ähnlichkeit zwischen Insertion Sort und Selection Sort?
Sowohl Insertion Sort als auch Selection Sort sind Sortieralgorithmen
Was ist der Unterschied zwischen Insertion Sort und Selection Sort?
Einfügungssortierung vs. Auswahlsortierung |
|
| Die Einfügungssortierung ist der Sortieralgorithmus, der das Array sortiert, indem er die Elemente einzeln verschiebt. | Die Auswahlsortierung ist der Sortieralgorithmus, der das kleinste Element im Array findet und das Element mit der ersten Position austauscht, dann das zweitkleinste Element findet und es mit dem Element an der zweiten Position austauscht und den Prozess bis fortsetzt das gesamte Array ist sortiert. |
| Bearbeiten | |
| Die Einfügungssortierung dient dazu, die Unterliste zu sortieren, indem zwei Elemente verglichen werden, bis das gesamte Array sortiert ist. | Die Auswahlsortierung wählt das kleinste Element aus und tauscht es mit der ersten Position aus, wählt erneut das kleinste Element für den Rest aus und tauscht es gegen die zweite Position aus und setzt diesen Vorgang bis zum Ende fort. |
| Stabilität | |
| Insertionsort ist ein stabiler Sortieralgorithmus. | Auswahlsortierung ist kein stabiler Sortieralgorithmus. |
Zusammenfassung – Einfügesortierung vs. Auswahlsortierung
Manchmal ist es notwendig, Daten zu sortieren. In der Informatik gibt es Algorithmen zum Sortieren von Daten. In diesem Artikel wurden die beiden Sortieralgorithmen besprochen, nämlich Insertion Sort und Selection Sort. Die Einfügungssortierung ist der Sortieralgorithmus, der das Array sortiert, indem Elemente einzeln verschoben werden. Die Auswahlsortierung ist der Sortieralgorithmus, der das kleinste Element im Array findet und das Element mit der ersten Position austauscht, dann das zweitkleinste Element findet und es mit dem Element an der zweiten Position austauscht und den Prozess fortsetzt, bis das gesamte Array sortiert ist. Der Unterschied zwischen der Einfügungssortierung und der Auswahlsortierung besteht darin, dass die Einfügungssortierung zwei Elemente gleichzeitig vergleicht, während die Auswahlsortierung das kleinste Element aus dem gesamten Array auswählt und sortiert.
Laden Sie das PDF von Insertion Sort vs. Selection Sort herunter
Sie können die PDF-Version dieses Artikels herunterladen und gemäß Zitationshinweis für Offline-Zwecke verwenden. Bitte laden Sie die PDF-Version hier herunter: Unterschied zwischen Insertion Sort und Selection Sort
