Visualisation du tri à bulles

Les algorithmes de tri placent les éléments d'un tableau dans un certain ordre.
Utilisons le tri à bulles (bubble sort) pour trier des nombres du plus petit au plus grand, changeant essentiellement quelque chose comme ceci :
[9, 1, 0, 4]
en ceci :
[0, 1, 4, 9].
L'algorithme de tri à bulles est court et simple, mais cela a un prix : une faible efficacité - un sujet idéal pour un codeur débutant !
Les valeurs inférieures "remontent" (bubble up) vers le haut si le tableau est affiché verticalement - d'où le nom. Dans notre cas, le tableau est horizontal, elles "remontent vers la gauche" à la place.
Pour rendre les choses un peu plus excitantes, nous allons attribuer une couleur différente à chaque nombre et afficher le tableau après chaque passe.

Version tableau unidimensionnel :

Cela semble étrange car il y a des lignes vides - nous les ajouterons plus tard lorsque nous passerons à la version 2D.

<html>

<body>

const canvas = document.getElementById("myCanvas");

const context = canvas.getContext("2d");

const shuffleLength = 1000;

const rowLength = 360;

const array=[]

for (let n = 0; n < rowLength; n++)

array[n] = n;

for (let n = 0; n < shuffleLength; n++) {

let cell1 = Math.floor(Math.random() * rowLength);

let cell2 = Math.floor(Math.random() * rowLength);

let temp = array[cell1];

array[cell1] = array[cell2];

array[cell2] = temp;

}

function animate() {

let swapped = false;

for (let i = 1; i <= rowLength - 1; i++) {

if (array[i - 1] > array[i]) {

let temp = array[i - 1];

array[i - 1] = array[i];

array[i] = temp;

swapped = true;

}

for (let n = 0; n < rowLength; n++) {

context.fillStyle = `hsl(${array[n]},100%,50%)`;

context.fillRect(n * 2, 0, 2, 50);

}

if (swapped)

window.requestAnimationFrame(animate);

}

animate();

</script>

</body>

</html>

Les lignes [1-6] configurent le Canvas HTML5, que nous utiliserons pour afficher le tableau.
[8] combien de fois mélanger les éléments avant le tri - choisi arbitrairement
[9] le nombre d'éléments
[12] le tableau à trier - vide pour l'instant
[13-14] remplir le tableau avec des nombres : [0, 1, 2, 3...]
[20-26] Mélanger le tableau. En raison de la manière dont nous avons rempli le tableau en [13-14], il est déjà trié. Pour voir le tri à bulles en action, nous devons détruire cet ordre. Pour ce faire, nous sélectionnons (pseudo-)aléatoirement deux éléments et échangeons leurs valeurs. Nous répétons ce processus shuffleLength fois.
[29-48] Tri réel et visualisation :
[30] Nous supposons qu'aucun élément n'aura besoin d'être échangé, ce qui signifie que tous les éléments sont déjà triés. Si l'algorithme nous prouve le contraire, nous savons qu'une autre itération est nécessaire.

[33-40] L'algorithme du Tri à Bulles
Maintenant vous connaissez la terrible vérité ! Cet algorithme consiste vraiment en seulement 6 instructions ! Tout ce battage médiatique pour cette petite boucle ! Vous regrettez probablement d'avoir navigué sur cette page, mais puisque vous êtes déjà là, autant finir de lire :
[33] Pour les éléments 1-360 :
[34] Si cet élément a une valeur supérieure au précédent :
[35-38] échanger les éléments : [35] copier le premier élément dans la variable temporaire
[36] copier le deuxième élément dans le premier
[37] copier la valeur temporaire dans le deuxième élément
[38] Comme nous avons dû échanger des éléments, notre hypothèse de [30] n'est plus vraie.

[41-44] Visualisation :
[41] Pour chaque élément :
[42] Définir la couleur à la valeur de
HSL (Teinte-Saturation-Luminosité) est une méthode de représentation des couleurs. Nous l'utilisons parce que pour une suite de nombres de 0 à 359, cela crée un arc-en-ciel. C'est donc juste une méthode pour obtenir une image (un arc-en-ciel) sans beaucoup de code.
[43] Dessiner un rectangle de 2x50 pixels.
[46-47] Si nous avons échangé des éléments, le tri peut être incomplet - vérifions en exécutant une autre passe.

Voici à quoi cela ressemble :

Cliquez sur l'image pour redémarrer.

Avec juste quelques lignes supplémentaires, nous pouvons trier un tableau bidimensionnel, de sorte que nous ayons plusieurs lignes indépendantes (ce que vous avez vu en haut de cette page) :

<html>

<body>

const canvas = document.getElementById("myCanvas");

const context = canvas.getContext("2d");

const mainArray = [];

const shuffleLength = 1000;

const rowLength = 360;

for (let row = 0; row < 90; row++) {

const array=[]

for (let n = 0; n < rowLength; n++)

array[n] = n;

mainArray[row] = array;

}

for (let row = 0; row < 90; row++) {

let array = mainArray[row];

for (let n = 0; n < shuffleLength; n++) {

let cell1 = Math.floor(Math.random() * rowLength);

let cell2 = Math.floor(Math.random() * rowLength);

let temp = array[cell1];

array[cell1] = array[cell2];

array[cell2] = temp;

}

function animate() {

let swapped = false;

for (let row = 0; row < 90; row++) {

let array = mainArray[row];

for (let i = 1; i <= rowLength - 1; i++) {

if (array[i - 1] > array[i]) {

let temp = array[i - 1];

array[i - 1] = array[i];

array[i] = temp;

swapped = true;

}

for (let n = 0; n < rowLength; n++) {

context.fillStyle = `hsl(${array[n]},100%,50%)`;

context.fillRect(n * 2, row * 2, 2, 2);

}

if (swapped)

window.requestAnimationFrame(animate);

}

animate();

</script>

</body>

</html>

Nous avons ajouté un tableau principal mainArray à deux dimensions [7]. Ce qui était le tableau dans la version précédente est maintenant un élément dans le mainArray : [15, 19, 32].
Maintenant, nous devons répéter toutes les actions pour chaque ligne : [11, 18, 31].
Nous dessinons maintenant des carrés de 2x2 pixels en [42].

Profitez des bulles !

Plus de tutoriels JavaScript :

Jeu de type Idle en environ 200 lignes de pur JavaScript
Boucle de texte animée