Tri Rapide (Récursif)

1. Le pointeur gauche pointe vers le premier élément et le poniteur droit vers le dernier. On prend le premier élément comme valeur pivot.
2. Le pointeur droit compare sa valeur avec le pivot. Si la valeur est supérieure, le pointeur se déplace à gauche. Si la valeur est inférieure, le pointeur s'arrête et l'élément est placé à la position du pointeur gauche.
3. Le pointeur gauche compare sa valeur avec le pivot. Si la valeur est inférieure, le pointeur se déplace à droite. Si la valeur est supérieure, le pointeur s'arrête et l'élément est placé à la position du pointeur droit.
4. On répète les étapes 2 et 3 jusqu'à ce que les deux pointeurs se rencontrent à la même position, où l'on place le pivot.
5. On divise le tableau en deux parties autour de la position du pivot. Tous les éléments à gauche sont inférieurs au pivot et tous les éléments à droite sont supérieurs.
6. On répète le processus pour chaque sous-tableau jusqu'à ce qu'il ne reste plus qu'un seul élément.

Complexité temporelle : Mielleur cas O(nlogn), Pire cas O(n²), Cas moyen O(nlogn)

• Chaque comparaison nécessite environ n opérations.
• Si le pivot est toujours au milieu, la division se fait en deux à chaque étape, avec logn niveaux de division, résultant en O(nlogn).
• Si le tableau est déjà trié, chaque pivot est soit le minimum soit le maximum, créant une structure en arbre dégénéré avec O(n²) au pire cas.

Complexité spatiale : Meilleur cas O(logn), Pire cas O(n)

• Le tri s'effectue sur place avec une pile comme espace auxiliaire.
• Chaque récursion place le pivot dans la pile.
• Dans le meilleur cas, avec logn niveaux, on utilise O(logn) d'espace.
• Dans le pire cas, avec n récursions, on utilise O(n) d'espace.

Implémentation en C (tri_rapide.c):

#include <stdio.h>

/* prototypes des fonctions */
void tri_rapide(int *, int, int);	// tri rapide (récursif)
void afficher(int *, int);		// affichage élément par élément

/* fonction principale */
int main(void)
{
	int tab[] = {4,2,6,9,5,1,3};
	int taille = sizeof(tab) / sizeof(int);
	afficher(tab, taille);

	tri_rapide(tab, 0, taille - 1);
	printf("[ après tri rapide ] ");
	afficher(tab, taille);
	return 0;
}
/* fonction auxiliaire */
void tri_rapide(int *tableau, int debut, int fin)		// tri rapide (récursif)
{
	if(debut >= fin) return ;
	int gauche = debut, droite = fin;
	int pivot = tableau[gauche];	// premier élément comme pivot
	while(gauche < droite)
	{
		// côté droit : si l'élément est plus grand que le pivot, on déplace le pointeur
		while(gauche < droite && tableau[droite] >= pivot) droite--;
		// si l'élément est plus petit, on le place à gauche
		tableau[gauche] = tableau[droite];
		// côté gauche : si l'élément est plus petit que le pivot, on déplace le pointeur
		while(gauche < droite && tableau[gauche] < pivot) gauche++;
		// si l'élément est plus grand, on le place à droite
		tableau[droite] = tableau[gauche];
	}
	// on place le pivot à sa position correcte
	tableau[gauche] = pivot;
	// on divise le tableau autour du pivot
	tri_rapide(tableau, debut, gauche  - 1);
	tri_rapide(tableau, gauche + 1, fin);
}

void afficher(int *tableau, int longueur)		// affichage élément par élément
{
	printf("éléments(%d): ", longueur);
	for(int k = 0; k < longueur; k++)
	{
		printf("%d  ", tableau[k]);
	}
	printf("\n");
}

Compilation : gcc -o tri_rapide tri_rapide.c Exécution : ./tri_rapide

Tri Fusion (Récursif)

1. On divise le tableau en deux moitiés à partir du milieu. On répète ce processus pour chaque moitié jusqu'à ce qu'il ne reste plus qu'un seul élément.
2. On fusionne les deux moitiés (chaque contenant un seul élément) en les triant.
3. On fusionne les moitiés déjà triées.
4. On répète l'étape 3 jusqu'à ce que tout le tableau soit trié.

Complexité temporelle : Meilleur cas O(nlogn), Pire cas O(nlogn), Cas moyen O(nlogn)

• Chaque division sépare le tableau en deux, créant logn niveaux.
• Chaque niveau nécessite environ n opérations pour fusionner, résultant en O(nlogn) total.

Complexité spatiale : O(n)

• On a besoin d'espace supplémentaire proportionnel à la taille du tableau pour stocker les éléments triés.

Implémentation en C (tri_fusion.c):

#include <stdio.h>
#include <math.h>

/* prototypes des fonctions */
void tri_fusion(int *, int, int);	// tri fusion (récursif)
void afficher(int *, int);		// affichage élément par élément

/* fonction principale */
int main(void)
{
	int tab[] = {4,2,6,9,5,1,3};
	int taille = sizeof(tab) / sizeof(int);
	afficher(tab, taille);

	tri_fusion(tab, 0, taille - 1);
	printf("[ après tri fusion ] ");
	afficher(tab, taille);
	return 0;
}
/* fonction auxiliaire */
void tri_fusion(int *tableau, int debut, int fin)		// tri fusion (récursif)
{
	if(debut >= fin) return ;
	// on divise le tableau en deux moitiés
	int milieu = debut + ceil((fin - debut) / 2);
	tri_fusion(tableau, debut, milieu);
	tri_fusion(tableau, milieu + 1, fin);
	// on fusionne les deux moitiés triées
	int tmp[fin - debut + 1];
	int i = debut, j = milieu + 1;
	for(int k = 0; k <= fin - debut; k++)
	{
		// si la moitié droite est terminée ou l'élément gauche < élément droit
		if(j > fin || (i <= milieu && tableau[i] < tableau[j]))
		{
			tmp[k] = tableau[i];
			i++;
		}
		// si la moitié gauche est terminée ou élément gauche >= élément droit
		else
		{
			tmp[k] = tableau[j];
			j++;
		}
	}
	// on copie les éléments du tableau temporaire vers le tableau original
	for(int i = debut, k = 0; i <= fin; i++, k++)
	{
		tableau[i] = tmp[k];
	}
}

void afficher(int *tableau, int longueur)		// affichage élément par élément
{
	printf("éléments(%d): ", longueur);
	for(int k = 0; k < longueur; k++)
	{
		printf("%d  ", tableau[k]);
	}
	printf("\n");
}

Compilation : gcc -o tri_fusion tri_fusion.c Exécution : ./tri_fusion

Tri de Shell

1. On choisit un intervalle (généralement la moitié de la taille du tableau) et on divise les données en groupes que l'on trie individuellement.
2. On réduit l'intervalle de moitié et on répète le processus.
3. On continue jusqu'à ce que l'intervalle soit de 1, effectuant le tri final.

Complexité temporelle : O(n²) - O(n log² n)

• Version améliorée du tri par insertion.
• Plus rapide que le tri par insertion mais plus lent que O(n log n).

Complexité spatiale : O(1)

• Le tri s'effectue sur place, n'utilisant qu'un espace constant pour les échanges.

Implémentation en C (tri_shell.c):

#include <stdio.h>
#include <math.h>

/* prototypes des fonctions */
void tri_shell(int *, int);			// tri de Shell
void afficher(int *, int);			// affichage élément par élément

/* fonction principale */
int main(void)
{
	int tab[] = {4,2,6,9,5,1,3};
	int taille = sizeof(tab) / sizeof(int);
	afficher(tab, taille);

	tri_shell(tab, taille);
	printf("[ après tri Shell ] ");
	afficher(tab, taille);
	return 0;
}
/* fonction auxiliaire */
void tri_shell(int *tableau, int longueur)		// tri de Shell
{
	int intervalle = ceil(longueur / 2);	// espace entre les éléments comparés
	while(intervalle > 0)
	{
		// de l'intervalle à la fin, on compare chaque élément avec celui qui se trouve avant
		for(int i = intervalle; i < longueur; i++)
		{
			// comparaison circulaire avec les éléments précédents selon l'intervalle
			for(int j = i; j >= intervalle; j -= intervalle)
			{
				if(tableau[j] < tableau[j - intervalle])
				{
					int temp = tableau[j];
					tableau[j] = tableau[j - intervalle];
					tableau[j - intervalle] = temp;
				}
			}
		}
		// on réduit l'intervalle
		intervalle  = ceil(intervalle / 2);
	}
}

void afficher(int *tableau, int longueur)		// affichage élément par élément
{
	printf("éléments(%d): ", longueur);
	for(int k = 0; k < longueur; k++)
	{
		printf("%d  ", tableau[k]);
	}
	printf("\n");
}

Compilation : gcc -o tri_shell tri_shell.c Exécution : ./tri_shell