GamerLIX

Membre

Algorithme de Tri-Bulle !

Hello world !
Première contribution sur ce forum , et je vous propose une fonction dite de "tri-bulle" en langage C.

À quoi ça sert ? En C nous pouvons créer des tableaux pour stocker des variables. Parfois nous avons envie de ranger ces variables dans un ordre précis.

La fonction que je vais vous présenter vous permettra de ranger ces variables dans un ordre croissant.

Le principe !

Imaginons que nous avons stocker les variables suivantes {3,2,5,4}
Notre fonction va faire plusieurs tours.
D'abord elle va regarder si deux éléments successifs sont bien ordonnés.

Premier tour

{3,2,5,4}
Du coup notre fonction va permuter ces deux nombres
{2,3,5,4}
Puis elle continue
{2,3,5,4}
Et enfin
{2,3,5,4}

Et là il reste encore deux variable qui n'ont pas permutées ! Bon on refait un second tour !

Second Tour

{2,3,5,4}
{2,3,5,4}
{2,3,4,5}

Tadaaa !!! Nous avons classé dans l'ordre croissant nos variables ! Remarquez que au premier tour notre fonction à bien laisser intacte 3,5 mais qu'au second tour elle à bien permuter 5 et 4.

Bon maintenant que nous avons compris le principe du "tri-bulle" passons au code :

[== Indéfini ==]
void tab_trier(int *tab, int n)
{
     int i, tmp, permutation = 1;
     while (permutation == 1)
     {
       permutation = 0;
       for (i=0; i<n-1; i++)
       {
         if (tab[i] > tab[i+1])
         {
         tmp = tab[i];
         tab[i] = tab[i+1];
         tab[i+1] = tmp;
           /* Il y a eu permutation */
         permutation = 1;
         }
       } 
      } /* while */
 
}

Je traduirais ce code ainsi ,

On déclare des variables de type int , dont , i qui servira pour parcourir le tableau, tmp qui servira pour la permutation ainsi que permutation.
Nous parcourons le tableau avec for jusqu'à n-1 , n étant la taille du tableau.
Si une variable du tableau est plus grande que la variable qui suit , c'est à dire i+1 alors :
La variable tmp stocke la valeur de tab i  , tab i  prend la valeur de tab[i+1] et tab[i+1] prend la valeur de tmp. En clair , les variables viennent de permuter. Elle ont échangées leurs places dans le tableau.

Ensuite on signal qu'il y a eu permutation afin de refaire un tour , et rebelotte !

Comment utiliser cette fonction ?

Faite un header qui contiendra le prototype de cette fonction !

[== Indéfini ==]
#ifndef tab_trier_H
#define tab_trier_H
void tab_trier(int *tab, int n);
#endif

Pour les débutants , sachez que j'ai utilisé dans ce header une astuce connue de tous les programmeurs en C. En effet j'ai mis une structure conditionnelle dans le préprocesseur afin d'éviter les inclusions infinies.
Principe d'inclusions infinies !

Si A.h dépend de B.h , alors l'ordinateur va inclure B.h , mais B.h dit d'inclure A.h , donc il inclut A.h , ect.

Avec cette astuce lorsque votre .h sera inclut , comme la constante tab_trier_H n'a pas encore était définie , alors on lit ce qui est dans le if. Mais comme en suite la constante  tab_trier_H sera définie par #define alors si l'ordinateur rejette un coup d'oeil au Header , la condition ne sera plus vraie !

Attention ! Ne pas oublier d'inclure le header à notre programme

Ce qui nous donne :

[== Indéfini ==]
#include<stdio.h>
#include<stdlib.h>
#include"tab_trier.h"
void tab_trier(int *tab, int n)
{
     int i, tmp, permutation = 1;
     while (permutation == 1)
     {
       permutation = 0;
       for (i=0; i<n-1; i++)
       {
         if (tab[i] > tab[i+1])
         {
         tmp = tab[i];
         tab[i] = tab[i+1];
         tab[i+1] = tmp;
           /* Il y a eu permutation */
         permutation = 1;
         }
       } 
      } /* while */
 
}

Bon bah voilà mes enfants , reste plus qu'à faire un test !

[== Indéfini ==]
#include<stdio.h>
#include<stdlib.h>
#include"tab_trier.h"

int main(int argc,char *argv[])
{
   int i,*tab = NULL,n,c = 0;
   
   printf("Taille du tableau = ");
   scanf("%d",&n);
   
   tab = malloc (n * sizeof(int));
   
   for (i = 0 ; i < n ; i++)
   {
	   c = i + 1;
	   printf("case %d =",c);
	   scanf("%d",&tab[i]);
   }
   for (i = 0 ; i < n; i++)
   {
	   c = i + 1;
	   printf("case %d = %d\n",c,tab[i]);
   }
   tab_trier(tab ,n);
   for (i = 0 ; i < n; i++)
   {
	   c = i + 1;
	   printf("case %d = %d\n",c,tab[i]);
   }
   return 0;
}

Explication de ce ptit code , je créé un "tableau dynamique" avec malloc. Retenez que la taille du tableau sera définie par l'utilisateur à l'exécution du programme grâce à scanf.

Ensuite nous parcourons le tableau afin d'en remplir chaques cases  ! Mais attention ! En C (comme dans d'autres langages j'imagine ) un tableau commence à 0. Et oui si vous stocker 5 variables , elles occuperont les cases 0,1,2,3,4.
Du coup je déclare avant une variable c de type int.

Puis je l'incrémente à chaque tour de la boucle for avec case du tableau i +1.

Ensuite nous parcourons le tableau pour voir , les variables ainsi que le numéro de leurs cases. (le numéro de la case de chaque variable étant définie par c , alors l'utilisateur verra les cases 1,2,3,4,5. Youpiii !)

Bon ensuite , nous faisons appel à notre fonction maison , elle prend en paramètre , le nom du tableau ainsi que le nom de la variable représentant sa taille.

Ensuite , parcourons de nouveau le tableau et... Hallelujah !!!

Nos variables sont dans l'ordre croissant!

Voilà c'était une petite présentation d'une fonction que j'ai trouvé sur le net il y a un bout de temps et qui , je pense , peut-être utile , merci d'avoir lu ce torchon jusqu'au bout Ciao !

PS:En espérant avoir été explicite dans ce tuto

Dernière modification par GamerLIX (12-04-2014 20:15:04)

IceF0x

#! Gourou Linux

Re : Algorithme de Tri-Bulle !

Merci pour la contribution 

---

Utiliser des logiciels propriétaires, c'est comme les plats préparés, on est incapable de dire les conservateurs qu'ils contiennent, on dira toujours que c'est bon, mais ça ne remplacera jamais le repas fait maison par sa maman.
]:D #! Crunchbang & Archlinux GNU/Linux User ]:D

GamerLIX

Membre

Re : Algorithme de Tri-Bulle !

De rien , ça me fait plaisir 

fr0g

Membre

Re : Algorithme de Tri-Bulle !

Les explications sont correctes je trouve .
Btw tu peux aussi te séparer d'une boucle et d'une variable en utilisant la récursion, il suffit de rappeler ta fonction après chaque permutation

void    tri(int *tab, int size)
{
  int   i;
  int   tmp;

  for (i = 0 ; i < (size - 1); i++)
    {
      if (tab[i] > tab[i + 1])
        {
          tmp = tab[i + 1];
          tab[i + 1] = tab[i];
          tab[i] = tmp;
          tri(tab, size); // rappel de la fonction
        }
    }
  return;
}

GamerLIX

Membre

Re : Algorithme de Tri-Bulle !

Et bien merci , effectivement ça simplifie la chose :-)