C-Programm für rekursive Einfügungssortierung

Einfügungssortierung ist ein Sortieralgorithmus, der auf einem direkten Vergleich basiert.

Dieser Algorithmus funktioniert, indem er ein Element an einer Position in einem sortierten Subarray platziert, d. h. das Subarray vor dem Element ist das sortierte Subarray.

Algorithmus

Schritt 1 – Schleife von 1 nach n-1 und ausführen –

Schritt 2 .1 – Wählen Sie das Element an Position i, Array[i] aus.

Schritt2.2 – Fügen Sie das Element an seiner Position arr[i] in das sortierte Unterarray array[0] ein.

Lassen Sie uns den Algorithmus anhand eines Beispiels verstehen

array = [34, 7, 12, 90, 51]

Für i = 1, arr[1] = 7, in das Subarray arr [ 0] – Position in arr[1].

[7, 34, 12, 90, 51]

Für i = 2, arr[2] = 12, geben Sie die Position in das Subarray arr[0] - arr[2] ein.

[7, 12, 34, 90, 51]

Für i = 3, arr[3] = 90, platzieren Sie es im Subarray arr[0] - arr[3].

[7, 12, 34, 90, 51]

Für i = 4, arr[4] = 51, platzieren Sie es an der richtigen Position im Subarray arr[0] - arr[4].

[7, 12, 34, 54, 90]

Hier werden wir sehen, wie die rekursive Einfügungssortierung funktioniert. Es funktioniert umgekehrt, d. h. wir rufen rekursiv die Funktion recursiveInsertionSort() auf, um ein Array von n-1 Elementen im Vergleich zur aktuellen Iteration zu sortieren. Dann fügen wir in dem von der Funktion zurückgegebenen sortierten Array das n-te Element an seiner Position im sortierten Array ein.

Das Programm der rekursiven Einfügungssortierung lautet wie folgt:

Beispiel

Demonstration

#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
   if (n <= 1)
      return;
   recursiveInsertionSort( arr, n-1 );
   int nth = arr[n-1];
   int j = n-2;
   while (j >= 0 && arr[j] > nth){
      arr[j+1] = arr[j];
      j--;
   }
   arr[j+1] = nth;
}
int main(){
   int array[] = {34, 7, 12, 90, 51};
   int n = sizeof(array)/sizeof(array[0]);
   printf("Unsorted Array:\t");
      for (int i=0; i < n; i++)
   printf("%d ",array[i]);
      recursiveInsertionSort(array, n);
   printf("</p><p>Sorted Array:\t");
   for (int i=0; i < n; i++)
      printf("%d ",array[i]);
   return 0;
}

Ausgabe

Unsorted Array: 34 7 12 90 51
Sorted Array: 7 12 34 51 90

Das obige ist der detaillierte Inhalt vonC-Programm für rekursive Einfügungssortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!