Exercice des tableaux

j'ai une solution, mais elle est nul

20 décembre 2006 à 17:59:51

J'ai fais le chapitre sur les tableaux et j'ai facilement trouvé la solution pour l'exercice 5 pour classer par ordre croissant les chiffres d'un tableaux. Mais ma solution est quand même un peu tordu. Voici ma fonction :

void ordonnerTableau(long tableau[]‚ long tailleTableau)
{
long i=0‚ j=0‚ k=0; //initialisation des variable
long tailleMax=tailleTableau–1; /*je rentre la valeur – 1 pour taille max de
car sinon le PC va avec une valeur qui n'est pas dans le tableau*/
do
{
for (i=0; i<tailleMax; i++)
{
if (tableau[i]>tableau[i+1]) //si mes nombre ne sont pas dans le bon sens
{
j= tableau[i];//je met mes valeur dans des variable provisoirement
k= tableau[i+1];
tableau[i]=k;//avant de les échanger de place
tableau[i+1]=j;
}
}
tailleMax––;
}while(tailleMax); /*je relance le processus autant de fois que un nombre
peux bouger de place*/
}

Je trouve ce code très maladroit a cause du fait que je répète plusieur fois les opération de déplacement de mes valeurs. Car avec 5 valeur, je fais 5² tour de manège. Si je doit ordonner 1000 chiffre, mon pauvre PC va mourir !

ddayx

20 décembre 2006 à 18:08:15

Ok, bravo ! ... :-°

Davidlouiz

20 décembre 2006 à 18:18:01

Voici comment je ferais :

- Je déclare un deuxième tableau de la même taille
- Je récupère la première valeur et je la place dans plusPetiteValeur (et j'enregistre son "adresse" - (adresse = i;)
- Je parcour le tableau : si la valeur est plus petite -> je la met à la place de plusPetiteValeur et j'enregistre son adresse (adresse = i;) sof si elle vaut -1.
- Puis arrivé à la fin, je ferait valeur[adresse] = -1
- Je placerais la valeur dans la première case du tableau, puis en boucle... j'avance... justqu'a la fin.

Par compte ca nessessite le double en RAM.

Sinon, y'a une autre solution :

Tu compare les 2 premiers, si le 2 et < le 1, tu les inverse (avec un variable temporaire).
Et à chaque fois que tu doit répéter cette manoeuvre, tu recommence depuis le début. (edit : heu nan, reculer d'une case seulement devrai suffir)
Et tant que les premier sont < que les suivant, tu avance.

Cette deusième technique est moin rapide mais prend pas de RAM et fonctionne pour tout les nombres !

Voilà, y'a sans doute des mieux.

Niluge

20 décembre 2006 à 18:18:22

Merci, mais, il doit bien avoir un autre solution ou il ne faut pas faire autant de boucle !

Birdoon

20 décembre 2006 à 18:22:16

Moi je trouve ma technique assez propre :

void ordonnerTableau(int tableau[]‚ int tailleTableau)
{
long i = 0‚ j = 0‚ nombreTemporaire = 0;
for (i = 0 ; i < tailleTableau ; i++)
{
for ( j = 0 ; j < tailleTableau ; j++)
{
if (tableau[i] < tableau[j])
{
nombreTemporaire = tableau[j];
tableau[j] = tableau[i];
tableau[i] = nombreTemporaire;
}
}
}
}

WhiteTiGer

20 décembre 2006 à 18:38:48

Et la mienne est la plus rapide

void swap(int *a‚ int *b)
{
if(*a == *b) return;

*a += *b;
*b = *a – *b;
*a –= *b;
}

void quicksort(int * t‚ int start‚ int end)
{
int i;
int count = start;
int pivot = (start + end)/2;

if( end – start <= 0 ) return;

swap(&t[start]‚ &t[pivot]);

for(i = start+1; i <= end; i++)
if(t[i]<t[start])
swap(&t[++count]‚ &t[i]);

swap(&t[count]‚ &t[start]);
quicksort(t‚ start‚ count–1);
quicksort(t‚ count+1‚ end);
}

Complexité garantie en N.log(N)

Si tu veux te renseigner sur les différentes méthodes, tape sur google "algorithmes de tri" & enjoy

HanLee

20 décembre 2006 à 20:23:00

Non elle n'est pas garantie en N.log(N), c'est seulement en moyenne.
Dans le pire des cas, c'est du O(N^2).

C'est le choix du pivot qui est déterminant.

WhiteTiGer

20 décembre 2006 à 21:18:37

Exact, au temps pour moi

Mais je crois me souvenir qu'elle n'atteint ce "pire des cas" que quand le tableau est déjà trié.