Trie bulle

Question

#include #include 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;it[i+1]) { aux=t[i]; t[i]=t[i+1]; t[i+1]=aux; test=0; } } printf(" "); /*AFFICHAGE DU TABLEAU APRES LE TRI*/ for (i=0;i

rrk275 · Answer

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

yann_lo_san · Answer

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

rrk275 · Answer

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

Trie bulle

3 réponses

Votre réponse

Discussions similaires