Tri à bolles Fermé

Question

Bonjour,
j'ai un exercice d'algorithmique que je n'ai pas su répondre qui est le suivant :
" On veut 'trier' un tableau d'indices 1...n de valeurs entières relatives de manière à trouver au début du tableau les entiers pairs, triés par valeurs non croissantes, et à la fin du tableau les entiers impairs, triés par valeurs non décroissantes. On aimerait utiliser un tri de type 'tri à bulles'.

1. Donner la forme générale de la boucle qui "trie" en faisant appel à une fonction booléenne "bulle". Celle-ci compare deux éléments successifs i et i+1 indique comme résultat le fait que les éléments ont été échangés ou non.

2. Écrire le code du prédicat "bulle".  

Je veux, svp, une réponse détaillée.

Cordialement.

toto · Answer

Bonjour

Réponse détaillée : montre nous de manière détaillée ce que tu as déjà fait, et si on voit qu'il déjà eu un vrai travail, nous nous ferons un plaisir de t'aider.
Parce qu'avec ta façon de poser ta question, tu présentes tous les symptômes de quelqu'un qui cherche à faire faire ses devoirs par les autres. Et ça n'est pas très apprécié ici.

chaibi.2000 · Answer

le code que j'ai fait(en C) :

bulle=1;
while(bulle)
{ bulle=0;
  for (i=0 ; i<n-1 && ! bulle; i++)
     if(T[i]>T[i+1])
      { echange(T,i,i+1);
         bulle =1;
       }

toto · Answer

Ton tri marche probablement, mais...
.Pourquoi mettre && !bulle dans le for ? Non seulement il n'est pas utile, mais il dégrade beaucoup l'efficacité du tri : Tu vas repartir de 0 dès que tu auras trouvé deux éléments à inverser, alors que tu sais très bien qu'il n'y en a pas avant au moins le rang n-1 (puisque tu es arrivé au rang n sans inversion).
Mais surtout, tu ne réponds pas au problème posé. On te demande d'utiliser une fonction bulle qui (etc, je ne recopie pas). On te demande la forme de la boucle et le code de la fonction bulle, toi tu donnes un programme (incomplet..) qui fait tout sans appeler la fonction bulle exigée.

manu · Answer

Moi j'ai une question sur l'énoncé (je travaille sur le même exo) :

qu'est-ce que veulent dire les formulations "(...)triés par valeurs non croissantes(...)" et "(...)triés par valeurs non décroissantes(...)" ?
Je connais"tri par valeur croissantes", "tri par valeur décroissantes", ou "non trié", mais alors "(...)triés par valeurs non croissantes(...)" ...???

traxex · Answer

ma proposition :

j ai mit les pairs a gauche et impair a droite sans trie les nombres pair ou impair

#include <stdio.h>
#include <stdlib.h>
# define n 10

typedef enum { TRUE, FALSE } booleen;

void f_affiche_tab ( int * tab )
{
int i;
for ( i = 0; i < n; i++ )
printf("%2d ",tab[i]);
printf("\n");
}

void f_echange ( int * tab, int a, int b )
{
int aux = tab[a];
tab[a] = tab[b];
tab[b] = aux;
}

booleen f_bulle ( int * tab, int a, int b )
{
if ( tab[a]%2 != 0 && tab[b]%2 == 0 ) /* tab[b] seulement pair on echange */
{
f_echange ( tab, a, b);
return TRUE;
}

return FALSE;
}

int main ()
{
int tab[n],i;

srand( getpid() ); /* initialise le générateur de nombres aléatoires */

for ( i = 0; i < n; i++ )
tab[i] = rand()%20; /* Valeur aléatoire de 0 à 10 */

printf("Mon tableau initiale\n");
f_affiche_tab (tab);

//printf("Les Etapes\n");
int bulle;
do
{
bulle = 0;
for ( i = 0; i < n-1; i++ )
if ( f_bulle ( tab, i, i+1 ) == TRUE )
{
bulle = 1;
//f_affiche_tab (tab);
}
} while (bulle);

printf("Mon tableau triée\n");
f_affiche_tab (tab);

return EXIT_SUCCESS;
}

Tri à bolles

5 réponses

Discussions similaires