Article source
L'algorithme de tri à bulles - DEV Community
Maximilian
Introduction
J'ai récemment suivi un cours sur les structures de données et les algorithmes dans le cadre de ma démarche pour apprendre la programmation de bas niveau et les concepts informatiques. Comme le dit l'adage, la meilleure façon de consolider ses connaissances sur un sujet est de l'enseigner, et comme j'ai déjà rempli mon quota d'ennuyer mon partenaire avec des discussions sur le code pour le mois (probablement l'année), j'ai pensé écrire une série d'articles sur certaines des choses que j'ai apprises. Voici l'un de ces articles.
Qu'est-ce que l'algorithme de tri à bulles
L'algorithme de tri à bulles est généralement utilisé lorsque la simplicité est privilégiée par rapport à l'efficacité. Sa complexité temporelle est de O(n^2), ce qui est loin d'être idéal lorsqu'on traite de listes plus grandes.
Comment fonctionne-t-il
Pour expliquer son fonctionnement, voici un pseudo-code :
for pointer1 in list
for pointer2 in list
if list[j] > list[j + 1]
swap list[j] and list[j + 1]
pointer2++
pointer1++
L'idée de cet algorithme est de faire « remonter » les éléments les plus grands de la liste vers la fin. On peut le concevoir avec 2 pointeurs, pointer1 et pointer2. On commence par placer les deux pointeurs sur le premier élément de la liste. On parcourt ensuite toute la liste avec pointer2 et on échange l'élément à la position de pointer2 si l'élément à la position pointer2 + 1 est plus grand en valeur. On répète ce processus jusqu'à atteindre la fin de la liste. On déplace ensuite pointer1 de 1 vers l'avant et on recommence le processus avec pointer2.
Vous avez peut-être remarqué que nous avons besoin d'un moyen d'éviter de vérifier des éléments que nous avons déjà triés. Étant donné que le but de chaque itération est de déplacer les éléments les plus grands vers la fin de la liste, nous pouvons le faire en limitant la borne de pointer2 à la valeur de pointer1 + 1.
Comment l'implémenter
Voici une implémentation abondamment commentée en Typescript :
function bubbleSort(arr: number[]): void {
// pointer 1
for (let i = 0; i < arr.length; ++i) {
// pointer 2 + limit iterations by pointer1 + 1
for (let j = 0; j < arr.length - 1 - i; ++j) {
// check if current item is larger than the next item
if (arr[j] > arr[j + 1]) {
// temporarily store the current item so we don't lose it
const tmp = arr[j];
// swap the items in the array
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
Trié
Ce n'est pas un algorithme vers lequel on se tournerait naturellement dans la plupart des cas, mais je pense que c'est un bon choix simple et facile pour débuter. J'espère que vous l'avez trouvé utile ou, au moins, un peu intéressant !