Programme C pour le tri par insertion récursive

Le tri par insertion est un algorithme de tri basé sur une comparaison sur place.

Cet algorithme fonctionne en plaçant un élément à une position dans un sous-tableau trié, c'est-à-dire que le sous-tableau avant l'élément est le sous-tableau trié.

Algorithme

Étape 1 - Bouclez de 1 à n-1 et exécutez -

Étape 2 .1 - Sélectionnez l'élément à la position i, tableau[i].

Étape 2.2 - Insérez l'élément dans le sous-tableau trié tableau[0] à sa position arr[i].

Comprenons l'algorithme à travers un exemple

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

Pour i = 1, arr[1] = 7, mettre dans le sous-tableau arr [ 0] - Position dans l'arr[1].

[7, 34, 12, 90, 51]

Pour i = 2, arr[2] = 12, mettez la position dans le sous-tableau arr[0] - arr[2].

[7, 12, 34, 90, 51]

Pour i = 3, arr[3] = 90, placez-le dans le sous-tableau arr[0] - arr[3].

[7, 12, 34, 90, 51]

Pour i = 4, arr[4] = 51, placez-le dans la bonne position dans le sous-tableau arr[0] - arr[4].

[7, 12, 34, 54, 90]

Ici, nous verrons comment fonctionne le tri par insertion récursive. Cela fonctionne de la manière inverse, c'est-à-dire que nous appellerons récursivement la fonction recursiveInsertionSort() pour trier un tableau de n-1 éléments par rapport à l'itération actuelle. Ensuite, dans le tableau trié renvoyé par la fonction, nous insérons le nième élément à sa position dans le tableau trié.

Le programme de tri par insertion récursive est le suivant :

Exemple

Démonstration

#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;
}

Sortie

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!