Sortieren durch Einfügen ist ein einfacher Sortieralgorithmus, der durch iteratives Einfügen jedes Elements einer unsortierten Liste an der richtigen Position in einem sortierten Teil der Liste funktioniert. es ist ein stabile Sortierung Algorithmus, was bedeutet, dass Elemente mit gleichen Werten ihre relative Reihenfolge in der sortierten Ausgabe beibehalten.

Sortieren durch Einfügen ist, als würde man Spielkarten in den Händen sortieren. Sie teilen die Karten in zwei Gruppen auf: die sortierten Karten und die unsortierten Karten. Anschließend wählt man eine Karte aus der unsortierten Gruppe aus und legt sie an der richtigen Stelle in der sortierten Gruppe ab.

Einfügesortieralgorithmus:

Sortieren durch Einfügen ist ein einfacher Sortieralgorithmus, bei dem ein sortiertes Array Element für Element erstellt wird. Es gilt als an Ort und Stelle Sortieralgorithmus, was bedeutet, dass kein zusätzlicher Speicherplatz über das ursprüngliche Array hinaus erforderlich ist.

Algorithmus:

Um eine Einfügungssortierung zu erreichen, führen Sie die folgenden Schritte aus:

Katrina Kaif

• Wir müssen mit dem zweiten Element des Arrays beginnen, da davon ausgegangen wird, dass das erste Element im Array sortiert ist.
• Vergleichen Sie das zweite Element mit dem ersten Element und prüfen Sie, ob das zweite Element kleiner ist, und tauschen Sie sie dann aus.
• Gehen Sie zum dritten Element und vergleichen Sie es mit dem zweiten Element, dann mit dem ersten Element und tauschen Sie es nach Bedarf aus, um es an der richtigen Position zwischen den ersten drei Elementen zu platzieren.
• Setzen Sie diesen Vorgang fort, vergleichen Sie jedes Element mit den vorherigen und tauschen Sie es nach Bedarf aus, um es an der richtigen Position zwischen den sortierten Elementen zu platzieren.
• Wiederholen Sie diesen Vorgang, bis das gesamte Array sortiert ist.

Funktionsweise des Einfügungssortierungsalgorithmus:

Betrachten Sie ein Array mit Elementen : {23, 1, 10, 5, 2}

Erster Pass:

• Aktuelles Element ist 23
• Es wird davon ausgegangen, dass das erste Element im Array sortiert ist.
• Der sortierte Teil bis 0 Index ist: [23]

Zweiter Durchgang:

• Vergleichen 1 mit 23 (aktuelles Element mit dem sortierten Teil).
• Seit 1 kleiner ist, einfügen 1 Vor 23 .
• Der sortierte Teil bis 1 Index ist: [1, 23]

Dritter Durchgang:

• Vergleichen 10 mit 1 Und 23 (aktuelles Element mit dem sortierten Teil).
• Seit 10 ist größer als 1 und kleiner als 23 , einfügen 10 zwischen 1 Und 23 .
• Der sortierte Teil bis 2 Index ist: [1, 10, 23]

Vierter Durchgang:

• Vergleichen 5 mit 1 , 10 , Und 23 (aktuelles Element mit dem sortierten Teil).
• Seit 5 ist größer als 1 und kleiner als 10 , einfügen 5 zwischen 1 Und 10 .
• Der sortierte Teil bis 3 Index ist : [1, 5, 10, 23]

Fünfter Durchgang:

• Vergleichen 2 mit 1, 5, 10 , Und 23 (aktuelles Element mit dem sortierten Teil).
• Seit 2 ist größer als 1 und kleiner als 5 einfügen 2 zwischen 1 Und 5 .
• Der sortierte Teil bis 4 Index ist: [1, 2, 5, 10, 23]

Endgültiges Array:

• Das sortierte Array ist: [1, 2, 5, 10, 23]

Implementierung der Einfügungssortierung:

// C++ program for insertion sort #include  using namespace std; // Function to sort an array using // insertion sort void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,   // to one position ahead of their  // current position  while (j>= 0 && arr[j]> key) { arr[j + 1] = arr[j];  j = j – 1;  } arr[j + 1] = key;  } } // Eine Hilfsfunktion zum Drucken eines Arrays // der Größe n void printArray(int arr[], int n) { int i;  für (i = 0; i< n; i++)  cout << arr[i] << ' ';  cout << endl; } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int N = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, N);  printArray(arr, N);  return 0; } // This is code is contributed by rathbhupendra>

// C program for insertion sort #include  #include  /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> key) { arr[j + 1] = arr[j];  j = j – 1;  } arr[j + 1] = key;  } } // Eine Hilfsfunktion zum Drucken eines Arrays der Größe n void printArray(int arr[], int n) { int i;  für (i = 0; i< n; i++)  printf('%d ', arr[i]);  printf('
'); } /* Driver program to test insertion sort */ int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int n = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, n);  printArray(arr, n);  return 0; }>

// Java program for implementation of Insertion Sort public class InsertionSort {  /*Function to sort array using insertion sort*/  void sort(int arr[])  {  int n = arr.length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> key) { arr[j + 1] = arr[j];  j = j – 1;  } arr[j + 1] = key;  } } /* Eine Hilfsfunktion zum Drucken eines Arrays der Größe n*/ static void printArray(int arr[]) { int n = arr.length;  für (int i = 0; i< n; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver method  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } }; /* This code is contributed by Rajat Mishra. */>

# Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j>= 0 und Schlüssel< arr[j] : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)): print ('% d' % arr[i]) # This code is contributed by Mohit Kumra>

// C# program for implementation of Insertion Sort using System; class InsertionSort {  // Function to sort array  // using insertion sort  void sort(int[] arr)  {  int n = arr.Length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,  // to one position ahead of  // their current position  while (j>= 0 && arr[j]> key) { arr[j + 1] = arr[j];  j = j – 1;  } arr[j + 1] = key;  } } // Eine Dienstprogrammfunktion zum Drucken // eines Arrays der Größe n static void printArray(int[] arr) { int n = arr.Length;  für (int i = 0; i< n; ++i)  Console.Write(arr[i] + ' ');  Console.Write('
');  }  // Driver Code  public static void Main()  {  int[] arr = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } } // This code is contributed by ChitraNayal.>

>

 // PHP program for insertion sort // Function to sort an array // using insertion sort function insertionSort(&$arr, $n) { for ($i = 1; $i < $n; $i++) { $key = $arr[$i]; $j = $i-1; // Move elements of arr[0..i-1], // that are greater than key, to  // one position ahead of their  // current position while ($j>= 0 && $arr[$j]> $key) { $arr[$j + 1] = $arr[$j]; $j = $j - 1; } $arr[$j + 1] = $key; } } // Eine Hilfsfunktion zum // Drucken eines Arrays der Größe n function printArray(&$arr, $n) { for ($i = 0; $i< $n; $i++) echo $arr[$i].' '; echo '
'; } // Driver Code $arr = array(12, 11, 13, 5, 6); $n = sizeof($arr); insertionSort($arr, $n); printArray($arr, $n); // This code is contributed by ChitraNayal. ?>>

5 6 11 12 13>

Zeitkomplexität: O(N^2)
Hilfsraum: O(1)

Komplexitätsanalyse der Einfügungssortierung :

Zeitkomplexität der Einfügungssortierung

• I'm besten fall: An) , Wenn die Liste bereits sortiert ist, wobei n die Anzahl der Elemente in der Liste ist.
• Durchschnittlicher Fall: An ² ) , Wenn die Liste zufällig geordnet ist
• Schlimmsten Fall: An ² ) , Wenn die Liste in umgekehrter Reihenfolge ist

Weltraumkomplexität der Einfügungssortierung

• Hilfsraum: O(1), Einfügungssortierung erforderlich O(1) zusätzlicher Platz, was ihn zu einem platzsparenden Sortieralgorithmus macht.

Vorteile der Einfügungssortierung:

• Einfach und leicht umzusetzen.
• Stabiler Sortieralgorithmus.
• Effizient für kleine Listen und nahezu sortierte Listen.
• Platzsparend.

Nachteile der Einfügungssortierung:

• Ineffizient für große Listen.
• In den meisten Fällen nicht so effizient wie andere Sortieralgorithmen (z. B. Zusammenführungssortierung, Schnellsortierung).

Anwendungen der Einfügungssortierung:

Einfügungssortierung wird häufig in Situationen verwendet, in denen:

• Die Liste ist klein oder nahezu sortiert.
• Einfachheit und Stabilität sind wichtig.

Häufig gestellte Fragen zur Einfügungssortierung

Q1. Was sind die Grenzfälle des Insertion-Sort-Algorithmus?

Die Einfügungssortierung nimmt die maximale Sortierzeit in Anspruch, wenn Elemente in umgekehrter Reihenfolge sortiert werden. Und es dauert minimal (Reihenfolge von n), wenn die Elemente bereits sortiert sind.

Q2. Was ist das algorithmische Paradigma des Insertion-Sort-Algorithmus?

Schalten Sie den Entwicklermodus aus

Der Insertion-Sort-Algorithmus folgt einem inkrementellen Ansatz.

Q3. Ist Insertion Sort ein In-Place-Sortieralgorithmus?

Ja, die Einfügungssortierung ist ein In-Place-Sortieralgorithmus.

Q4. Ist Insertion Sort ein stabiler Algorithmus?

Ja, die Einfügungssortierung ist ein stabiler Sortieralgorithmus.

F5. Wann wird der Insertion-Sort-Algorithmus verwendet?

Die Einfügungssortierung wird verwendet, wenn die Anzahl der Elemente gering ist. Dies kann auch nützlich sein, wenn das Eingabearray fast sortiert ist und nur wenige Elemente in einem komplett großen Array falsch platziert sind.