Tri Rapide

Un algorithme qui permet de trier un tableau (Tri rapide)

Indication: Wikipedia


Fonction Partitionnement(T: tab[1..n] d'entier, iMin, iMax: entier): entier;
	Var
		i, j, v, temp: entier;

	Debut

		v := T[iMax];
		i := iMin;
		j := iMax - 1;

		TantQue(i <= j) Faire

			TantQue(i < iMax) Et (T[i] <= v) Faire
				i := i + 1;
			FinTantQue

			TantQue(j >= iMin) Et (T[j] >= v) Faire
				j := j - 1;
			FinTantQue

			Si(i < j) Faire
				temp := T[i];
				T[i] := T[j];
				T[j] := temps;
			FinSi
		FinTantQue

		T[iMax] := T[i];
		T[i] := v;

		renvoyer i;

	Fin;

Procédure TriRapide(T: tab[1..n] d'entier, iMin, iMax: entier);
	Var
		i: entier;

	Debut

		Si(iMin < iMax) Alors
			i := Partitionnement(T, iMin, iMax);
			// Trier la partie gauche
			TriRapide(T, iMin, i - 1);
			// Trier la partie droite
			TriRapide(T, i + 1, iMax);
		FinSi
	Fin;

Procédure QuickSprt(T: tab[1..n] d'entier, n: entier)

	Debut

		TriRapide(T, 0, n - 1);

	Fin;

Laisser des commentaires:

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :