Article source
L'algorithme du 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 d'apprentissage de la programmation de bas niveau et des concepts d'informatique. Comme le dit l'adage, la meilleure façon de consolider ses connaissances dans un domaine est de l'enseigner, et comme j'ai déjà rempli mon quota pour ennuyer ma partenaire avec des discussions sur la programmation pour le mois (probablement l'année), j'ai pensé écrire une série d'articles avec certaines des choses que j'ai apprises. Celui-ci en fait partie.
Qu'est-ce que l'algorithme du tri à bulles
L'algorithme du tri à bulles est généralement appliqué lorsque la simplicité est privilégiée par rapport à l'efficacité. Il a une complexité temporelle de O(n^2), ce qui est moins qu'idéal lorsqu'on traite de grandes listes.
Comment fonctionne-t-il
Pour expliquer son fonctionnement, voici du 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. Nous commençons par placer les deux pointeurs sur le premier élément de la liste. Nous parcourons ensuite toute la liste avec pointer2 et échangeons l'élément à la position de pointer2 si l'élément à la position pointer2 + 1 a une valeur supérieure. Nous répétons ce processus jusqu'à atteindre la fin de la liste. Nous avançons ensuite pointer1 de 1 et nous recommençons le processus avec pointer2.
Vous avez peut-être remarqué que nous avons besoin d'un moyen d'éviter de vérifier les é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 y parvenir 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 tourne 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 !