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 :

Taalinstellingen van de site

Als u liever doorgaat op de Nederlandse versie van de site, klik dan op "Annuleren". Als je annuleert, zal dit bericht niet meer verschijnen tijdens de sessie.

You are on the Dutch 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

Sie befinden sich in der Holländisch 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

Vous vous trouvez sur la version néerlandaise du site, mais votre système indique que vous préférez utiliser la langue française.

Souhaitez-vous atteindre la page en français?
Cliquez ici pour continuer en français: Consulter la page en français

Nederlandse vertaling

U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.

Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.

Bij voorbaat dank.

Document heeft de 16/06/2005 gemaakt, de laatste keer de 26/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/programmer-trier.html

De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.