Tris rapide et maximier

Fermé
IloveJPK - 29 oct. 2009 à 12:55
tarek_dotzero Messages postés 817 Date d'inscription jeudi 19 juillet 2007 Statut Membre Dernière intervention 12 avril 2022 - 29 oct. 2009 à 13:33
Bonjour,

Je voudrais écrire les codes en C pour effectuer des tris rapide et maximier.

Pour le tri rapide, voici mon code :

int partition (T_Elt T[], int premier, int dernier)
{
int compteur=premier, i, pivot=T[premier], echange;
for(i=premier+1 ; i<=dernier ; i++)
{
if(pivot>T[i])
{
compteur++;
echange=T[i];
T[i]=T[compteur];
T[compteur]=echange;
}
}
echange=T[premier];
T[premier]=T[compteur];
T[compteur]=echange;
return(compteur);
}

void Tri_Rapide(T_Elt T[], int premier, int dernier)
{
int pivot;
if (premier<dernier)
{
pivot=partition(T, premier, dernier);
Tri_Rapide(T, premier, pivot-1);
Tri_Rapide(T, pivot+1, dernier);
}
}

J'arrive à générer la solution mais lorsque je tente d'éxécuter, le programme plante. Auriez-vous une solution ?

Pour le tri maximier, j'ai écrit les codes permettant de remonter et de redescendre un élément, d'organiser et de trier :

void echanger (T_Elt T[], int i, int j)
{
int echange;
echange=T[i];
T[i]=T[j];
T[j]=echange;
}

void remonter (T_Elt T[], int n, int i)
{
if (i==1) return;
if (T[i]>T[i/2])
{
echanger (T, i, i/2);

remonter (T, n, i/2);
}
}

void redescendre ( T_Elt T[], int n, int i)
{
int imax;
if (i>=n/2 +1) return;
if ((2*i+1<=n)&&(T[2*i+1]>T[2*i]))
imax=2*i+1;
else
imax=2*i;
if (T[imax]>T[i])
{
echanger (T, imax, i);
redescendre (T, n, imax);
}
}

void organiser( T_Elt T[], int n )
{
int i;
for(i = 2 ; i < n ; i++)
remonter(T, n, i);
}


void Tri_Arbre( T_Elt T[], int n )
{
int i;
organiser(T, n);
for(i=n-1 ; i>0 ; i-- )
{
echanger(T, 0, i);
redescendre(T, n, 0);
}
}

Mais le tableau obtenu n'est pas trié...

Merci de votre aide
A voir également:

4 réponses

on s en tappe eh du kon
0
tarek_dotzero Messages postés 817 Date d'inscription jeudi 19 juillet 2007 Statut Membre Dernière intervention 12 avril 2022 120
29 oct. 2009 à 13:04
Tu es sûre que ce truc marche?
De toute façon, on ne peut pas dire que c'est un "trie rapide" même s'il est juste: l'utilisation de la récursivité donne une complexité exponentielle.
0
Merci pour ces critiques... Auriez-vous des solutions à mes problèmes ?
0
tarek_dotzero Messages postés 817 Date d'inscription jeudi 19 juillet 2007 Statut Membre Dernière intervention 12 avril 2022 120
29 oct. 2009 à 13:33
Je ne connait que des méthodes n^2 comme le trie en boule, mais cela reste plus rapide que le trie exponentielle.
Le trie en boules consiste à faire remonter les éléments les plus grands vers la fin du tableau.

Un exemple en .vbs (j'ai pas un compilateur c installé)



dim tableau(5)

tableau(1) = 11
tableau(2) = 2
tableau(3) = 23
tableau(4) = 14
tableau(5) = 5

i = 1

while(i < 5)

      if(tableau(i) > tableau(i+1))then
		echange = tableau(i)
                tableau(i) = tableau(i+1)
		tableau(i+1) = echange
		i = 0
      end if
      i = i + 1
	'MsgBox i

wend

for i = 0 to 5
	MsgBox tableau(i)
next
 	

0