Programme C pour le tri récursif à bulles

Le tri à bulles est l'un des algorithmes de tri les plus simples utilisés pour trier les données en comparant les éléments adjacents. Tous les éléments sont comparés par étapes. La première étape place la plus grande valeur à la fin, la deuxième étape place le deuxième plus grand élément à l'avant-dernière position, et ainsi de suite jusqu'à ce que la liste complète soit triée.

Algorithme de tri à bulles

• int arr[5]= { 5,4,2,1,3 };

• int i, j ;

• Traverse de l'index i=0 à i

  • Traverse de l'index j=0 à la taille du tableau - i - 1

  • Si arr[i]>arr[j] Échangez arr[i] avec arr[j]

• Fin

Tri récursif à bulles

• Si la longueur du tableau est de 1, retournez

• Parcourez le tableau une fois, fixez l'élément maximum à la fin​​p>

• Le reste des étapes est exécuté de manière récursive sauf la dernière element Array

Exemple

Entrée − Arr[] = {5,7,2,3, 1,4}; longueur=6

Sortie − Tableau trié : 1 2 3 4 5 7

Description −

First Pass
5 7 2 3 1 4 → swap → 5 2 7 3 1 4
5 2 7 3 1 4 → swap → 5 2 3 7 1 4
5 2 3 7 1 4 → swap → 5 2 3 1 7 4
5 2 3 1 7 4 → swap → 5 2 3 1 4 7
Second Pass
5 2 3 1 4 7 → swap → 2 5 3 1 4 7
2 5 3 1 4 7 → swap → 2 3 5 1 4 7
2 3 5 1 4 7 → swap → 2 3 1 5 4 7
2 3 1 5 4 7 → swap → 2 3 1 4 5 7
Third Pass
2 3 1 4 5 7 → swap → 2 1 3 4 5 7
2 1 3 4 5 7 no swap
Fourth Pass
2 1 3 4 5 7 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 no swap in further iterations

Input− Arr[] = { 1, 2, 3, 3, 2 };

Output− Tableau trié : 1 2 2 3 3

Description -

First Pass
1 2 3 3 2 → swap → 1 2 3 2 3
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 no swap in further iterations
Second Pass
1 2 2 3 3 no swap in further iterations

La méthode utilisée dans le programme ci-dessous est la suivante

Dans la méthode récursive de tri à bulles, la situation de base est la longueur du tableau = 1. Sinon, utilisez une seule boucle for pour parcourir le tableau et échanger les éléments en conséquence.

• Prenez le tableau d'entrée Arr[] et la longueur comme nombre d'éléments qu'il contient.

• La fonction recurbublSort(int arr[], int len) obtient le tableau et sa longueur, et utilise le tri à bulles pour trier le tableau de manière récursive.

• Obtenez la température variable.

Si la longueur du tableau est 1, void est renvoyé.

• Sinon, utilisez une seule boucle for pour parcourir le tableau et pour chaque élément arr[i]>arr[i+1], échangez les éléments.

• Définissez temp=arr[i], arr[i]=arr[i+1] et arr[i+1]=temp.

• Diminuez maintenant la longueur de 1 car la boucle précédente plaçait le plus grand élément à la dernière position.

• Appelez récursivement recurbublSort(arr,len).

• A la fin de tous les appels, lorsque len devient 1, nous quittons la récursion et trions le tableau.

• Imprimez le tableau trié dans main.

Exemple

#include <stdio.h>
void recurbublSort(int arr[], int len){
   int temp;

   if (len == 1){
      return;
   }
   for (int i=0; i<len-1; i++){
      if (arr[i] > arr[i+1]){
         temp=arr[i];
         arr[i]=arr[i+1];
         arr[i+1]=temp;
      }
   }
   len=len-1;
   recurbublSort(arr, len);
}
int main(){
   int Arr[] = {21, 34, 20, 31, 78, 43, 66};
   int length = sizeof(Arr)/sizeof(Arr[0]);

   recurbublSort(Arr, length);

   printf("Sorted array : ");
   for(int i=0;i<length;i++){
      printf("%d ",Arr[i]);
   }

   return 0;
}

Output

Si nous exécutons le code ci-dessus, il générera la sortie suivante

Sorted array: 20 21 31 34 43 66 78

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!