Trie bulle

#include <stdio.h>
#include <conio.h>

void main()
{
 clrscr();
 int n; /*Le nombre d'elements*/
 int t[20]; /*Tableau de 20 cases*/
 int aux; /*Variable temporaire*/
 int test; /* "0" si le tableau n'est pas trier, "1" sinon*/
 int i; /*variable de parcour du tableau*/
 int x; /*Variable compte le nombre d'execution du traitement*/
 
 /*LECTURE DE LA TAILLE AVEC CONTROL DE SAISIE*/
 do
 {
  printf("Saisir la taille du tableau entre 2 et 20: ");
  scanf("%d",&n);
 }while(n<2 || n>20);
 
 /*REMPLISSAGE TU TABLEAU*/
 for (i=0;i<n;i++)
 {
  printf("T[%d]= ",i);
  scanf("%d",&t[i]);
 }
 printf("\n");
 
/*AFFICHAGE DU TABLEAU AVANT LE TRI*/
 for (i=0;i<n;i++)
 {
  printf("%d ",t[i]);
 }

 /*TRI DU TABLEAU*/         c'est ici le problem
 test=0;
 for (i=0;(i<n-1) && (!test);i++)
 {
  test=1;
  while (t[i]>t[i+1])
  {
   aux=t[i];
   t[i]=t[i+1];
   t[i+1]=aux;
   test=0;
  }
 }

 printf("\n");
 /*AFFICHAGE DU TABLEAU APRES LE TRI*/
 for (i=0;i<n;i++)
 {
  printf("%d ",t[i]);
 }
 getch();
}

Juste un code pas de question ?

Oua tu as un manifique algo de tri en O(n) dommage qu'il ne puisse pas marcher
un tri bulle ca ressemble a ca :

Tant qu'on fait des modifications
 |  Pour chaque element
 |  | Si plus grand que le suivant
 |  |   | echanger
 |  |  +
 | +
 +

Soit :

int test = 1 ;
do
{
  test = 0 ;
  for( int id = 0 ; id < n - 1 ; id++ )
    if( t[id] < t[id+1] )
     {
         aux = t[id] ;
         t[id] = t[id+1] ;
         t[id+1] = aux ;
         test = 1 ;
     }
}
while( test ) ;

Louis

Pourquoi faire 2 boucles imbriqués ?


int pos = 0;
int dernier = n-1;
int aux;

while( pos < dernier )
{
     if( T[pos] > T[pos+1] )
     {
         aux  = T[pos+1];
         T[pos+1] = T[pos];
         T[pos] = aux;
         pos = -1;
     }
     pos++;
}

Pourquoi deux boucles imbriquées??

parce que mon algo est en N^2 le tien en N^3 .. c'est vrai que pour des valeurs < 20 on s'en fout ( quoique .. ) mais des que l'on a genre 1000 ton algo met 0.36 secondes .. bien trop ( le mien met moins de 0.01 )

rrk275