Comment trier facilement avec l'algorithme Bubble Sort en Javascript

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.