Tri rapide

[invitefa8436e7]

Bonjour,

Je ne sais pas si c'est ici qu'il faut que je pose ma question mais j'ai un problème dans la mise au point d'un algorithme de tri rapide. J'ai écrit ce code en C :

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 ?

Merci d'avance
-----

[sylvainc2]

La logique semble correcte. Si ca plante c'est peut-être parce qu'il fait un trop grand nombre d'appels récursifs à Tri_Rapide(), si tu as une grand nombre de données à trier, la pile saute. Est-ce que ca plante aussi avec un petit nombre de données?

[invitefa8436e7]

En fait, c'est un programme qui doit compter le nombre d'affectations et de comparaisons.

[invitefa8436e7]

Il me semble aussi qu'il n'y a pas de problème de logique. J'ai un autre problème pour un tri arbre. J'ai écrit le code suivant :

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 = 1 ; 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);
	}
}

Cette fois, le compilateur m'indique une erreur de logique : le tableau que j'obtiens n'est pas trié... Où y aurait-il une erreur ?

Merci d'avance

[A voir en vidéo sur Futura]

[acx01b]

salut

tu t'es planté dans ton main, ta fonction tri_rapide elle fonctionne

[invitefa8436e7]

Et pour le tri arbre ?

[invite897678a3]

Bonjour,

Une petite idée...

Si la fourchette de valeurs des éléments à trier est relativement limitée (<100 ou peut-être inférieure à 1 000) et dans la mesure où il vous pourriez créer un tableau aussi grand, il suffirait de lire chaque valeur et de la mettre à sa place dans le tableau.

Lire ensuite le tableau (pour les valeurs non nulles): toutes les valeurs sont triées.

C'est le tri qui tue!

[acx01b]

déja on a fait l'effort de regarder tri_rapide,
tu sais c'est pas très intéressant de regarder un code "cas d'école" comme un tri ...

[invitefa8436e7]

Alors là je suis entièrement d'accord : ça n'a rien d'intéressant. Mais c'est pas à moi qu'il faut le dire.