In diesem Artikel besprechen wir den Einfügungssortierungsalgorithmus. Der Arbeitsvorgang der Einfügungssortierung ist ebenfalls einfach. Dieser Artikel wird für Studierende sehr hilfreich und interessant sein, da sie in ihren Prüfungen möglicherweise mit der Einfügesortierung konfrontiert werden. Daher ist es wichtig, das Thema zu diskutieren.

Die Einfügungssortierung funktioniert ähnlich wie das Sortieren von Spielkarten in Händen. Wir gehen davon aus, dass die erste Karte im Kartenspiel bereits sortiert ist, und wählen dann eine unsortierte Karte aus. Wenn die ausgewählte unsortierte Karte größer als die erste Karte ist, wird sie auf der rechten Seite platziert; andernfalls wird es auf der linken Seite platziert. Ebenso werden alle unsortierten Karten genommen und genau an ihren Platz gelegt.

Der gleiche Ansatz wird bei der Einfügungssortierung angewendet. Die Idee hinter der Einfügungssortierung besteht darin, zunächst ein Element zu nehmen und es durch das sortierte Array zu durchlaufen. Obwohl es einfach zu verwenden ist, eignet es sich aufgrund der zeitlichen Komplexität der Einfügungssortierung im Durchschnitt und im schlechtesten Fall nicht für große Datenmengen An²) , wobei n die Anzahl der Elemente ist. Die Einfügungssortierung ist weniger effizient als die anderen Sortieralgorithmen wie Heap-Sortierung, Schnellsortierung, Zusammenführungssortierung usw.

Einfügungssortierung hat verschiedene Vorteile wie:

• Einfache Implementierung
• Effizient für kleine Datensätze
• Adaptiv, d. h. geeignet für Datensätze, die bereits im Wesentlichen sortiert sind.

Sehen wir uns nun den Algorithmus der Einfügungssortierung an.

Algorithmus

Die einfachen Schritte zum Erreichen der Einfügungssortierung sind wie folgt aufgeführt:

Schritt 1 - Wenn das Element das erste Element ist, gehen Sie davon aus, dass es bereits sortiert ist. Rückkehr 1.

Shell-Skript ausführbar machen

Schritt 2 - Wählen Sie das nächste Element aus und speichern Sie es separat in a Schlüssel.

Schritt 3 - Vergleichen Sie nun die Schlüssel mit allen Elementen im sortierten Array.

Schritt 4 - Wenn das Element im sortierten Array kleiner als das aktuelle Element ist, wechseln Sie zum nächsten Element. Andernfalls verschieben Sie größere Elemente im Array nach rechts.

Schritt 5 – Geben Sie den Wert ein.

Schritt 6 – Wiederholen Sie diesen Vorgang, bis das Array sortiert ist.

Funktionsweise des Einfügungssortierungsalgorithmus

Sehen wir uns nun die Funktionsweise des Einfügungssortierungsalgorithmus an.

Um die Funktionsweise des Einfügungssortierungsalgorithmus zu verstehen, nehmen wir ein unsortiertes Array. Anhand eines Beispiels lässt sich die Einfügesortierung leichter verstehen.

Die Elemente des Arrays seien -

Zunächst werden die ersten beiden Elemente bei der Einfügesortierung verglichen.

Hier ist 31 größer als 12. Das bedeutet, dass beide Elemente bereits in aufsteigender Reihenfolge vorliegen. Daher wird 12 vorerst in einem sortierten Unterarray gespeichert.

Gehen Sie nun zu den nächsten beiden Elementen über und vergleichen Sie sie.

Hier ist 25 kleiner als 31. 31 ist also nicht an der richtigen Position. Tauschen Sie nun 31 gegen 25 aus. Neben dem Tauschen überprüft die Einfügungssortierung auch alle Elemente im sortierten Array.

Im Moment hat das sortierte Array nur ein Element, nämlich 12. Daher ist 25 größer als 12. Daher bleibt das sortierte Array nach dem Austausch sortiert.

Nun sind zwei Elemente im sortierten Array 12 und 25. Gehen Sie weiter zu den nächsten Elementen, die 31 und 8 sind.

Sowohl 31 als auch 8 sind nicht sortiert. Also, tauscht sie aus.

Nach dem Austausch sind die Elemente 25 und 8 unsortiert.

Also, tauscht sie aus.

Jetzt sind die Elemente 12 und 8 unsortiert.

Tauschen Sie sie also auch aus.

Das sortierte Array enthält nun drei Elemente mit den Nummern 8, 12 und 25. Gehen Sie zu den nächsten Elementen mit den Nummern 31 und 32.

Daher sind sie bereits sortiert. Das sortierte Array umfasst nun 8, 12, 25 und 31.

Gehen Sie zu den nächsten Elementen 32 und 17.

17 ist kleiner als 32. Also tauschen Sie sie aus.

Durch Vertauschen werden 31 und 17 unsortiert. Tauschen Sie sie also auch aus.

Durch den Austausch werden nun 25 und 17 unsortiert. Führen Sie den Austausch also erneut durch.

Jetzt ist das Array vollständig sortiert.

Komplexität der Einfügungssortierung

Sehen wir uns nun die zeitliche Komplexität der Einfügungssortierung im besten Fall, im Durchschnittsfall und im schlechtesten Fall an. Wir werden auch die räumliche Komplexität der Einfügungssortierung sehen.

1. Zeitkomplexität

Beste Fallkomplexität -Dies geschieht, wenn keine Sortierung erforderlich ist, d. h. das Array bereits sortiert ist. Die Zeitkomplexität der Einfügungssortierung beträgt im besten Fall An) .Durchschnittliche Fallkomplexität -Es tritt auf, wenn die Array-Elemente in einer durcheinandergebrachten Reihenfolge vorliegen, die nicht richtig aufsteigend und nicht richtig absteigend ist. Die durchschnittliche Fallzeitkomplexität der Einfügungssortierung beträgt An²) .Worst-Case-Komplexität -Es tritt auf, wenn die Array-Elemente in umgekehrter Reihenfolge sortiert werden müssen. Angenommen, Sie müssen die Array-Elemente in aufsteigender Reihenfolge sortieren, die Elemente jedoch in absteigender Reihenfolge. Die zeitliche Komplexität der Einfügungssortierung im schlimmsten Fall beträgt An²) .

2. Raumkomplexität

• Die räumliche Komplexität der Einfügungssortierung beträgt O(1). Dies liegt daran, dass bei der Einfügungssortierung eine zusätzliche Variable zum Austauschen erforderlich ist.

Implementierung der Einfügungssortierung

Sehen wir uns nun die Programme zur Einfügungssortierung in verschiedenen Programmiersprachen an.

Programm: Schreiben Sie ein Programm, um die Einfügungssortierung in der Sprache C zu implementieren.

 #include void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 &amp;&amp; temp <= 17 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting are - 
'); printarr(a, n); insert(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-18.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in python.</p> <pre> def insertionSort(a): # Function to implement insertion sort for i in range(1, len(a)): temp = a[i] # Move the elements greater than temp to one position #ahead from their current position j = i-1 while j &gt;= 0 and temp <a[j] : a[j + 1]="a[j]" j="j-1" def printarr(a): # function to print the array for i in range(len(a)): (a[i], end=" " ) a="[70," 15, 2, 51, 60] print('before sorting elements are - ') printarr(a) insertionsort(a) print('
after < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-19.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C++ language.</p> <pre> #include using namespace std; void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 &amp;&amp; temp <= 2 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) cout << a[i] <<' '; main() a[]="{" 89, 45, 35, 8, 12, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting are - '<<endl; printarr(a, n); insert(a, cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-20.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C# language.</p> <pre> using System; class Insertion { static void insert(int[] a) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.Length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 &amp;&amp; temp <= 12 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } static void printarr(int[] a) function print array int i; n="a.Length;" for (i="0;" i < n; i++) console.write(a[i] + ' '); main() int[] a="{" 98, 54, 53, 18, 21, }; console.write('before sorting are - 
'); printarr(a); insert(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-21.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in Java.</p> <pre> public class Insert { void insert(int a[]) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 &amp;&amp; temp <= 22 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[]) function print array int i; n="a.length;" for (i="0;" i < n; i++) system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 92, 50, 5, 20, 11, }; insert i1="new" insert(); system.out.println('
before sorting are - i1.printarr(a); i1.insert(a); system.out.println('

after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-22.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in PHP.</p> <pre> <?php $a = array( 92, 50, 5, 20, 11, 22 ); function printArray($a) { for($i = 0; $i < 6; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>&apos;; printArray($a); for ($i = 1; $i = 0 &amp;&amp; $temp <= $a[$j]) * move the elements greater than temp to one position ahead from their current position* { $a[$j+1]="$a[$j];" $j="$j-1;" } echo ' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </=></pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-23.webp" alt="Insertion Sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm&apos;s complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;>

Ausgabe:

Das ist also alles über den Artikel. Ich hoffe, der Artikel ist hilfreich und informativ für Sie.

Dieser Artikel beschränkte sich nicht nur auf den Algorithmus. Wir haben auch die Komplexität, Funktionsweise und Implementierung des Algorithmus in verschiedenen Programmiersprachen besprochen.