Algorithmes de tris

Sommaire du document

Dans nos différents algorithmes de tri, nous rencontrerons principalement deux types d'opérations : les comparaisons et les permutations. Il est clair que les performances des algorithmes différeront selon le nombre et la proportion de ces opérations (les comparaisons sont nettement moins coûteuses que les permutations).
Bien que ces deux types représentent les opérations fondamentales des algorithmes de tris, nous pouvons à certains moments utiliser un autre type d'opération : les affectations, pour remplacer certaines suites de permutations (une permutation est en fait une série de trois affectations).

Voyons à présent comment implémenter les différents algorithmes :

Exemples concrets d'implémentations : les tris en C, trier des structures en C, les tris en Java.

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.

Boucle intérieure

Nous nous positionnons à la fin du tableau, et nous comparons le dernier élément (à l'index i) avec son prédécesseur (à l'index i-1). S'il est plus petit que son prédécesseur, nous permutons les deux éléments.

Ensuite, nous nous positionnons sur l'avant dernier élément (i=i-1), et nous comparons ce dernier (à l'index i) avec son prédécesseur (à l'index i-1). S'il est plus petit que son prédécesseur, nous permutons les deux éléments.

Nous répétons ces opérations jusqu'au moment où le deuxième élément du tableau est atteint.
Pourquoi ne pas aller jusqu'au premier élément ? Parceque dans ce cas, nous comparerions le premier élément avec son prédécesseur qui n'existe pas (OutOfBoundException).

A la fin de ces opérations, nous avons la certitude que le premier élément du tableau est le plus petit.

Boucle extérieure

Nous devrions normalement effectuer le travail complet de la boucle intérieure un nombre de fois égal à la taille du tableau.

Boucle
extérieure
8462134120
18462134120
8462131420
8462113420
8461213420
8416213420
8146213420
1846213420
21846213420
1846241320
1846241320
1842641320
1824641320
1284641320
1284641320
31284641320
1284641320
1284461320
1284461320
1248461320
1248461320
1248461320
41248461320
1248461320
1248461320
1244861320
1244861320
1244861320
1244861320
51244861320
1244861320
1244681320
1244681320
1244681320
1244681320
1244681320
61244681320
1244681320
1244681320
1244681320
1244681320
1244681320
1244681320
71244681320
1244681320
1244681320
1244681320
1244681320
1244681320
1244681320
 
 1244681320

Légende :

Valeurs de départ | Comparaisons | Permutations | Valeurs triées

Que pouvons nous remarquer ?

Les éléments sont correctement triés, mais nous avons un gaspillage à deux niveaux :

  • interne : après le premier passage, il n'est plus nécessaire de comparer la première valeur, et ainsi de suite.
  • externe : depuis le 5è passage de la boucle externe, les éléments sont triés.

Afin d'améliorer notre système, nous pouvons diminuer d'une unité (décrémenter) la valeur de notre compteur pour la boucle intérieure à chaque passage dans la boucle extérieure.
En plus, nous pouvons utiliser un booléen qui sera à false à chaque début de la boucle extérieure, et qui sera mis à true si une permutation a eu lieu. Si aucune permutation n'a eu lieu après une boucle intérieure, le tableau est trié.

Boucle
extérieure
8462134120
18462134120
8462131420
8462113420
8461213420
8416213420
8146213420
1846213420
21846213420
1846241320
1846241320
1842641320
1824641320
1284641320
31284641320
1284641320
1284461320
1284461320
1248461320
41248461320
1248461320
1248461320
1244861320
51244861320
1244861320
1244681320
61244681320
1244681320
 
 1244681320
Nous ne repassons plus dans la boucle 7, car la boucle 6 n'a généré aucune permutation.

Légende :

Valeurs de départ | Comparaisons | Permutations | Valeurs triées

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).

Tri par sélection de la plus petite valeur

Ce tri porte aussi le nom de tri par sélection en ordre croissant.

Nous commencons par le premier élément du tableau, que nous allons comparer avec le reste des éléments, à la recherche du plus petit. A chaque fois que nous rencontrerons un élément plus petit, celui-ci devient le candidat à la permutation.

Boucle
extérieure
8462134120
18462134120
8462134120
8462134120
8462134120
8462134120
8462134120
8462134120
1462134820
21462134820
1462134820
1462134820
1462134820
1462134820
1462134820
1264134820
31264134820
1264134820
1264134820
1264134820
1264134820
1246134820
41246134820
1246134820
1246134820
1246134820
1244136820
51244136820
1244136820
1244136820
1244613820
61244613820
1244613820
1244681320
71244681320
1244681320
81244681320
1244681320
 
 1244681320

Légende :

Valeurs de départ | Valeur à permuter | Comparaisons | Candidat à la permutation | Permutations | Valeurs triées

Tri par sélection de la plus grande valeur

Ce tri porte aussi le nom de tri en ordre décroissant.

Cet algorithme de tri est plus souvent utilisé. Le principe est identique, mais nous plaçons les éléments dans le tableau depuis la dernière case (qui contiendra l'élément qui possède la valeur la plus élevée) jusqu'à la première (la plus petite valeur).

Nous commencons par le dernier élément du tableau, que nous allons comparer avec le reste des éléments, à la recherche du plus grand. A chaque fois que nous rencontrerons un élément plus grand, celui-ci devient le candidat à la permutation.

Boucle
extérieure
8462134120
18462134120
8462134120
8462134120
8462134120
8462134120
8462134120
8462134120
28462134120
8462134120
8462134120
8462134120
8462134120
8462134120
8462141320
38462141320
8462141320
8462141320
8462141320
8462141320
4462181320
44462181320
4462181320
4462181320
4462181320
4412681320
54412681320
4412681320
4412681320
4214681320
64214681320
4214681320
1244681320
71244681320
1244681320
81244681320
1244681320
 
 1244681320

Légende :

Valeurs de départ | Valeur à permuter | Comparaisons | Candidat à la permutation | Permutations | Valeurs triées

Comparaisons entre le tri par sélection en ordre croissant et le tri par sélection en ordre décroissant

Lorsque nous effectuons des permutations, lors du tri par sélection en ordre croissant l'ordre d'apparition des éléments égaux (la valeur 4 dans nos exemples) est préservée. L'ordre est inversé lors de tri par sélection en ordre décroissant.

Propriétés du tri par sélection

Le nombre de passages dans la boucle extérieure est identique au nombre d'éléments de notre structure. Dans le cas de notre tableau, nous pouvons légèrement optimiser le code en évitant de comparer la dernière valeur avec elle même, mais ce gain serait compensé par un test qui serait effectué à chaque passage (par exemple en vérifiant que les deux indexes de cellules sont identiques, ce qui signifie que l'on travaille sur une seule cellule et qu'il n'est pas nécessaire de la trier).

A chaque passage dans la boucle extérieure, le nombre de comparaisons diminue de 1. Au xième passage dans la boucle extérieure, nous avons x-1 comparaisons.

Complexité du tri par sélection

Complexité du tri par sélection

Exemple de code Pascal de tri par sélections

  1. program selectionSort;
  2. function maxValueIndex(var a : array of integer; minIndex, maxIndex : integer);
  3. {Pre: a defined
  4. maxIndex>=minIndex;
  5. minIndex>=0;
  6. a[minIndex..maxIndex] defined
  7.  Post: for each i into minIndex..maxIndex, a[maxIndex] >= a[i]
  8. }
  9. var tempMax : integer;
  10. begin
  11. if minIndex >= maxIndex then maxValueIndex := minIndex;
  12. else begin
  13. tempMax := maxValueIndex(a, minIndex+1, maxIndex);
  14. if a[minIndex]<a[tempMax]
  15. then maxValueIndex := tempMax;
  16. else maxValueIndex := minIndex;
  17. end
  18. end;
  19. procedure swap(var a : array of integer; i, j : integer);
  20. {Pre: a defined
  21. j>i;
  22. i>=0;
  23. a[i] defined
  24. a[j] defined
  25.  Post: a[i]=old value at a[j] et a[j]=old value at a[i]
  26. }
  27. var temp: integer;
  28. begin
  29. temp := a[i];
  30. a[i] := a[j];
  31. a[j] := temp;
  32. end;
  33. procedure selectionSort(var a : array of integer; arraySize : integer);
  34. {Pre: a defined
  35. arraySize>=0;
  36. a indexed from 0 to arraySize -1
  37. for each i into 0..arraySize-1, a[i] defined
  38.  Post: for each i into 0..arraySize-2, a[i] <= a[i+1]
  39. }
  40. var i : integer;
  41. begin
  42. for i := arraySize downto 0 do
  43. swap(a, i, maxValueIndex(a,1,i));
  44. end;
  45. {main program
  46. }
  47. begin
  48. const maxIndice = 7;
  49. var testArray : packed array[0..maxIndice] of integer;
  50. testArray[0] := 8;
  51. testArray[1] := 4;
  52. testArray[2] := 6;
  53. testArray[3] := 2;
  54. testArray[4] := 13;
  55. testArray[5] := 4;
  56. testArray[6] := 1;
  57. testArray[7] := 20;
  58. var i : integer;
  59. writeln('Unsorted array :');
  60. for i:=0 to maxIndice do
  61. writeln('value ', testArray[i], ' at index ', i);
  62. selectionSort(testArray, maxIndice+1);
  63. writeln('Sorted array :');
  64. for i:=0 to maxIndice do
  65. writeln('value ', testArray[i], ' at index ', i);
  66. 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.

Boucle
extérieure
8462134120
18462134120
28462134120
8462134120
8462131420
38462131420
8462131420
8462131420
8462141320
48462141320
8462141320
8461241320
58461241320
8461241320
8461241320
8461241320
8412461320
68412461320
8412461320
8412461320
8124461320
78124461320
8124461320
8124461320
8124461320
8124461320
8124461320
1244681320
 
 1244681320

Légende :

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

Ordre de grandeur du tri par insertions

Nous pouvons appliquer le principe diviser pour régner pour le tri par insertion, même si à chaque fois nous avons un élément suivi par le reste des éléments. Ceci nous rappelle les méthodes head() et tail() que nous avions défini dans notre type abstrait Liste.

Selon le type de structure utilisé, la partie "combiner" (qui correspond àinsérer un élément) dans une liste triée est de Ordre de grandeur(n), ou pour un arbre rouge-noir de Ordre de grandeur(log n), ce qui nous donne Ordre de grandeur(n2) pour l'exécution totale du tri par insertions.

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 = 2h - 1

et

h = log2(n + 1)

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

Principe du Heap sort

Dans le cas du heap sort nous travaillerons en deux phases :

  • La construction.
  • Le tri.

Après chaque phase de tri, l'élément de la valeur la plus élevée se trouve repoussé en bas de l'arbre (puisque le but est d'avoir le plus petit élément en premier lieu, puis les éléments ordonnés de manière croissante). Il est donc nécessaire de reconstruire un nouvel arbre sans tenir compte de l'élément trié, et de répéter ce cycle jusqu'au moment où il ne reste plus qu'un élément.

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.

Complexité du tri par fusions

Complexité du tri par fusions

Nous pouvons constater que la complexité du tri par fusion Ordre de grandeur(n log n) est nettement inférieure à la complexité du tri par sélections Ordre de grandeur(n2). Le tri par fusions est beaucoup plus rapide que le tri par sélections.

Exemple de code Pascal de tri par fusions

  1. function mergeSort(var a : array of integer; minIndex, maxIndex : integer);
  2. {Pre: a defined
  3. maxIndex>=minIndex;
  4. minIndex>=0;
  5. a[minIndex..maxIndex] defined
  6.  Post: for each i into minIndex..maxIndex, a[maxIndex] >= a[i]
  7. }
  8. var center : integer; {center of the array}
  9. begin
  10. if minIndex > maxIndex {O(1)}
  11. then begin
  12. center := (minIndex + maxIndex) div 2; {O(1)}
  13. mergeSort(a, minIndex, center); {T(n/2)}
  14. mergeSort(a, center+1, maxIndex); {T(n/2)}
  15. merge(a, minIndex, center, maxIndex); {O(n)}
  16. end
  17. end;

 

Réseaux sociaux

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher les interactions avec les réseaux sociaux sur ces pages.

 

Nuage de mots clés

30 mots clés dont 0 définis manuellement (plus d'information...).

Avertissement

Cette page ne possède pas encore de mots clés manuels, ceci est donc un exemple automatique (les niveaux de pertinence sont fictifs, mais les liens sont valables). Pour tester le nuage avec une page qui contient des mots définis manuellement, vous pouvez cliquer ici.

Vous pouvez modifier vos préférences dans votre profil pour ne plus afficher le nuage de mots clés.

 

Historique et modifications de la page

  • Dimanche 04 Octobre 2009, 18:05 : Ajout de la complexité pour certains tris.
    Correction du tableau du tri par sélection.
    Ajout du tri par sélection en ordre décroissant.
    Ajout d'exemples en Pascal.

Liste des images

  1. Complexité du tri par sélection (Référence : infobrol)
  2. Complexité du tri par fusions (Référence : infobrol)

 

Astuce pour imprimer les couleurs des cellules de tableaux : http://www.gaudry.be/ast-rf-450.html
Aucun commentaire pour cette page

© Ce document issu de l′infobrol est enregistré sous le certificat Cyber PrInterDeposit Digital Numbertection. Enregistrement IDDN n° 5329-457
Document créé le 15/06/05 23:00, dernière modification le Mercredi 28 Juin 2017, 14:26
Source du document imprimé : http:///www.gaudry.be/programmer-trier.html
St.Gaudry©07.01.02
Outils (masquer)
||
Recherche (afficher)
Recherche :

Utilisateur (masquer)
Apparence (afficher)
Stats (afficher)
15838 documents
455 astuces.
550 niouzes.
3107 definitions.
447 membres.
8121 messages.

Document genere en :
0,10 seconde

Mises à jour :
Mises à jour du site
Citation (masquer)
Je place l'enthousiasme au-dessus même des compétences professionnelles.

Edward Appleton
 
l'infobrol
Nous sommes le Mardi 12 Décembre 2017, 05:45, toutes les heures sont au format GMT+1.00 Heure, heure d'hiver