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 :

Einstellungen für die Site-Sprache

Wenn Sie lieber mit der deutschen Version der Website fortfahren möchten, klicken Sie auf "Abbrechen". Wenn Sie abbrechen, wird diese Meldung während der Sitzung nicht mehr angezeigt.

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

Vous vous trouvez sur la version allemande 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

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 16/06/2005, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/de/programmer-trier.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.