Tris rapide et maximier

IloveJPK -  
tarek_dotzero Messages postés 834 Statut Membre -
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

nana
 
on s en tappe eh du kon
0
tarek_dotzero Messages postés 834 Statut Membre 122
 
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
IloveJPK
 
Merci pour ces critiques... Auriez-vous des solutions à mes problèmes ?
0
tarek_dotzero Messages postés 834 Statut Membre 122
 
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