Algorithmes de tris

Bubble Sort : Tri par échanges

Comme des bulles qui remontent à la surface, les éléments de plus faibles valeurs se déplacent vers le début de notre tableau. C'est pourquoi cette technique de tri est souvent nommée le tri à bulles (bubble sort), mais nous le retrouvons aussi sous le nom de tri par échanges (exchange sort).

C'est le tri le plus simple, mais il en existe de très nombreuses variantes. Nous verrons une implémentation de base, et une petite amélioration de cette implémentation générale.

Selection Sort : Tri par sélections

Le principe du tri par sélection est de diminuer le nombre de permutations, en le limitant au nombre d'éléments à trier. Par rapport à un tri par insertions ou un tri à bulles, le nombre de comparaisons sera ici égal ou même suppérieur. Ceci devient pourtant très intéressant dans le cas où la comparaison des éléments a un coût peu élevé, mais que les permutations ont un coût élevé (le déplacement des éléments -qui est un ensemble de suppressions et d'ajouts- dans la structure utilisée nécessite beaucoup de ressources en temps ou en mémoire).

Nous pouvons procéder de 2 manières, de la plus petite vers la plus grande valeur (du début vers la fin), ou de la plus grande vers la plus petite valeur (de la fin vers le début).

program selectionSort;
function maxValueIndex(var a : array of integer; minIndex, maxIndex : integer);
{Pre: 	a defined
		maxIndex>=minIndex;
		minIndex>=0;
		a[minIndex..maxIndex] defined
 Post:	for each i into minIndex..maxIndex, a[maxIndex] >= a[i] 
}
var tempMax : integer;
begin
	if minIndex >= maxIndex then maxValueIndex := minIndex;
	else begin
		tempMax := maxValueIndex(a, minIndex+1, maxIndex);
		if a[minIndex]<a[tempMax]
			then maxValueIndex := tempMax;
			else maxValueIndex := minIndex;
		end
end;
procedure swap(var a : array of integer; i, j : integer);
{Pre: 	a defined
		j>i;
		i>=0;
		a[i] defined
		a[j] defined
 Post:	a[i]=old value at a[j] et a[j]=old value at a[i] 
}
var temp: integer;
begin
	temp := a[i];
	a[i] := a[j];
	a[j] := temp;
end;
procedure selectionSort(var a : array of integer; arraySize : integer);
{Pre: 	a defined
		arraySize>=0;
		a indexed from 0 to arraySize -1
		for each i into 0..arraySize-1, a[i] defined
 Post:	for each i into 0..arraySize-2, a[i] <= a[i+1]
}
var i : integer;
begin
	for i := arraySize downto 0 do
		swap(a, i, maxValueIndex(a,1,i));
end;
{main program
}
begin
	const maxIndice = 7;
	var testArray : packed array[0..maxIndice] of integer;
	testArray[0] := 8;
	testArray[1] := 4;
	testArray[2] := 6;
	testArray[3] := 2;
	testArray[4] := 13;
	testArray[5] := 4;
	testArray[6] := 1;
	testArray[7] := 20;
	var i : integer;
	writeln('Unsorted array :');
	for i:=0 to maxIndice do
		writeln('value ', testArray[i], ' at index ', i);
	selectionSort(testArray, maxIndice+1);
	writeln('Sorted array :');
	for i:=0 to maxIndice do
		writeln('value ', testArray[i], ' at index ', i);
end.

Tri par insertions

Le tri par insertion permet d'éviter les nombreuses permutations du tri par échanges.

Le principe général est de comparer une valeur de référence avec toutes celles qui suivent tant que la valeur suivante est inférieure, ou jusqu'à la fin du tableau si aucune valeur ne lui est supérieure. La valeur de référence sera placée après la dernière valeur qui lui est inférieure.

Il s'agit donc de mémoriser cette valeur référence, de déplacer d'une position le bloc des éléments valeurs inférieures ou égales qui suit, puis de placer la valeur référence dans la cellule libérée.

En réalité, le déplacement du bloc consiste en une série d'affectations (t[i]=t[i+1]).

Comme nous ne pouvons comparer la dernière valeur du tableau avec ses suivantes, nous débuterons la boucle à l'avant dernière valeur du tableau, jusqu'à la première.

Légende :

Valeurs de départ | Valeur de référence | Comparaisons | Déplacement | Valeurs triées

Heap Sort : Tri par tas

Le heap sort est basé sur les abres binaires balancés, ou red black tree(cliquez ici pour plus d'informations sur le parcours des éléments d'un arbre).

Un arbre est composé de nœuds qui sont reliés entre eux de manière à former une structure hiérarchique, dont chaque nœud ne peut avoir qu'un seul parent. Le premier nœud se nomme la racine (root), mais la représentation des arbres est le plus souvent inverse à la nature, présentant la racine en haut, et les branches vers les enfants vers le bas. Les nœuds qui n'ont pas d'enfants sont nommés les feuilles (leaves).

Un arbre binaire est un arbre dont chaque nœud peut être parent de deux nœuds enfants maximum.

La hauteur d'un arbre correspond au nombre de nœuds composant le chemin le plus long de la racine à la feuille la plus basse.

Dans un arbre binaire balancé (équilibré), chaque niveau double le nombre de nœuds du niveau précédent (si le nombre d'éléments ne s'y prête pas, c'est seulement le dernier niveau qui ne comportera pas exactement le double du précédent).

Nous pouvons donc en déduire certaines relations :

• h = hauteur de l'arbre binaire balancé complet
• n = nombre d'éléments de l'arbre

n = 2^h - 1

et

h = log₂(n + 1)

Ces notions sont importantes, car nous travaillons avec une structure logique en arbre, mais avec une structure réelle en tableau.

Quick Sort : Tri rapide

Le tri rapide repose sur le principe "diviser pour régner" (divide and conquer). Nous pouvons simplifier le tri en divisant notre structure en structures plus petites (par exemple diviser notre tableau en 2) séparées par une valeur pivot. Comme nous divisons à chaque fois le problème en 2, nous parlons d'algorithme dichotomique.

Le même principe est appliqué à chaque patrie. Nous pouvons donc en déduire que nous utiliserons un procédé récursif pour le tri rapide.

Le principe comporte certaines similarités avec le tri par fusion, mais ici les deux sous-structures n'ont pas nécessairement une taille semblable (car c'est le pivot qui détermine l'endoit de la séparation), et pour le tri rapide il n'est pas nécessaire de fusionner les sous ensembles lors de la remontée dans la pile de récursion.

Le choix du pivot est relativement important, et en pratique nous pouvons utiliser le premier ou le dernier élément.

Merge Sort : Tri par fusions

Comme pour le tri rapide, le tri par fusions repose sur le principe "diviser pour régner" (divide and conquer). Nous pouvons simplifier le tri en divisant notre structure en structures plus petites de même dimension à une valeur près (par exemple diviser notre tableau en 2 parties). Comme nous divisons à chaque fois le problème en 2, nous parlons d'algorithme dichotomique.

Le même principe est appliqué à chaque patrie. Nous pouvons donc en déduire que nous utiliserons un procédé récursif pour le tri par fusions.

lorsque nous ne pouvons plus diviser notre sous-tableau (une seule cellule), la récursion s'arrête, et nous remontons la pile de récursion en fusionnant à chaque fois les sous-structures, jusqu'au moment où nous atteignons le niveau de départ et que notre structure est triée.

Exemple de code Pascal de tri par fusions

Code Pascal (Tri par fusion) (17 lignes)

function mergeSort(var a : array of integer; minIndex, maxIndex : integer);
{Pre: 	a defined
		maxIndex>=minIndex;
		minIndex>=0;
		a[minIndex..maxIndex] defined
 Post:	for each i into minIndex..maxIndex, a[maxIndex] >= a[i] 
}
var center : integer; {center of the array}
begin
	if minIndex > maxIndex 	                    {O(1)}
	then begin
		center := (minIndex + maxIndex) div 2;  {O(1)}
		mergeSort(a, minIndex, center);         {T(n/2)}
		mergeSort(a, center+1, maxIndex);       {T(n/2)}
		merge(a, minIndex, center, maxIndex);   {O(n)}
	end
end;

Retourner au début du code

Type de notation à utiliser pour les ordres de grandeur :

Paramètres de langue du site

Si vous préférez continuer sur le site en français, cliquez sur "Annuler". Si vous annulez, ce message n'apparaîtra plus durant la session.

You are on the French version of the site, but your system indicates that you prefer to use the English language.
The entire site is not translated yet, but the menus and buttons on the interface are largely translated.

Would you like to reach the page in English?
Click here to continue in English: Consult the English version of this page

U bevindt zich op de Franse versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Sie befinden sich in der französischen Version der Website, Ihr System gibt jedoch an, dass Sie die deutsche Sprache bevorzugen.
Die gesamte Site ist noch nicht übersetzt, aber die Menüs und Schaltflächen auf der Benutzeroberfläche sind weitgehend übersetzt.

Möchten Sie die Seite auf Deutsch erreichen?
Klicken Sie hier, um fortzufahren: Konsultieren Sie die deutsche Version dieser Seite

Version en cache

21/11/2024 09:50:45 Cette version de la page est en cache (à la date du 21/11/2024 09:50:45) afin d'accélérer le traitement. Vous pouvez activer le mode utilisateur dans le menu en haut pour afficher la dernère version de la page.

Document créé le 16/06/2005, dernière modification le 26/10/2018
Source du document imprimé : https://www.gaudry.be/programmer-trier.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.