Comment trier facilement avec l'algorithme Bubble Sort en Javascript
Publié le 07 novembre 2022
Nous voilà parti pour une série d'articles sur les algorithmes de tri.
Pour ce premier volet, nous allons passer en revue l'algorithme de tri à bulles, ou Bubble Sort en anglais.
Fonctionnement de Bubble Sort
Le principe est simple et le nom Bubble sort n'est pas choisi par hasard :
- Les plus grandes valeurs considérées comme lourdes coulent (sink en anglais) progressivement vers le bas de la liste.
- Les plus petites valeurs considérées comme légères remontent comme des bulles (bubble pour remonter / bouillonner en anglais) vers le haut de la liste.
Prenons la série de nombres suivante :
En itérant sur chaque nombre de la série, si le nombre courant est supérieur au nombre suivant, alors on permute leur position :
Lorsque une boucle complête sur la série est faite sans qu'aucune permutation n'ait été effectuée, l'opération de tri est terminée.
Exemple de code
Traduisons tout ça en code avec un exemple en Javascript :
const swap = ( arr, i, j ) => {
let temp = arr[ i ];
arr[ i ] = arr[ j ];
arr[ j ] = temp;
}
const bubbleSort = arr => {
for ( let i = 0; i < arr.length - 1; i++ ) {
let swapped = false;
for ( let j = 0; j < arr.length - 1; j++ ) {
if ( arr[ j ] > arr[ j + 1 ] ) {
swap( arr, j, j + 1 );
swapped = true;
}
}
// SI aucun nombre n'a été permuté lors de la boucle précedente
// ALORS le tri est terminé et on peut sortir de la boucle
if ( !swapped ) {
break;
}
}
return arr;
}
const arr = [ 2, 1, 4, 3, 5, 7, 6, 8 ];
bubbleSort( arr ) // [ 1, 2, 3, 4, 5, 6, 7, 8 ]
Performances de Bubble Sort
Grosso modo, n'utilisez pas cet algorithme en production ! Bien qu'il soit facile à comprendre, le Bubble Sort est en réalité bien moins performant que d'autres de ses compères, comme le Quick Sort ou le Insertion Sort que nous étudierons dans de prochains articles.
Le Bubble Sort est surtout présenté à titre éducatif pour initier les néophytes aux algorithmes de tri.
2 commentaires
Guiguizaure
Hugo Derré