Dans ce nouvel article je vous propose d’apprendre (ou réapprendre) à implémenter des algorithmes de tri qui ne font pas appel à la fonction “sort” disponible en Javascript. Savoir trier des tableaux est non seulement utile lorsque l’on manipule des données, mais cela vous permettra également de vous améliorer en algorithmie. Le tri des tableaux est également une façon d’apprendre (ou de réapprendre) des méthodes d’optimisation algorithmiques pour utiliser plus intelligemment les ressources. Après avoir vu ce qu’implique l’implémentation de différentes méthodes pour trier, nous passerons à la pratique en implémentant trois algorithmes utilisés pour trier des tableaux en Javascript :
- Le “tri à bulles” (“bubble sort” en anglais”)
- Sa variante le “tri à peigne” (“comb sort” en anglais)
- Et enfin le “tri rapide” (“quicksort” en anglais).
Table des matières :
Pourquoi mettre en place des algorithmes de tri ?
Si vous avez l’habitude de travailler avec Javascript, vous avez sans aucun doute l’habitude d’utiliser la fonction “sort” pour trier des tableaux uni ou multi-dimensionnels. En voici un exemple :
var Arr = [2,5,3,1,6]
Arr.sort(function (a, b) {
return a - b
})
console.log(Arr)
// [1, 2, 3, 5, 6]
var Arr = [[2,1,5],[1,4,7],[2,1,6]]
Arr.sort(function (a,b) {
var c
a.some(function (d,i) {
return c = d - b[i]
})
return c
})
console.log(Arr)
// [[1, 4, 7],[2, 1, 5],[2, 1, 6]]
Cette méthode est tout à fait valable, mais dans certains cas il peut être intéressant d’apprendre (ou de réapprendre) à implémenter des méthodes de tri sans utiliser une fonction comme “sort”. Il en existe aujourd’hui plusieurs comme : tri par sélection, insertion, à bulles, rapide etc… Bien que relativement évident à comprendre et mettre en œuvre, le problème du tri des tableaux en informatique a amené au développement de plusieurs approches et algorithmes.
Bubble sort
Le “ tri à bulles “ (“Bubble sort” en anglais) est le plus simple des algorithmes de tri, mais aussi le moins efficace. Il s’agit d’un algorithme présenté principalement dans un but éducatif, mais peu utilisé aujourd’hui dans la pratique. La procédure de l’algorithme consiste à étudier par paires les valeurs d’une liste et à remettre progressivement les valeurs dans le bon ordre. L’algorithme s’arrête lorsqu’il n’y a plus de mise à jour à faire. Exemple de mise en œuvre avec la liste suivante :
3, 2, 4, 1
On observe d’abord les deux premières valeurs qui forment une “paire”, soit 3 et 2. On constate que 3 est plus grand que 2, on met donc à jour la liste de cette façon :
2, 3, 4, 1
On étudie ensuite la deuxième paire, soit 3 et 4. L’ordre ici est correct, par conséquent, on ne procède à aucune mise à jour. On étudie ensuite la troisième paire, soit les valeurs 4 et 1. On doit changer l’ordre des valeurs, et la liste est donc mise à jour :
2, 3, 1, 4
On reprend depuis le début avec les deux premières valeurs, soit 2 et 3. L’ordre étant correct, on ne procède à aucune mise à jour. La paire suivante, composée des valeurs 3 et 1, doit quant à elle faire l’objet d’un changement. On met donc à jour la liste :
2, 1, 3, 4
Les deux dernières valeurs (soit 3 et 4) sont dans le bon ordre, on peut donc revenir au début de la liste. Il faut alors modifier l’ordre des valeurs 2 et 1. On met à jour la liste comme suit :
1, 2, 3, 4
La liste est maintenant organisée dans le bon ordre. L’algorithme permet certes de réaliser un tri, mais pas de la façon la plus efficace possible car on est obligé de regarder la liste plusieurs fois alors qu’il serait possible de limiter ces opérations. Sa variante, le “tri à peigne” (‘Comb sort” en anglais), implique d’accélérer le travail en étudiant d’abord des paires très éloignées puis des paires très proches. Nous verrons en détail son fonctionnement dans la deuxième partie de cet article.
QuickSort
L’algorithme dit de “tri rapide” (“QuickSort” en anglais”) quant à lui cherche justement à optimiser le tri en adoptant une approche que l’on qualifie de “diviser pour régner”. Le concept général est de partitionner la liste à trier en plusieurs sous-ensembles qui vont faire l’objet d’un tri distinct. On peut réaliser ce travail en utilisant une valeur pivot qui va nous permettre en quelque sorte de diviser la liste en deux. L’idée étant de pouvoir placer à gauche du pivot tous les éléments inférieurs, et à droite tous les éléments supérieurs. Là aussi, repartons de notre exemple précédent pour comprendre ce travail :
3, 2, 4, 1
La première des choses est de choisir une valeur de “pivot”. Cette valeur va nous servir à nous permettre de traiter la liste des valeurs à trier. Par défaut, on peut choisir la dernière valeur. Cette valeur sera donc au début 1. On regarde ensuite si les valeurs de la liste sont inférieures à la valeur de pivot. Aucune des valeurs n’est inférieure à 1. Par conséquent, on va uniquement procéder à une opération qui consiste à intervertir l’ordre de la première est de la dernière valeur. Nous avons donc à cette étape un nouveau tableau :
1, 2, 4, 3
Le nouveau pivot est maintenant 3. On procède de la même façon, mais on s’intéresse cette fois-ci aux valeurs de 2 à 3. On constate que seul 2 est inférieur à pivot. On consigne donc l’index de la valeur suivante, soit 4, et on procède à un changement de place des deux dernières valeurs pour obtenir cette liste :
1, 2, 3, 4
Toutes les valeurs sont maintenant à la bonne place. Nous venons donc d’apprendre (ou de réapprendre) à mettre en œuvre deux algorithmes de tri pour trier des listes. Je vous propose maintenant de passer à l’étape suivante qui consiste à implémenter ces trois algorithmes en Javascript.
Implémentations en Javascript
Nous allons à présent voir comment implémenter ces algorithmes avec le langage Javascript. Pour chacune des implémentations, je précise que nous apprendrons à implémenter les algorithmes pour des listes uni et multidimensionnels (soit des listes avec seulement une ou au contraire plusieurs dimensions par variables).
Bubble sort
Nous allons tout d’abord implémenter la méthode du “tri à bulles”. Commençons par déclarer une variable “ToSort” qui contient la liste des valeurs à trier :
var ToSort = [4,2,5,1,3]
// ToSort = [[2,1],[1,1],[2,3],[2,2],[0,1]]
Vous trouverez en commentaire une liste avec plusieurs dimensions pour faire des tests. On déclare à la suite une variable “Swap” pour consigner le nombre de modifications réalisées dans le tri de la liste. Le programme s’arrête lorsqu’il n’y a plus eu aucune modification après un tour complet :
var Swap = 0
On va ensuite mettre en place une boucle qui va itérer sur la longueur de la variable “ToSort”, et on implémente le premier cas de figure où la liste comporte des valeurs qui sont multidimensionnelles (pour le savoir, on regarde si le premier élément du tableau “ToSort” contient plusieurs dimensions) :
for (var i = 0; i < ToSort.length-1; i++) {
if (ToSort[0].length !== undefined) {
for (var j = 0; j < ToSort[i].length; j++) {
if (ToSort[i+1][j] < ToSort[i][j]) {
var Temp = [ToSort[i+1][j],ToSort[i][j]]
ToSort[i+1][j] = Temp[1]
ToSort[i][j] = Temp[0]
Swap += 1
}
}
}
Si les valeurs contiennent plusieurs dimensions, on va devoir faire une comparaison valeurs par valeurs mais également colonnes par colonnes. Si la valeur suivante est inférieure à la valeur comparée, on procède à son déplacement dans la liste (en échangeant simplement leur place) et on incrémente la variable “Swap” de 1. On peut ensuite mettre en place la cas où la liste ne contient pas des valeurs multidimensionnels :
else {
if (ToSort[i+1] < ToSort[i]) {
Temp = [ToSort[i+1],ToSort[i]]
ToSort[i+1] = Temp[1]
ToSort[i] = Temp[0]
Swap += 1
}
}
Même opération que précédemment, sauf qu’il n’est pas utile de faire une comparaison colonnes par colonnes. Enfin, on doit vérifier l’état de variable “Swap” dans le cas où nous sommes au bout de la boucle principale. Si cette valeur est à 0 (ce qui indique un bon ordre de toutes les valeurs), on peut tout simplement stopper la boucle, dans le cas contraire elle sera réinitialisée. Puis on peut afficher les résultats :
if (i+1 === ToSort.length-1) {
if (Swap === 0) {
break
} else {
i -= ToSort.length-1
Swap = 0
}
}
}
console.log(ToSort)
Voici des exemples de résultats :
[ 1, 2, 3, 4, 5 ]
[ [ 0, 1 ], [ 1, 1 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ] ]
Combsort
Cet algorithme du “tri à bulles” possède une variante dénommée “ comb sort “ (ou “tri à peigne” en anglais). Elle permet de nettement améliorer l’algorithme du “tri à bulles” en déplaçant plus rapidement les plus petites valeurs vers le début de la liste. L’inconvénient du “tri à bulles” est que la comparaison est toujours réalisée en étudiant le voisin immédiat de chacun des éléments, ce qui ralenti fortement le tri des valeurs. En commençant au contraire par des valeurs plus éloignées, on pourra déplacer plus rapidement les plus petites valeurs. Voici l’implémentation de cet algorithme en Javascript :
var ToSort = [4,2,5,1,3]
// ToSort = [[2,1],[1,1],[2,3],[2,2],[0,1]]
var ToSortRange = ToSort.length
while (ToSortRange > 1 || Swap === 1) {
ToSortRange = Math.floor(ToSortRange / 1.3)
if (ToSortRange < 1) {
ToSortRange = 1
}
var i = 0
var Swap = 0
while(i < ToSort.length - ToSortRange) {
if (ToSort[0].length !== undefined) {
for (var j = 0; j < ToSort[0].length; j++) {
if (ToSort[i][j] > ToSort[i + ToSortRange][j]) {
var Temp = [ToSort[i][j],ToSort[i + ToSortRange][j]]
ToSort[i][j] = Temp[1]
ToSort[i + ToSortRange][j] = Temp[0]
Swap = 1
}
}
} else {
if (ToSort[i] > ToSort[i + ToSortRange]) {
Temp = [ToSort[i],ToSort[i + ToSortRange]]
ToSort[i] = Temp[1]
ToSort[i + ToSortRange] = Temp[0]
Swap = 1
}
}
i += 1
}
}
console.log(ToSort)
Ce qui change ici, c’est l’introduction d’une notion d’intervalle (variable “ToSortRange”), calculée sur la base de la longueur de la liste/tableau à trier divisé par un facteur (ici 1,3). Plutôt que de traiter une valeur en étudiant à chaque fois son voisin immédiat, comme dans l’implémentation classique de l’algorithme du “tri à bulles”, on traite d’abord les voisins les plus éloignés puis les voisins les plus proches.
QuickSort
Enfin, on peut ensuite passer à l’implémentation de l’algorithme de “tri rapide”. Vous pouvez là aussi déclarer deux listes à trier :
var ToSort = [4,2,5,1,3]
// ToSort = [[2,1],[1,1],[2,3],[2,2],[0,1]]
L’implémentation du “tri rapide” va s’articuler autour d’une logique récursive avec deux fonctions : une fonction de tri et une fonction pour partitionner. Nous commençons donc d’abord par créer une fonction “QuickSort” (la fonction principale pour trier) qui prend pour paramètres le tableau à trier, la valeur d’index minimale et la valeur maximale :
function QuickSort (List,Low,High) {
On met en place ensuite une condition si la valeur “Low” est inférieur à la valeur “High” (ou autrement dit, si la valeur d’index minimale est inférieur à la valeur d’index maximale) :
if (Low < High) {
On déclare alors une variable “PartitionIndex” pour récupérer l’index à utiliser pour partitionner la liste. Cette valeur est obtenue par l’utilisation d’une fonction “Partition” qui utilise pour paramètres la liste à trier, ainsi que la valeur minimale et la valeur maximale d’index :
var PartitionIndex = Partition(List,Low,High)
Puis on déclare deux appels à la fonction “QuickSort” et on ferme la fonction :
QuickSort(List,Low,PartitionIndex-1)
QuickSort(List,PartitionIndex+1,High)
}
}
On réalise deux appels : dans le cas, la valeur d’index maximale correspond à la valeur de “PartitionIndex” moins 1. Dans le second cas, le minimum est égal à la valeur de “PartitionIndex” plus 1. Une fois que cela est fait, on déclare ensuite une fonction “Partition” qui prend pour paramètres la liste à trier, et les valeurs minimales et maximales d’index. On déclare dans le même temps le premier cas de figure qui correspond à une liste qui est uni-dimensionnelle :
function Partition (List,Low,High) {
if (List[0].length === undefined) {
var Pivot = List[High]
var Index = Low
var Temp
for (var j = Low; j < High; j++) {
if (List[j] < Pivot) {
Temp = [List[Index],List[j]]
List[Index] = Temp[1]
List[j] = Temp[0]
Index += 1
}
}
Temp = [List[Index],List[High]]
List[Index] = Temp[1]
List[High] = Temp[0]
return Index
}
L’idée est d’identifier ici une valeur qui serait inférieure à la variable “Pivot” (qui correspond à la valeur utilisée pour partitionner). Lorsqu’une telle valeur est identifiée, on peut mettre à jour la valeur d’index, pour utiliser un nouveau pivot lors des utilisations suivantes de la fonction “QuickSort”. Une fois la boucle terminée, on modifie l’ordre des éléments et on retourne la valeur “Index”, qui va correspondre à la valeur de la variable “PartitionIndex” dans la fonction “QuickSort”. On peut ensuite mettre en œuvre le cas où la liste contient des valeurs avec plusieurs dimensions :
else {
Pivot = List[High]
Index = Low
Temp
for (var j = Low; j < High; j++) {
for (var k = 0; k < List[0].length; k++) {
if (List[j][k] < Pivot[k]) {
Temp = [List[Index],List[j]]
List[Index] = Temp[1]
List[j] = Temp[0]
Index += 1
}
}
}
Temp = [List[Index],List[High]]
List[Index] = Temp[1]
List[High] = Temp[0]
return Index
}
}
On fait la même chose que précédemment, sauf qu’il faut ici intégrer une comparaison par colonnes. Puis on fait appel à la fonction “QuickSort” et on affiche les résultats :
QuickSort(ToSort,0,ToSort.length-1)
console.log(ToSort)
Et voici des exemples si on lance le programme :
[ 1, 2, 3, 4, 5 ]
[ [ 0, 1 ], [ 1, 1 ], [ 2, 1 ], [ 2, 2 ], [ 2, 3 ] ]
Conclusions
Nous avons donc appris (ou réappris) à implémenter trois algorithmes très connus pour trier des tableaux : le” tri à bulles”, sa variante “le tri à peigne” et enfin le “tri rapide”. Si les algorithmes de tri sont très utiles pour réaliser du triage en tenant compte de critères comme la performance, connaître ces algorithmes permet aussi de découvrir des stratégies d’optimisation lorsqu’il s’agit de traiter d’importants volumes de données : diviser pour régner, optimiser l’étude des distances etc… Enfin, vous pouvez dans vos entretiens professionnels être confronté à des questions relatives à l’algorithmie qui peuvent porter sur des sujets aussi classiques sur le tri des données. Il est donc utile à plusieurs titres de connaître ces algorithmes et de savoir les implémenter.
Simon CHABROL 
Laisser un commentaire